一、unordered 系列关联式容器
在 C++98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 log₂N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在 C++11 中，STL 又提供了 4 个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
1.1 unordered_map
1.2 unordered_map 的文档介绍
- unordered_map 是存储<key, value>键值对的关联式容器，其允许通过 keys 快速的索引到与其对应的 value。
- 在 unordered_map 中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
- 在内部，unordered_map 没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到 key 所对应的 value，unordered_map 将相同哈希值的键值对放在相同的桶中。
- unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_maps 实现了直接访问操作符 (operator[])，它允许使用 key 作为参数直接访问 value。
- 它的迭代器至少是前向迭代器。
1.3 unordered_map 的使用
unordered_map 成员函数
unordered_map 的使用
void test_unordered_map1() {
unordered_map<string, string> dict;
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("love", "爱"));
dict["sort"] = "排序";
dict["miss"];
dict["miss"] = "想念、错过";
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end()) {
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
int main() {
test_unordered_map1();
return 0;
}
注意：
- [] 实际调用哈希桶的插入操作，用参数 key 与 V() 构造一个默认值往底层哈希桶中插入，如果 key 不在哈希桶中，插入成功，返回 V()，插入失败，说明 key 已经在哈希桶中，将 key 对应的 value 返回。
