[c++] vector

 벡터는 표준 C의 배열과 유사한데 항목들은 연속된 메모리에 저장되며 자신만의 슬롯을 할당받습니다. 

 벡터는 인덱스로 접근 할 수 있습니다. 특이사항으로 런타임 시간에 자신의 크기를 동적으로 커질 수 있다는 점입니다.

 벡터에 대한 레퍼런스 내용을 정리한 사이트입니다.  일부분만 번역이 되어 있어서 영어로 된 버전을 보시는 것을 

 추천 드립니다. 

https://en.cppreference.com/w/cpp/container/vector

https://ko.cppreference.com/w/cpp/container/vector

std::vector - cppreference.com

Vector의 성능

 위의 글에도 나왔지만 다시 한번 정리해서 올립니다.

 임의 요소에 접근 속도 = 상수시간 O(1) 

 마지막 요소에 대한 삽입/삭제 = 분할 상환 상수 시간 대체로 O(1) (재할당이 발생할 수 있기 때문)

 특정 위치에 대한 삽입/삭제 = 마지막 요소와 특정 위치 거리에 비례하는 O(n)

 (특정위치요소부터 마지막 요소 인덱스를 +1 시켜야 함, 연속된 메모리이기 때문에 빠르긴 함)

Vector의 재할당 방식

 vector의 재할당을 방식이 어떻게 진행되는지 직접 확인해봅시다.

#include <vector>
using namespace std;
int main()
{
	std::vector<int> int_vector;	
	cout << "[start] capacity = " << int_vector.capacity() << endl;

	size_t current_capacity = int_vector.capacity();

	for (int i = 0; i < 100; i++)
	{
		int_vector.push_back(1);
		if (current_capacity != int_vector.capacity())
		{
			current_capacity = int_vector.capacity();
			cout << "capacity = " << int_vector.capacity() << " size = " << int_vector.size() << " pointer = " <<&int_vector[0] <<  endl;
		}
	}

	return 0;
}

 

결  과

 초기의 capacity값은 0으로 셋팅 되어 있습니다.  

 컨테이너에 데이터가 삽입될 때마다 capacity와 size를 비교해서 size가 capacity를 넘어서면 재할당이 발생합니다. 

 재할당의 공식은 현재capacity + (현재 capacity / 2) = 새로운 capacity입니다.

 재할당이 발생할 때마다 현재 capacity만큼 힙에서 할당된 연속된 메모리를 해제하고 새로운 capacity만큼의 연속된

 메모리를 힙에서 할당해서 가져온 후에 데이터를 복사합니다. 만약 데이터를 복사하는 과정에서 이동 연산자가 지원

 된다면 더욱 효율적인 작업이 가능합니다. 

reserve를 통한 메모리 공간 예약

#include <vector>
using namespace std;
int main()
{
	std::vector<int> int_vector;	
	cout << "[start] capacity = " << int_vector.capacity() << endl;

	int_vector.reserve(50);
	cout << "capacity = " << int_vector.capacity() << " reserve = 50" << endl;
	size_t current_capacity = int_vector.capacity();

	for (int i = 0; i < 100; i++)
	{
		int_vector.push_back(1);
		if (current_capacity != int_vector.capacity())
		{
			current_capacity = int_vector.capacity();
			cout << "capacity = " << int_vector.capacity() << " size = " << int_vector.size() << " pointer = " <<&int_vector[0] <<  endl;
		}
	}

	return 0;
}

reserver 50 사용 결과

 reserver() 함수를 통해서 초기값을 50으로 지정하면 capacity가 50으로 지정되고 재할당 공식을 그대로 유지되는

 상태로 재할당이 진행됩니다. 

재할당시 iterator 무효화

 벡터를 사용할 때 재 할당 시 이전에 소유하고 있던 iterator가 무효화되는 것에 주의해야 합니다. 

재할당시 iterator 무효화 1

재할당시 iterator 무효화 2

 위의 예제는 vector가 재할당 된 후 이전에 할당받은 vector의 iterator인 begin 변수가 무효화되는 것을 확인할 수

 있습니다. 이후에 밑에서 begin에 접근하게 되면 프로세스는 잘못된 접근으로 인해서 종료됩니다.

 특히 멀티 스레드 환경에 vector에 접근할 때 주의 해야 합니다.

Vector의 push_back, emplace_back의  차이

 c++ 11에서 emplace_back이라는 함수가 추가되었습니다. 아래의 예제를 통해서 기존의 push_back과 어떻게 다른지

 확인해 보겠습니다.

class Object
{
public:
	Object(int v) : value(v) 
	{
		cout << "Construct Object" << endl;
	}
	virtual ~Object() 
	{
		cout << "Destruct Object" << endl;
	}

	Object(const Object & o) : value(o.GetValue())
	{
		cout << "Copy Object" << endl;
	}
	Object(const Object && o) : value(o.GetValue())
	{
		cout << "Move Object" << endl;
	}

	int GetValue() const { return value; }
private:
	int value;
};

테스트를 확인하기 위해서 사용할 Object 클래스입니다. 

int main()
{
	std::vector<Object> obj_vector;
	Object obj(1);
	obj_vector.push_back(obj);

	return 0;
}

결 과

Vector의 push_back에 데이터를 전달하기 위해서 임시 Object객체를 생성한 후에 전달합니다. 

그러면 Object의 일반 생성자 1번, 복사 생성자 1번, 소멸자 2회가 호출됩니다. 

int main()
{
	std::vector<Object> obj_vector;
	obj_vector.push_back(Object(1));

	return 0;
}

결 과

Vector의 push_back에 직접 임시 객체를 전달하는 방식으로 호출합니다. 

그러면 Object의 일반 생성자 1번, 이동 생성자 1번, 소멸자 2회가 호출됩니다. 

이렇듯 push_back을 사용하기 위해서는 Vector의 인자 객체의 임시 객체가 필요합니다.

int main()
{
	std::vector<Object> obj_vector;
	obj_vector.emplace_back(1);

	return 0;
}

결 과

emplace_back을 사용하면 일반 생성자 1회와 소멸자 1회 호출로 데이터 삽입이 완료됩니다. 

임시 객체가 생성되지 않습니다. 그 이유는 emplace_back은 Vector의 인자 객체의 생성자 파라미터를 전달받아서 

Vector 내부에서 객체를 생성해서 삽입을 진행하기 때문에 더욱 효율적입니다.

예제에서는 Object 클래스의 인자 값인 int v를 전달받고 있습니다. 

Vector의 shrink_to_fit

 c++ 11에 shrink_to_fit 함수가 추가되었습니다.

int main()
{
	std::vector<int> int_vector;
	int_vector.reserve(100);
	for(int i = 0; i < 20; i++)
		int_vector.push_back(1);

	cout << "capacity = " << int_vector.capacity() << " size = " << int_vector.size() <<" &int_vector[0] = " << &int_vector[0] << endl;
	int_vector.shrink_to_fit();
	cout << "run shrink_to_fit()" << endl;
	cout << "capacity = " << int_vector.capacity() << " size = " << int_vector.size() << " &int_vector[0] = " << &int_vector[0] << endl;

	return 0;
}

결 과

shrink_to_fit를 호출하면 추가적으로 할당된 메모리를 반환하고 실제 벡터의 사이즈의 크기만큼만 메모리를

할당하도록 합니다. 예제의 메모리를 보면 이 작업 시 재할당이 발생된다는 것을 확인할 수 있습니다.

예제에서는 할당된 메모리가 100이고 실제 사용량이 20인 벡터에서 shrink_to_fit() 함수 호출 후에

할당된 메모리가 20으로 변경되었고 80이 시스템에 반환된 것을 확인할 수 있습니다.

하지만 프로젝트에서 실제로 사용될 가능성은 낮을 듯합니다.