C++ STL

Sequence Containers

• Sequence Containers는 데이터를 순차적으로 저장하는 자료구조입니다. 구현이 단순하므로 가볍고 빠릅니다. 여러분이 저장할 데이터가 정렬 상태를 계속 유지할 필요가 없다면 좋은 선택입니다.

1. vector

• 메모리상에서 데이터가 연속적으로 위치하는 배열

2. deque

• Container 앞, 뒤에 데이터를 빠르게 넣고 뺄 수 있는 double-ended queue입니다.

3. list

• linked list입니다. Container의 어느 위치든 O(1)에 데이터를 삽입하거나 삭제할 수 있지만 random access(Container의 i번째 데이터에 O(1)에 접근)은 불가능합니다.

Associative Containers

• 데이터를 정렬된 상태로 유지하는 자료구조입니다. Red-Black Tree를 기반으로 하고 데이터의 추가/삭제/접근의 시간복잡도가 O(logN)입니다. 데이터를 정렬된 상태로 유지하는 것은 매우 강력한 기능이고 O(logN)은 적은 시간복잡도지만 연산에 붙는 상수가 크고 사용하는 메모리가 많으므로 주의가 필요합니다.

1. map, set

• Red-Black Tree는 Binary Search Tree이므로 어떤 key를 기준으로 데이터를 저장합니다. set은 데이터를 자체를 key로 사용하고, map은 (key, value) 쌍을 받아서 사용합니다.
• 단순히 데이터를 정렬 상태로 유지하고 싶다면 set을, (key, value) 데이터 쌍을 key를 기준으로 정렬하고 싶다면 map을 사용하면 됩니다.

2. multiset

• 원소의 중복을 허용합니다. 같은 key를 여러 개 저장하고 싶을 때 사용합니다. 단, 시간복잡도 주의가 필요합니다. set에서 key의 개수를 세거나, key를 지우는 함수는 모두 O(logN)이지만, multiset에서는 같은 key를 모두 세고, 모두 지우므로 O(logN + (같은 key를 가지는 데이터의 개수)) 만큼의 시간이 듭니다.

Unordered Associative Containers

• 해시값을 사용해 데이터를 저장하는 자료구조입니다. 대부분의 경우에서 데이터의 추가/삭제/접근이 O(1)이므로 Associated Container보다 효율적입니다. 하지만 데이터를 정렬된 상태로 유지해야 하거나 해시 충돌이 걱정되는 상황이라면 Associated Container를 사용하는 게 좋습니다.

1. unordered_set, unordered_map

• Data를 중복 없이 저장하고 싶고, Data의 순서가 상관 없을 때 Associateve Container 대신 사용할 수 있습니다.

2. unordered_multiset, unordered_multimap

• Associateve Container 때와 마찬가지로, 같은 key를 가진 데이터를 중복으로 가져야 할 때 사용됩니다.

Container Adaptors

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

1. stack, queue

• LIFO (Last-In, First-Out) 자료구조인 stack과 FIFO (First-In, First-Out) 자료구조인 queue의 기능을 제공합니다.

2. priority_queue

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