STL Container - vector

원글: https://mystes.tistory.com/121

---

주요 특징

std::vector는 STL에서 가장 인기있는 템플릿 라이브러리 중 하나입니다. 컨테이너의 앞 또는 뒤에 자유롭게 추가 및 삭제가 가능하며 인덱스를 통한 접근(랜덤 액세스) 역시 지원합니다.

 

각 요소는 연속적으로 저장되므로 반복자를 통해 요소에 액세스 할 수 있을 뿐만 아니라 요소에 대한 일반 포인터에 오프셋을 사용하여 요소에 액세스할 수도 있습니다. 즉, 벡터의 요소에 대한 포인터는 배열의 요소에 대한 포인터를 기대하는 함수에 저장될 수 있습니다.

 

벡터의 저장 공간은 자동으로 처리되며 필요에 따라 확장됩니다. 벡터는 향후 증가를 처리하기 위해 더 많은 메모리가 할당되기 때문에 일반적으로 정적 배열보다 더 많은 공간을 차지합니다. 따라서 벡터는 요소가 삽입될 때마다 재할당할 필요가 없고, 추가 메모리가 소진될 때만 재할당합니다. 할당된 메모리의 총량은 capacity 함수를 사용하여 확인할 수 있습니다.

 

재할당은 일반적으로 성능 측면에서 많은 비용을 소모하는 작업으로, 요소의 수를 미리 알고 있는 경우 reserve 함수를 사용하여 재할당을 제거할 수 있습니다.

 

기본 사용 예제

생성 및 할당

벡터의 기본 생성 및 할당은 다음과 같습니다. (주석을 통해 결과 값을 대체합니다)

std::vector<int> v1;                      // v1 : {}
std::vector<int> v2 = { 1, 2, 3, 4, 5 };  // v2 : { 1, 2, 3, 4, 5 }
std::vector<int> v3 = v2;                 // v3 : { 1, 2, 3, 4, 5 }

std::vector<int> v4(v3.begin(), v3.end());  // v4 : { 1, 2, 3, 4, 5 }
std::vector<int> v5(3, 10);                 // v5 : { 10, 10, 10 }
std::vector<int> v6(v5);                    // v6 : { 10, 10, 10 }

std::vector<int> v7(10);     // v7 : { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
std::vector<int> v8(10, 1);  // v8 : { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

std::vector<int> v9;
v9.assign(5, 2);  // v9 : { 2, 2, 2, 2, 2 }
v9.assign(v7.begin(), v7.end());  // v9 : { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

std::vector<int> v10;
v10 = { 1, 2, 3, 4, 5 };  // v10 : { 1, 2, 3, 4, 5 }

테스트 중인 환경은 C++20 버전입니다. 하위 버전에서 일부 코드가 동작하지 않을 수 있습니다.

 

추가 및 삭제

벡터에 요소를 추가 및 삭제하는 기본 코드는 다음과 같습니다.

std::vector<int> v = { 1, 2, 4, 5 };

// 벡터의 "맨 끝"에 요소를 추가합니다.
v.push_back(6);  // v : { 1, 2, 4, 5, 6 }

// 벡터의 "맨 앞"에 요소를 추가합니다.
v.insert(v.begin(), 0);  // v : { 0, 1, 2, 4, 5, 6 }

// 벡터의 "3번째 요소 다음"에 요소를 추가합니다.
v.insert(v.begin() + 3, 3);  // v : { 0, 1, 2, 3, 4, 5, 6 }

// 벡터의 "맨 끝"에 요소를 제거합니다.
v.pop_back();  // v : { 0, 1, 2, 3, 4, 5 }

// 벡터의 "맨 앞"에 요소를 제거합니다.
v.erase(v.begin());  // v : { 1, 2, 3, 4, 5 }

// 벡터의 "3번째 요소 다음" 요소를 제거합니다.
v.erase(v.begin() + 3);  // v : { 1, 2, 3, 5 }

// 벡터 모든 요소를 삭제합니다.
v.clear();  // v : { }

 

수정 및 순회

벡터의 요소를 변경하거나 순회하는 방법입니다.

std::vector<int> v = { 1, 2, 3 };

// 벡터 마지막 요소를 반환합니다.
auto n1 = v.back();  // n1 = 3

// 벡터 첫 번째 요소를 반환합니다.
auto n2 = v.front();  // n2 = 1

// 벡터의 요소를 수정합니다.
v[0]    = 10;
v.at(1) = 20;

// 벡터의 요소를 출력합니다.
for (int i = 0; i < v.size(); ++i)
  std::cout << v[i] << ' ';

// 벡터의 요소를 출력합니다.
for (auto it = v.begin(); it != v.end(); ++it)
  std::cout << *it << ' ';

// 벡터의 요소를 출력합니다.
for (auto n : v)
  std::cout << n << ' ';

// 벡터의 크기를 출력합니다.
auto n3 = v.size();  // n3 = 3

 

심화 학습

본문에서 제가 테스트 하는 환경은 ARMv8 Debian입니다. x86 계열이라고 값이 크게 차이나는 것은 아니지만 일부 퍼포먼스나 용량 수치가 변경될 수 있습니다.

push vs emplace

두 방법의 차이는 복사 생성자의 호출 유무입니다.

class Object
{
 public:
  Object() { std::cout << "Object()" << std::endl; }
  ~Object() { std::cout << "~Object()" << std::endl; }
  Object(const Object&) { std::cout << "Object(const Object&)" << std::endl; }
  Object(Object&&) { std::cout << "Object(Object&&)" << std::endl; }
};

int main()
{
  std::vector<Object> v;

  std::cout << "--- emplace_back ---" << std::endl;
  v.emplace_back();

  std::cout << "--- push_back ---" << std::endl;
  v.push_back(Object());

  std::cout << "--- release ---" << std::endl;
}

--- emplace_back ---
Object()
--- push_back ---
Object()
Object(Object&&)
Object(const Object&)
~Object()
~Object()
--- release ---
~Object()
~Object()

Object 객체를 벡터에 추가할 때, emplace_back의 경우 생성자가 1회만 호출됩니다.

그러나 push_back은 먼저 임의의 객체 인스턴스를 생성하고, 그것을 벡터로 이동합니다. 이 과정에서 복사 생성자 및 임의 객체에 대한 소멸자도 호출됩니다.

만약 객체의 생성, 소멸, 복사에 많은 리소스가 소모되는 경우 이 과정은 매우 불필요할 수 있습니다.

 

저장 공간

특징에서 설명했던 것과 같이 벡터의 저장 공간은 동적으로 할당됩니다. 최초 할당되면 일정 수치의 용량을 가지며, 요소가 추가될 때 용량이 증가하는 방식입니다.

코드를 통해 자세히 알아보겠습니다.

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v;
  auto             cap = v.capacity();

  for (int i = 1; i <= 1000; i++)
  {
    v.push_back(i);
    if (cap != v.capacity())
    {
      std::cout << v.size() << ' ' << v.capacity() << '\n';
      cap = v.capacity();
    }
  }
}

요소를 추가하며, size와 capacity가 어느 시점에 변화하는지, 출력하는 코드입니다. 주요 특징은 capacity가 지수적으로 증가한다는 것을 볼 수 있습니다.

요소의 개수가 일정 수치에 다다르면 내부적으로 Capacity를 증가시킵니다. 자세한 내용은 여기 stack overflow 답변에 자세하게 설명되어 있습니다.

하지만 중요한 점은 vector의 원소가 삭제되었다 할 지라도 늘어난 capacity는 줄어들지 않는다는 점입니다.

v.clear();
std::cout << v.capacity() << std::endl;  // 1024

물론 이것은 크게 문제가 되지 않습니다. 운영체제는 메모리를 관리하는 과정에서 일부 힙 메모리를 재사용하고, vector가 소멸되는 시점에 해당 capacity는 반환되기 때문입니다.

 

벡터의 해제

하지만 벡터가 지역변수가 아닌 전역 또는 멤버 변수로 장시간 유지되는 경우 사용되는 capacity를 반환해 주는 것이 좋습니다.

v.shrink_to_fit();

그 이유는 아래와 같습니다.

struct BigData { char a[1024 * 1024] = {}; };

std::vector<BigData> v;
for (int i = 1; i <= 1000; i++)
  v.push_back({});

v.clear();
printf("clear : %lu ... %lu\n", v.capacity(), rs::utils::resource::processMemory().physical_);

v.shrink_to_fit();
printf("shrink_to_fit : %lu ... %lu\n", v.capacity(), rs::utils::resource::processMemory().physical_);

rs::utils::resource::processMemory() 는 필자가 개발하여 사용하는 SDK로, 현재 프로세스 물리 메모리를 반환하는 함수입니다.

프로세스의 실제 메모리를 출력해보면 clear 이후 메모리가 유지되는 것을 볼 수 있습니다. 만약 벡터가 전역 변수이거나, 프로세스가 살아있는 동안 유지되는 벡터일 경우 해당 메모리는 프로그램이 종료되기 전까지 유지될 것입니다.

따라서 사용하지 않는 벡터의 경우 메모리를 반환하는 습관이 필요합니다.

 

인덱스 접근

벡터의 인덱스에 접근할 때 대표적으로 2가지 방법이 있습니다.

• at()
• operator[]

먼저 at은 [] 보다 상대적으로 빠른 퍼포먼스를 보여줍니다.

int main()
{
  std::vector<int> v = { 1, 2, 3 };

  auto start  = rs::time::tick<nanoseconds>();
  auto res_at = v.at(1);
  auto end    = rs::time::tick<nanoseconds>();
  std::cout << "at: " << (end - start) << "ns" << std::endl;  // 1568ns

  start  = rs::time::tick<nanoseconds>();
  auto res_bracket = v[1];
  end    = rs::time::tick<nanoseconds>();
  std::cout << "bracket: " << (end - start) << "ns" << std::endl;  // 128ns
}

테스트 환경에 따라 결과 값은 다르게 출력됩니다.

rs::time 모듈 역시 필자가 사용하는 개인용 SDK 함수입니다. chrono를 래핑한 함수입니다.

단순 수치만 보면 10배 이상의 퍼포먼스를 보여주지만 operator[]의 치명적인 단점은 예외 처리가 불가능하다는 것입니다.

int main()
{
  std::vector<int> v = { 1, 2, 3 };

  try {
    int res = v[9999];
    std::cout << res << std::endl; // 컴파일러에 따라 다른 쓰레기 값
  } catch (std::exception& e) {
    std::cout << e.what() << std::endl;  // 출력되지 않음
  }
}

위 코드는 v의 존재하지 않는 인덱스를 참조합니다. 그러나 예외는 발생하지 않고 0(gcc) 또는 기타 쓰레기 값(clang)을 반환합니다.

만약 operator[]가 아닌 at을 사용하는 경우 아래처럼 예외가 정상적으로 발생합니다.

vector::_M_range_check: __n (which is 9999) >= this->size() (which is 3)