[C++] std::vector

std::array 자주 사용되는 자료 구조이지만, 주요 단점이 몇 가지 존재한다.

1. 배열의 크기는 컴파일 시간에 결정되는 상수이다. 즉, 프로그램 실행 중에 변경할 수 없다.
2. 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다.
3. std::array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용한다.

---

std::vector - 가변 크기 배열

vector는 C 스타일 배열 또는 std::array가 가지고 있는 가장 두드러지는 문제 중 하나인 '고정 크기' 문제를 해결한다. std::vector는 초기화 과정에 데이터의 크기를 제공하지 않아도 된다.

다음은 벡터를 초기화하는 몇 가지 방법이다.

// 크기가 0인 벡터 선언  
std::vector<int> vec;  
  
// 지정한 초깃값으로 이뤄진 크기가 5인 벡터 선언  
std::vector<int> vec1 = {1, 2, 3, 4, 5};  
  
// 크기가 10인 vector 선언  
std::vector<int> vec2(10);  
  
// 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언  
std::vector<int> vec3(10, 5);

 

벡터에 새로운 원소를 추가하려면 push_back( ) 또는 insert( ) 함수를 사용한다. push_back( ) 함수는 벡터의 맨 마지막에 새로운 원소를 추가한다.

• insert( ) 함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있다.
  • 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하다. O(n)의 시간이 걸린다.
• push_back( ) 은 벡터에서 자주 사용되는 연산이며, 매우 빠르게 동작한다.
  • 맨 뒤에 원소를 삽입할 때: 뒤쪽에 남아 있는 공간이 있다면 O(1)의 시간이 걸린다.
  • 공간이 충분하지 않다면 모든 원소를 다 복사/이동해야 하며, 이때는 O(n)의 시간이 걸린다.

std::vector<int> vec;  
  
vec.push_back(1);  
  
vec.push_back(4);  
  
vec.insert(vec.begin(), 0);

 

그러나 push_back( ) 과 insert( ) 함수는 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점이다.

 

이러한 단점은 새로운 원소가 추가될 위치에 해당 원소를 생성하는 방식으로 최적화할 수 있으며, 이러한 기능이 emplace_back( ) 또는 emplace( ) 함수에 구현되어 있다.

 

또한 맨 마지막 원소를 제거하는 pop_back( ) 함수와 지정한 index의 원소를 제거하는 erase( ) 함수가 존재하며, 그 밖에 clear( )와 벡터가 사용할 용량을 지정하는 reserve(capacity), 여분의 메모리 공간을 해제하는 shrink_to_fit( ) 함수를 주로 사용한다.

---

std::vector 할당자

std::vector는 템플릿 매개변수에 데이터 타입 다음에 할당자를 전달할 수 있다.

 

사용자 정의 할당자를 사용하려면, 정해진 인터페이스를 따라야 한다.

 

벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocate( ), deallocate( ), construct( ), destroy( ) 등의 함수를 제공해야 한다.

 

할당자는 메모리 할당과 해제, 그리고 여타 동작에서 데이터를 손상시키지 않도록 주의해야 한다.

 

즉, 일반적인 힙 메모리 대신 자체적인 메모리 풀 또는 이와 유사한 자원을 사용하거나 자동 메모리 관리가 필요한 응용 프로그램을 만들어야 하는 경우에 사용자 정의 할당자를 사용하면 유용하다.