⭐ 이 글은 C++ STL Containers: Choose your containers wisely을 참고하여 정리한 글입니다.

---

0. Containers의 유형

• Sequence Container
  - 정렬됨. 모든 원소에 위치가 있음
  - vector, deque, list

• Associative Container
  - Key의 정렬 기준에 따라 정렬됨
  - set, multiset, map, multimap

• Unordered Associative Container
  - 요소의 위치가 중요하지 않음

  • 정렬을 하지 않기 때문에 대용량 데이터에 유리함

• Adapter Container
  - Sequential container를 사용하는 또다른 방법. (Wrapper로 싸여 있음)
  - stack, queue, priority queue

---

1. Sequence Container

원소들이 입력된 순서대로 정렬되어 있습니다.

>> std::vector

크기가 변하는 배열이라고 생각하면 됩니다. 크기가 변화하기 때문에 heap에 저장됩니다.

• random access 지원 O(1)
• 중간에 원소 삽입은 뒷부분 원소를 모두 움직여야 하니 O(n)
• vector의 size가 capacity보다 커지면 새로운 공간에 reallocate 후 이전 vector은 지움
  -> 잦은 reallocate를 방지하려면 capacity를 지정해 줄 수 있는 reserve()라는 함수를 사용.
  -> 가능하면 남은 공간을 잡아주는 함수인 shrink_to_fit()을 사용할 수 있다.
  -> but! 어쨌든 해당 size만큼 새로운 공간을 할당하고 기존 원소를 복사하므로 시간이 많이 걸림. 따라서 resize()혹은 clear()을 먼저 사용한 후 swap()이나 shrink_to_fit()을 호출해야 함

>> std::deque

double ended queue라는 뜻입니다. 양방향으로 크기를 키울 수 있습니다.

• random access 지원 O(1)
• 처음과 끝에 삽입하는 것은 O(1)에 가능
• 중간에 원소를 삽입하는 것은 O(n)
• deque는 vector과 달리 메모리 할당이 조금 더 큰 block으로 할당되기 때문에 잦은 push_back()과 push_front()에 vector보다 유리함

>> std::list

list는 doubley linked list처럼 동작합니다. 따라서 모든 원소는 그 앞, 뒤 원소의 위치를 가지고 있습니다.

• random access 지원 x
• vector과 deque와 달리 list는 각 원소에 O(1)에 접근 불가.
  -> 그 전 원소를 모두 순회해야 하므로 O(n) 소모
• 양방향 iterator을 지원하며 특정 위치에서의 insert()와 erase()는 O(1)에 가능
• 만약 단방향 순회만 필요하다면, std::forward_list가 시간,공간복잡도에 우위임

2. Associative Container

key값이 특정 정렬 기준에 따라 정렬되어 있어 key값으로 원소를 접근하는 것이 매우 용이한 것이 특징입니다.

>> std::set

set은 key없이 value들이 특정 정렬 기준에 따라 정렬되어 있습니다. 그러나 value의 중복은 불가합니다.

• random access 지원 x
• 삽입, 삭제, 찾기는 O(log n)
• 정렬되지 않은 sequence로 set을 초기화 하는 것은 정렬과 같으므로 O(n log n)
• 정렬된 sequence로 set을 초기화한다면 O(n)
• lower_bound()와 upper_bound()가 O(n)의 시간으로 동작.
  -lower_bound()와 upper_bound()는 Random Access가 가능한 Container에서는 O(log n)
  - set, multiset과 같은 경우에는 O(n)

>> std::multiset

set과 동일하지만 중복 value가 허용됩니다.

• 중복된 value의 수 만큼 count()함수에서 O(n)의 시간이 추가적으로 필요

>> std::map

key와 value의 pair로 이뤄졌습니다. key는 중복이 불가하고 특정 기준에 따라 정렬되어 있습니다.

• random access 지원 x
• multiset의 count()가 중복된 원소의 수만큼 느릴 수 있으므로 map을 사용할 수 있음
• 삽입, 삭제, 찾기는 O(log n)

>> std::multimap

map과 동일하지만 중복된 key가 가능합니다.

3. Unordered Associative Container

>> std::unordered_set

>> std::unordered_map

• 모두 Hash Table implementation이 존재
• Hash Table을 사용하므로 삽입, 검색이 O(1)(선형 충돌로 인한 최악의 경우 O(n))에 동작!
• 원소들이 정렬되어 있지 않아, 이진 검색은 사용할 수 없음
• 같은 이유로 begin()은 가장 작은 값을 가리키지 않음
• Hash 함수가 공간 대비 효율에 매우 중요하니, 좋은 Hash 함수를 사용하는 것이 중요함

4. Adapter Container

• 생성자에 특정 allocator을 전달하는 것이 가능
• emplace()를 지원하여 공간 효율을 얻을 수 있음. 추가 정보는 링크

>> std::stack

• LIFO data structure로서 끝 부분에서만 삽입, 삭제, 회수가 가능
• STL에서는 기본적으로 deque를 사용해서 구현됨
• push(), pop(), top(),empty()가 존재

>> std::queue

• FIFO data structure로서 넣은 반대 방향에서 회수가 가능
• STL에서는 기본적으로 list로 구현되었지만, deque도 가능
• push(), pop(), front(),back(),empty()가 존재

>> std::priority_queue

• 삽입한 순서에 상관없이 priority가 높은 데이터가 먼저 나옴
• Heap(완전 이진 트리)로 구현됨

---

5. Conclusion

• 특정 위치로 바로 접근(Random access)가 필요? ✅ Sequnce Container
• 원소들이 정렬되어야 한다? ✅ordered container 아니다? ✅hashed container
• 잦은 push_back()이 필요? ✅deque를 써라! (vector대신)
• 만약 메모리가 엄격히 제한되어있다면 Hash table을 쓰는 것은 힘들수도
• map을 순회해야한다면 ✅ordered_map을 써라
• 만약 크기를 고정할 수 있다면 ✅std::array가 vector보다 좋다
• 중간에 잦은 삽입과 삭제가 필요하다면 ✅list가 vector나 deque보다 좋다