C++ 순차 컨테이너 (vector, deque, list)

vector<T>

타입 T를 원소로 갖는 순차 컨테이너로 현재 할당된 용량(capacity)을 초과하는 즉시 더 많은 원소를 저장할 수 있는 추가 공간이 자동으로 할당된다. 컨테이너의 끝에서 원소를 추가 또는 삭제할 때만 효율적이다.

- 용량/크기: capacity(), reserve(), size(), resize(), empty()

- 원소 접근: [], at(), front(), back()

- 원소 추가: push_back(), emplace_back(), emplace(), insert()

- 원소 삭제: clear(), pop_back(), erase()

 

 

deque<T>

타입 T의 원소들을 deque(double-ended queue)로 저장하는 컨테이너이다. 순차열의 시작이나 끝에 객체들을 효율적으로 추가하거나 삭제할 수 있다. 원소를 저장하는 방식 때문에 크기(size)와 용량이(capacity) 항상 같다.

- 용량/크기: capacity(), size(), resize(), empty()

- 원소 접근: [], at(), front(), back()

- 원소 추가: push_back(), push_front(), emplace_back(), emplace_front(), emplace(), insert()

- 원소 삭제: clear(), pop_back(), pop_front(), erase()

 

 

list<T>

타입 T 객체의 이중 연결 리스트를 구현한 컨테이너이다. vector, deque와 비교하면 순차열의 어느 위치라도 상수 시간에 원소를 삽입 또는 삭제할 수 있다는 장점이 있다. 하지만 특정 위치에 있는 원소에 바로 접근할 수 없어 처음부터 마지막 원소까지 순회해야 한다는 단점이 있다. 랜덤 엑세스 반복자를 사용할 수 없고 양방향 반복자를 사용한다. 양방향 반복자에는 정수를 더하거나 뺄 수 없으며 ++이나 --로만 수정 가능하다. 또는 iterator 헤더의 advance() 함수를 이용할 수 있다. ( ex. advance(l.begin(), 10) )

- 용량/크기: capacity(), size(), resize(), empty()

- 원소 접근: [], at(), front(), back()

- 원소 추가: push_back(), push_front(), emplace_back(), emplace_front(), emplace(), insert()

- 원소 삭제: clear(), pop_back(), pop_front(), erase(), remove()

 

---

 

초기화: vector, deque, list 모두 아래 방법으로 초기화 가능

vector<int> v (n);                      // n개의 원소를 기본값으로 초기화
vector<int> v (n, x);                   // n개의 원소를 x값으로 초기화

vector<int> v {1, 2, 3, 4, 5};          // 초기화 리스트로 초기화
vector<int> v {v2};                     // v2의 복사본
vector<int> v {v2.begin(), v2.end()};   // 반복자 범위를 지정해 초기화

** uniform initialization (C++11~): https://modoocode.com/286

 

resize(): vector, deque, list 모두 아래 방법으로 resize 가능

v.resize(n);        // size를 n으로 변경하되, 추가되는 원소는 기본값
v.resize(n, x);     // size를 n으로 변경하되, 추가되는 원소는 x값

vector<int> v {1, 2, 3};
v.resize(5);        // {1, 2, 3, 0, 0}
v.resize(7, 100);   // {1, 2, 3, 0, 0, 100, 100}
v.resize(6);        // {1, 2, 3, 0, 0, 100}

 

insert(): vector, deque, list 모두 아래 방법으로 insert 가능

// 반복자 p가 가리키는 원소 앞에
v.insert(p, x);                             // x 삽입
v.insert(p, n, x);                          // n개의 x 삽입
v.insert(p, b, e);                          // 반복자 범위 [b, e)를 삽입

vector<int> v = {1, 2, 3};                  // {1, 2, 3}
v.insert(++v.begin(), 100);                 // {1, 100, 2, 3}
v.insert(++v.begin(), 2, 200);              // {1, 200, 200, 100, 2, 3}
v.insert(--v.end(), v2.begin(), v2.end());  // {1, 200, 200, 100, 2, ..., 3}

vector는 끝이 아닌 위치에 삽입하면 오버헤드가 발생한다. 삽입 위치 뒤에 있는 모든 원소는 새 원소를 위한 공간을 만들기 위해 이동해야 한다. 삽입 이후에 원소의 개수가 할당된 용량(capacity)보다 크다면 메모리도 더 할당해야 한다. deque 역시 처음이나 끝이 아닌 위치에 삽입하면 오버헤드가 발생하고 모든 반복자가 무효화된다. 그러나 list는 원소를 삽입한다고 기존 원소를 이동할 필요 없이 포인터만 바꿔주면 된다. 상수 시간에 처리할 수 있으며 반복자도 무효화되지 않는다. list에서 반복자가 무효화될 때는 해당 반복자가 가리키는 원소가 삭제되었을 때 뿐이다.

 

erase(): vector, deque, list 모두 아래 방법으로 erase 가능

v.erase(p);     // 반복자 p가 가리키는 원소를 삭제하고 그 다음 원소를 반환
v.erase(b, e);  // 반복자 범위 [b, e)의 원소를 삭제하고 그 다음 원소를 반환

vector<int> v {1, 2, 3, 4, 5};      // {1, 2, 3, 4, 5}
v.erase(++v.begin());               // {1, 3, 4, 5}
v.erase(++v.begin(), --v.end())	    // {1, 5}

vector는 erase로 크기(size)가 변경되어도 용량(capacity)는 변경되지 않는다. list는 역시 상수 시간에 원소를 삭제할 수 있다.

 

---

algorithm 헤더의 유용한 함수

swap(), find(), copy(), sort(), reverse()

swap(Tx, Ty);       // 객체 Tx와 객체 Ty를 swap
find(b, e, x);      // 반복자 구간 [b, e)에서 x를 찾아 가리키는 반복자를 반환
copy(sb, se, db);   // src의 반복자 구간 [sb, se)를 dst의 반복자 db가 가리키는 곳부터 복사
sort(b, e);         // 반복자 구간 [b, e)를 기본 오름차순으로 정렬
sort(b, e, comp);   // 반복자 구간 [b, e)를 comp에 따라 정렬 (comp가 greater<>()일 경우 내림차순 정렬)
reverse(b, e);      // 반복자 구간 [b, e)의 순서를 뒤바꿈

** remove 추가: http://egloos.zum.com/h2ostudio/v/4343561

remove는 어떤 값을 가지는 원소를 삭제해주지만, 진짜로 삭제하진 않는다.

 

list의 sort()

sort()는 랜덤 엑세스 반복자가 필요하므로 list에는 사용할 수 없다. 대신 list 템플릿에 sort() 함수가 별도로 정의되어 있다. 두 버전이 있는데 인수가 없는 버전은 원소를 오름차순으로 정렬하며, 인수가 있는 버전은 비교를 위한 람다 표현식이나 함수 객체를 인수로 받는다.

l.sort()
l.sort(greater<>());

 

 

---

Reference: C++14 STL 철저 입문