☑️ 더 자세히 추가 학습 필요

Sequence Containers

순차적으로 저장하는 자료구조

• 구현 단순
• 가벼움
• 속도가 빠름
• 저장할 데이터를 정렬할 필요 없는 경우

💡 vector

• push_back() : $O(1)$
• reallocation(할당된 공간이 전부 차서 배열을 통쨰로 복사해 새로운 vector에 할당) : 시간 ⬆️
• 메모리상에 연속적으로 존재

💡 deque

• reallocation : $O(1)$
  • vector와 달리 할당된 공간이 전부 차면 버퍼 하나만 할당됨
• 메모리상에 연속적으로 존재x -> 공간지역성 고려 or C배열의 라이브러리와 상호작용시 불리

💡 list

• std::list : doubly-linked list
• std::forward_list : singly-linked list

---

Associative Containers

데이터를 정렬된 상태로 유지하는 자료구조

• Red-Black Tree 기반 -> 데이터의 추가/삭제/접근의 시간복잡도가 O(logn)
• 연산에 붙는 상수가 큼 & 메모리 차지가 큼 주의

💡 std::set

• set : 데이터 자체를 key로 사용
• std::map : (key, value) 쌍을 받아서 사용
• key의 개수세기 / 지우기의 시간복잡도는 $O(logn)$

💡 multiset

• 원소의 중복 허용(같은 key를 여러개 저장 가능)
• 시간 복잡도 주의☑️ key의 개수세기 / 지우기의 시간복잡도는 $O(logn + (같은 key를 가지는 데이터의 개수))$

---

Unordered Associative Containers

💡std::unordered_set (std::unordered_map)

• Data를 중복 없이 저장, 순서가 상관없을 때
• Associative Container 대신 사용 가능

std::unordered_map의 저장 방식

• 데이터를 여러개의 버킷에 나눠서 저장
  • 저장될 버킷 = {주어진 key의 해시값} % {버킷 개수}
    -> 이때 다른 key여도 같은 버킷에 들어갈 수 있다 = 해시 충돌
• 해시 충돌에 대응하기 위해 각 버킷마다 linked list로 (key, value) 쌍을 저장

• 시간 복잡도 : O(n)
  ∵ 해시값이 고르지 않게 분포하여 하나의 버킷에 모든 데이터가 삽입된 경우 데이터를 추가/삭제/접근하기 위해 linked list를 순회
  
• hash function : std::hash (primitive 타입, string 지원)

💡 std::unordered_multiset (`std::unordered_multimap)

---

Container Adaptors

• std library에 실제로 구현되어 있지 않음
• Sequence Container를 건네주면 그것을 자기 용도에 맞춰서 사용할 수 있도록 인터페이스만 제공합니다.

💡 std::stack, std::queue

• deque 컨테이너를 이용하여 저장
  ex) queue의 정의 : template<class T,class Container = std::deque> class queue;

💡 std::priority_queue

• Container를 max heap으로 유지
• 데이터가 완벽히 정렬된 상태는 아니지만 최댓값은 빠르게 찾을 수 있음
• 연속적으로 데이터의 최댓값 또는 최솟값만 필요할 때는 상수가 큰 std::set보다 훨씬 효율적으로 동작