/
/

[C++] std::vector 알아보기

vector
STLvector
avatar
뇽
2025.02.11
·
14 min read
3366

vector 안에서 일어나는 일들

vector 안에서 일어나는 일들
vector 에는 요소를 추가, 삭제하는 다양한 함수들이 존재한다. 우리는 그저 무심코 "요소를 추가하면 되고, 삭제하면 되고"라고 생각할것이다. 내가 지금까지 그랬다. 하지만 vector 가 내가 원하는 컨테이너인지 정확히 이해하기위해서, 또한 성능의 향상을 위해서는.. 각 함수가 호출되었을때 내부적으로 무슨일이 생기는지를 알고있어야한다. 이 무슨일이 생기는지를 이해하면 다른 컨테이너와 장,단점을 서로 비교할수있게될것이다. 각 함수에 따라 무슨일이 발생하는지를 파해쳐보려한다. < vector 의 내부 상황을 확인하기위한 함수와 구조체 > void print(const char* str) { std::cout
https://leestrument.tistory.com/entry/vector-%EC%95%88%EC%97%90%EC%84%9C-%EC%9D%BC%EC%96%B4%EB%82%98%EB%8A%94-%EC%9D%BC%EB%93%A4

여기 블로그 설명이 맛있어서(?) 먼저 이걸 보며 공부하기로 했다.

#include <iostream>
#include <vector>

void print(const char* str)
{
    std::cout << str << std::endl;
}

void print(int n)
{
	std::cout << n << "번 호출! " << std::endl;
}

void printResult(const char* str, int a, int b)
{
	std::cout << str << "은 " << a << "번의 루프에서 총 " << b << "번의 함수를 호출했습니다" << std::endl;
}

int counter = 0;
bool letsPrint = false;

struct T
{
	T()
	{
		if (letsPrint) print("Constructor"); counter++;
	}

	T(const T& other)
	{
		if (letsPrint) print("Copy Constructor"); counter++;
	}

	T(T&& other) noexcept
	{
		if (letsPrint) print("Move Constructor"); counter++;
	}

	~T()
	{
		if (letsPrint) print("~Destructor"); counter++;
	}

	T& operator=(const T& other)
	{
		if (letsPrint) print("Copy Assignment"); counter++; return *this;
	}

	T& operator=(T&& other) noexcept
	{
		if (letsPrint) print("Move Assignment"); counter++; return *this;
	}
};

해당 예제를 이용해 클래스의 객체가 생성되거나 파괴될 때 counter 를 증가시켜 함수가 몇번 호출되는지 셀 수 있다.

void push_back(const T& value);

int main()
{
	std::vector<T> vec;
	int loopLength = 100;
	for (int i = 0; i < loopLength; i++)
	{
		vec.push_back({});
	}
	printResult("push_back", loopLength, counter);

	return 0;
}
push_back 은 1번의 루프에서 총 3번의 함수를 호출했습니다
push_back 은 10번의 루프에서 총 80번의 함수를 호출했습니다
push_back 은 100번의 루프에서 총 868번의 함수를 호출했습니다
push_back 은 1000번의 루프에서 총 7274번의 함수를 호출했습니다
push_back 은 10000번의 루프에서 총 78568번의 함수를 호출했습니다
push_back 은 100000번의 루프에서 총 853042번의 함수를 호출했습니다

push_back({}) 을 하면, main 함수가 종료되기 전에 아래와 같이 콘솔에 출력된다.

Constructor
Move Constructor
~Destructor

  1. Constructor : {} 가 기본 생성자 T() 를 호출해 임시 객체를 생성한다. 생성된 임시 객체는 push_back 함수의 인자로 전달된다.

  2. Move Constructor : push_back 의 rvalue 레퍼런스 오버로드가 호출되면서 벡터 내부의 메모리에 임시 객체를 이동 생성하며, 이 때 T(T&& other) noexcept 가 호출된다.

  3. ~Destructor : push_back 호출이 완료되면, 인자로 전달된 임시 객체는 더 이상 필요하지 않으므로 소멸된다.

void emplace_back(Args&&... args)

int main()
{
	std::vector<T> vec;
	int loopLength = 100;
	for (int i = 0; i < loopLength; i++)
	{
		vec.emplace_back();
	}
	printResult("push_back", loopLength, counter);

	return 0;
}
emplace_back 은 1번의 루프에서 총 1번의 함수를 호출했습니다
emplace_back 은 10번의 루프에서 총 60번의 함수를 호출했습니다
emplace_back 은 100번의 루프에서 총 668번의 함수를 호출했습니다
emplace_back 은 1000번의 루프에서 총 5274번의 함수를 호출했습니다
emplace_back 은 10000번의 루프에서 총 58568번의 함수를 호출했습니다
emplace_back 은 100000번의 루프에서 총 653042번의 함수를 호출했습니다
emplace_back 은 1000000번의 루프에서 총 5199506번의 함수를 호출했습니다

emplace_back() 을 하면, main 함수가 종료되기 전에 아래와 같이 콘솔에 출력된다.

Constructor

emplace_back 은 전달된 인자를 그대로 사용해 객체를 벡터 내부의 메모리 공간에 직접 생성하기 때문에 임시 객체가 생성되지 않고, 따라서 이동 생성자의 호출이나 임시 객체의 소멸자 호출이 발생하지 않는다.

Constructor
Constructor
Move Constructor
~Destructor
Constructor
Move Constructor
Move Constructor
~Destructor
~Destructor

근데 3번만 emplace_back 을 호출해도 이렇게 난리가 난다. 기본 생성자만 호출한다고 해서 깔끔하게 들어갈 줄 알았지만.. 결과를 보니 그렇지 않았다. emplace_back 은 전달된 인자를 사용해 컨테이너 내부에 제자리에 객체를 생성하지만, 할당된 메모리가 부족할 경우에는 추가 과정이 발생하게 된다고 한다.

  1. 새로운 메모리 블록을 할당한다

  2. 기존의 원소들을 새 메모리로 옮긴다.
    - 먼저, 기존의 첫 번째 원소가 이동 : Move Constructor
    - 옮긴 후, 이전 메모리의 첫 번째 원소는 더 이상 필요 없으므로 소멸 : ~Destructor

void reserve(size_type new_cap);

앞에서 메모리 재할당이 수많은 함수 호출을 불러일으키는 것을 확인했다. reserve 를 통해 capacity 를 크게 설정해놓으면, vector 에 요소가 추가될 때 발생할 수 있는 재할당 가능성을 줄일 수 있다. reserve 가 호출되었을 때와 호출되지 않았을 때의 결과를 비교해보자.

// reserve를 호출하지 않았을 때
push_back 은 1000번의 루프에서 총 7274번의 함수를 호출했습니다
emplace_back 은 1000번의 루프에서 총 5274번의 함수를 호출했습니다

// reserve를 호출했을 때
push_back은 1000번의 루프에서 총 3000번의 함수를 호출했습니다
push_back은 1000번의 루프에서 총 1000번의 함수를 호출했습니다

void clear();

int main()
{
	std::vector<T> vec;
	vec.reserve(10);
	int loopLength = 10;
	for (int i = 0; i < loopLength; i++)
	{
		vec.emplace_back();
	}

	counter = 0;
	vec.clear();
	printResult("push_back", loopLength, counter);

	return 0;
}
Constructor
Constructor
Constructor
Constructor
Constructor
Constructor
Constructor
Constructor
Constructor
Constructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
push_back은 10번의 루프에서 총 10번의 함수를 호출했습니다

clear 함수는 vector 의 요소를 모두 제거한다. 로그를 보면 알 듯이 소멸자만 호출된다. 다른 멤버 변수를 가지고 있다면 해당 소멸자들도 불리기 때문에, 호출 수가 비례하여 증가하게 된다. vec.size() 만 줄어들고 늘어난 vec.capacity() 는 줄지 않는다는 것을 기억하자.

iterator erase(iterator pos);

erase 는 vector 의 요소를 지워주는 함수이며, 위치를 가리키는 iterator 를 인자로 넘겨주어야 한다. erase 함수의 결과를 출력하기 위해 따로 함수를 정의해주자.

void printErase(int a, const char* str, int b, int c)
{
	std::cout
		<< a
		<< "번의 "
		<< str
		<< " 호출은 "
		<< b
		<< "개의 요소를 가진 vector 에서 총 "
		<< c
		<< "번의 함수를 호출했습니다"
		<< std::endl;
}
int main()
{
	std::vector<T> vec;
	int loopLength = 10;
	for (int i = 0; i < loopLength; i++)
	{
		vec.push_back({});
	}

	counter = 0;
	vec.erase(vec.begin() + 1);
	printErase(1, "erase", loopLength, counter);

	return 0;
}
1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 9번의 함수를 호출했습니다

erase 를 단 한번만 했는데도 9번의 함수가 호출된다.

Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
~Destructor

벡터에 10개의 원소가 있을 때, 1번 원소를 지우게 되면 2번~9번 원소가 앞으로 한칸씩 옮겨지므로 총 8번의 Move Assignment 가 호출되고, 마지막 요소는 중복되므로 pop_back 을 통해 소멸자가 호출되어 파괴된다.

1번의 erase 호출은 100개의 요소를 가진 vector 에서 총 99번의 함수를 호출했습니다
1번의 erase 호출은 1000개의 요소를 가진 vector 에서 총 999번의 함수를 호출했습니다
1번의 erase 호출은 10000개의 요소를 가진 vector 에서 총 9999번의 함수를 호출했습니다
1번의 erase 호출은 100000개의 요소를 가진 vector 에서 총 99999번의 함수를 호출했습니다
1번의 erase 호출은 1000000개의 요소를 가진 vector 에서 총 999999번의 함수를 호출했습니다

원소의 갯수가 늘어나면 늘어날 수록, 엄청난 수의 Move Assignment 호출이 일어나게 되는 것이다. 최대한 뒤쪽의 원소를 삭제하자.

iterator erase(iterator first, iterator last);

first 원소부터 last - 1 까지 삭제된다.

int main()
{
	std::vector<T> vec;
	int loopLength = 10;
	for (int i = 0; i < loopLength; i++)
	{
		vec.push_back({});
	}

	letsPrint = true;
	counter = 0;
	vec.erase(vec.begin() + 1, vec.begin() + 3);
	printErase(1, "erase", loopLength, counter);

	return 0;
}

벡터의 2, 3번째 원소를 삭제해보자. [last, end) 구간의 원소가 앞으로 당겨지고, 벡터의 크기를 (원래 크기 - 제거한 원소 수) 만큼 줄인다. 이동 후 필요 없어진 마지막 두 개의 원소는 pop_back() 을 통해 소멸된다.

Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
~Destructor
~Destructor

1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 9번의 함수를 호출했습니다

결론적으로 한개의 iterator 를 넘기든, 두개의 iterator 를 넘기든 동일한 양의 함수 호출이 발생한다.

void pop_back();

1번의 pop_back() 호출은 1000000개의 요소를 가진 vector 에서 총 1번의 함수를 호출했습니다

마지막 요소를 삭제할 때 어떠한 원소도 움직일 필요가 없으므로, 단 1번의 소멸자 호출만이 발생한다.

std::iter_swap(index1, index2);

<algorithm> 안에 포함되어 있는 함수이다. erase() 함수를 사용하면 나머지 객체가 왼쪽으로 shift 되어야 하므로, 이를 피하기 위해 지우고자 하는 원소와 마지막 원소를 swap 한 후, pop_back 하면 된다. 이를 해주는 것이 iter_swap 함수이다.

#include <algorithm>

int main()
{
	std::vector<int> vec {1,2,3,4};
	std::iter_swap(vec.begin() + 1, vec.end() - 1);
	for (const auto& it : vec)
	{
		std::cout << it << " "; // 1 4 3 2
	}

	return 0;
}

1번 인덱스와 3번 인덱스가 swap 되어 1 4 3 2 가 출력된다. 여기서 pop_back 을 해주면, 1 4 3 이 된다. 여기서 알 수 있는 것은, iter_swap 후 pop_back 은 vector 원소들의 순서를 바꾼다는 것이다. 따라서 vector 를 정렬할 필요가 없거나, 당장 정렬할 필요가 없을 때 사용하는 것이 좋다.

- 컬렉션 아티클