C++ STL 종류

복잡도 : amortized O(1)

원래는 배열 내 원소를 찾는 과정이 (인덱스가 있으므로) O(1) 에 끝난다. 하지만 vector 의 경우 (C 에서 공간을 미리 받아뒀다가 꽉 차면 realloc 하는 것 처럼) 미리 받은 공간이 꽉 차면 다시 할당하고 복사하는 과정이 드물게 일어난다. 복사는 무조건 O(n) 이므로, 드물게 O(n) 이 된다.

그러면 우리는 이 알고리즘을 O(n) 으로 봐야 할까? 대부분은 그렇지 않기 때문에 그렇게 여기면 정확한 표현이 안된다. 따라서 ‘가끔 얘가 딴짓하느라 (O(n)) 좀 느릴 수 있어. 그 비용은 원래 행동할 때 (O(1)) 에 나눠서 (분할해서) 낸 비용이라고 생각해 보자’ 라는 뜻의 amorized 가 붙은 것이다.

여담으로, Amotized Analysis (분할 상환 분석) 이란 것도 있다. 특정 알고리즘에서 최악의 경우를 가정하고 연산을 수행시켰을 때의 평균 수행 시간을 분석한다.

Vector

  vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
    cout << *itr << endl;
  }

반복자로 erase 하면 반복자가 망가진다

for (; itr != end_itr; itr++) {
  if (*itr == 20) {
    vec.erase(itr);
  }
}

이러면 erase 이후에 for 문을 못 돌려서 run-time assertion failure 가 떨어진다.

vector<int>::iterator itr = vec.begin();

for (; itr != vec.end(); ++itr) {
  if (*itr == 20) {
    vec.erase(itr);
    itr = vec.begin();
  }
}

erase 가 작동했을 때, itr 을 다시 지정해주면 에러는 사라진다. 하지만 너무 불필요한데.. 처음으로 꼭 가야 하나?

for (vector<int>::size_type i = 0; i != vec.size(); i++) {
  if (vec[i] == 20) {
    vec.erase(vec.begin() + i);
    i--;
  }
}

그냥 itr 를 건드리지 말고, 특정 원소 위치를 직접 집어서 erase 시키면 된다. 그리고 i 값을 1 미리 빼서 다음 루프에도 원위치될 수 있도록 하면 끝.

vector<int>::size_type 타입을 썼다는 걸 눈여겨 보자. 그냥 int i 를 쓰면 왜 안되는지도 잘 생각해보자.

::const_iterator

말 그대로 이 iterator 로는 값을 바꿀 수 없다.

  vector<int>::const_iterator citr = vec.cbegin() + 2;

  // 상수 반복자가 가리키는 값은 바꿀수 없다. 불가능!
  *citr = 30;

이 때는 cbegin / cend 를 쓴다는 점을 주의. 보통은 값이 바뀌지 않을 때 iterate 를 돌리기 때문에 const_iterator 를 쓰는게 낫다.

::reverse_iterator

  cout << "역으로 vec 출력하기!" << endl;
  // itr 은 vec[2] 를 가리킨다.
  vector<int>::reverse_iterator r_iter = vec.rbegin();
  for (; r_iter != vec.rend(); r_iter++) {
    cout << *r_iter << endl;
  }

역순으로 출력한다. 이 때는 rbegin / rend 를 쓴다.

둘 조합도 물론 있다. const_reverse_iterator

Ranged-based for loop

Python 을 써봤다면 크게 어려운 개념은 아니다. 사용법만 익혀두자.

  vector<int> vec;
  vec.push_back(1);
  vec.push_back(2);
  vec.push_back(3);

  // range-based for 문
  for (int elem : vec) {
      cout << elem << endl;
  }
for (/* 원소를 받는 변수 정의 */ : /* 컨테이너 */) { }

List

Vector 는 배열과 동일시했다면, List 는 배열이 아닌 double-linked list 이다.

list 의 장점은, 특정 위치 원소 제거에 O(1) 만 소요된다는 점이다. (당연하다.)

void delete_list(dlistType * aList) {
    aList->mPrev->mNext = aList->mNext;
    aList->mNext->mPrev = aList->mPrev;
    free(aList);
}

Deque (덱)

Double ended queue 를 말한다. 앞의 두 컨테이너와 비교해 보면,

하지만 단점이 있다. 덱은 벡터처럼 연속 메모리에 있지 않다 (허미) 따라서 메모리 위치를 보관할 추가 영역이 더 필요하다. 즉, 실행 속도를 취하기 위해 메모리 영역을 더 확보하는 컨테이너다.

왜 벡터보다 빠를까? 덱은 2단계 구조로 되어 있는데,

  1. 특정 메모리 (블록) 영역을 가리키는 ‘블록 주소 테이블’
  2. 서로 동떨어진 ‘블록’ 들

여기서 특정 영역이건 맨 앞/맨 마지막이건 데이터를 추가하려 들면.. 특정 블록만 건드리거나 아예 새 블록만 할당받아버리면 그만이기 때문이다. 벡터였다면 (메모리 영역을 늘리거나 할 때만이라도) 전체 메모리 영역이 움직여야 한다.

cpp-2

그래서 어떤 걸 써야하나?

부록

C+11 에는 array 도 있다. vector 는 ‘dynamic contiguous array’ 라고 하면 array 는 ‘static -‘ 이다. 즉 사이즈가 고정되기 때문에 push_back() 같은 건 없다.