這篇文章來介紹 Associative containers and Unordered associative containers。 associative containers 關心的是 element 是否屬於同一個 set，因此對於每個 associative containers 而言，find() function 是個相當關鍵且基本的 member function。「set」是 for 一般的 single data；「map」是 for key-value pair data。
Overview
我們嘗試一次來觀察所有的 associative containers，不論是 ordered, unordered，還是 single key or multiple keys，並且一起討論這些 containers 的特色和優缺點。
Associative containers Overview
| Name | Brief | Capacity | Element Access | Modifiers | Others |
|---|---|---|---|---|---|
| set | Binary Search Tree (RB-tree) | “size, empty” | “insert, erase, clear, swap” | “find, count” | |
| multiset | Binary Search Tree (RB-tree) | “size, empty” | “insert, erase, clear, swap” | “find, count” | |
| map | Binary Search Tree (RB-tree) | “size, empty” | “operator [], at” | “insert, erase, clear, swap” | “find, count” |
| multimap | Binary Search Tree (RB-tree) | “size, empty” | “insert, erase, clear, swap” | “find, count” |
Unordered associative containers Overview
| Name | Brief | Capacity | Element Access | Modifiers | Others |
|---|---|---|---|---|---|
| unordered_set | Hash Table | “size, empty” | “insert, erase, clear, swap” | “find, count” | |
| unordered_multiset | Hash Table | “size, empty” | “insert, erase, clear, swap” | “find, count” | |
| unordered_map | Hash Table | “size, empty” | “operator [], at” | “insert, erase, clear, swap” | “find, count” |
| unordered_multimap | Hash Table | “size, empty” | “insert, erase, clear, swap” | “find, count” |
Data Structure
當我們在研究一個 container 的時候，會先要知道它背後實作的 data structure，因為每個 data structure 都其特性，這樣可以幫助我們理解該 container 的優缺點和特色差異。
Associative containers Using Binary Search Tree
對於 associative containers 而言，快速找到 element 是個關鍵的部分，因此 (ordered) associative containers 採用 binary search tree，search element 的複雜度為 $log(n)$。
Unordered associative containers Using Hash Table
使用 Hash table 的好處是速度很快，find(search) time is constant。但它就不具備有 sorted data 的功能。
Element Access
你會發現只有 map and unordered_map 有直接 access element 的能力(非random access)，主要原因是：
- associative containers 是想要快速的知道該 element 是否存在該 set 中，加上背後實作的 data structures 的緣故，基本上並不支援 random access。
- map overriding operator[], at()，主要不是要 random access，而是可以根據給定的 key，找到 value。
- multimap 如果給定一個 key，有可能會回傳多個 values，因此並不支援 operator [], at()。
Modifiers
insert() 的種類
基本上分成以下四種：
- copy insertion
- move insertion
- range insertion
- initializer list insertion
詳細的實作方法請見 github source code。
erase() 的種類
基本上分成三種：
- erase by key
- erase by position
- erase by range
clear() and swap()
基本上用法都和之前一樣。
Others : find() count()
不管是 Associative containers or Unordered associative containers 用法都是一樣的，因為這就是這種 container 類型的特色和最主要使用的情境。
Comments