1. 关联容器简介：
STL标准模板库（Standard Template Library）是惠普实验室开发的一系列软件的统称。
STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）、iterator（迭代器）。
容器类可分为：序列式容器（sequence containers）、关联式容器（associative containers）。
序列式容器 包括：
vector、list、deque、stack、queue、heap、priority_queue、slist 等；
关联式容器 包括：
set、map、multiset、multimap、unordered_set、unordered_map 等。
2. map：
2.1 关联式容器map的定义：
==> 关联容器 和 顺序容器 有着根本的不同：
关联容器中的元素是按 关键字 来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的 位置 来顺序保存和访问的。
虽然关联容器的很多行为与顺序容器相同，但其不同之处反映了关键字的作用。
==> 关联容器支持高效的关键字查找和访问：
两个主要的关联容器：map， set。
map中的元素是一些 “key-value” 键值对，关键字起到索引的作用，值则表示与索引相关的数据。
set中每个元素只包含一个关键字，set支持高效的关键字查询操作，即检查一个关键字是否在set中。
==> 标准库提供8个关联容器：
有序集合：（按关键字有序保存元素）
map, set, multimap, multiset
无序集合：
unordered_map, unordered_set, unodered_multimap, unordered_multiset
==> 应用场景举例：
map： 可以将一个人的名字作为关键字，将其电话号码作为值；
set： 银行可以定义一个名为bad_checks的set来保存那些曾经开过空头支票的人的名字。
==> 定义关联容器：
map<string, size_t> word_count;
set<string> exclude;
==> 初始化：
map<string, string> authors = {
{
"Joyce", "James"}, {
"Austen", "Jane"}, {
"Dickens", "Charles"} };
2.2 关联容器map的操作：
关联容器不支持顺序容器的位置相关的操作，例如 push_back(), push_front() 等，因为关联容器中的元素都是根据关键字存储的，这些位置操作对关联容器没有意义。
==> pair<> 类型：
map中的元素类型是pair。
pair<string, string> anon;
pair<string, size_t> word_count;
pair<string, vector<int>> line;
pair支持的操作：
pair<T1, T2> p; //默认构造
pair<T1, T2> p(v1, v2);
pair<T1, T2> p = {
v1, v2};
pair<T1, T2> p = make_pair(v1, v2);
p.first; //返回pair中的first成员
p.second; //返回pair中的second成员
p1 == p2;
p1 != p2;
==> map的使用举例：
class CBaseSocket;
typedef unordered_map<fd, CBaseSocket*> SocketMap;
SocketMap g_socket_map;
//1. map.insert(): 插入
void AddBaseSocket(CBaseSocket *pSocket) {
g_socket_map.insert( make_pair((int)pSocket->GetSocket(), pSocket) );
}
//2. map.erase(): 删除
void RemoveBaseSocket(CBaseSocket *pSocket) {
g_socket_map.erase((int)pSocket->GetSocket());
}
//3. map.find(): 查找
CBaseSocket* FindBaseSocket(int fd) {
//通过key查找map中对应元素的value
CBaseSocket *pSocket = nullptr;
SocketMap::iterator iter = g_socket_map.find(fd);
if(iter != g_socket_map.end()) {
pSocket = iter->second;
pSocket->AddRef();
}
return pSocket;
}
//map.find(key); 返回一个迭代器，指向第一个关键字为key的元素
//若key不在容器中，则返回尾后迭代器
关于map，只需记住一个使用原则：
map<> 的数据类型是pair<>，pair<>访问的方法是通过first和second。
在使用脚标的方式访问map元素中，map可以使用关键字直
2.3 map 与 unordered_map 的区别：
map 中的元素是按照key有序存储，其底层数据结构是 红黑树 ，查找、插入、删除的 时间复杂度均为 O(logN)；
unordered_map 中的元素是无序存储的，其底层数据结构是 hashtable + list/rbtree， 查找、插入、删除的 时间复杂度均为 O(1)。
map 与 unorded_map 的时间复杂度比较：（rbtree与hashtable）
map的优点在于有序，缺点在于为了保证顺序存储，在插入、删除时都需要对红黑树进行维护，所以插入、删除、查找的时间复杂度都是O(logN)；
当不需要保证顺序存储时，可使用 unordered_map，效率更高，插入、删除、查找的时间复杂度为O(1)。
unordered_map是C++11中对hash_map的官方实现，其底层数据结构为 hashtable+list/rbtree，hashtable可以看做是一个数组，通过哈希函数计算后将元素存储在hashtable中，使用list解决哈希碰撞。当同一list中的结点个数超过8个时，自动改为使用rbtree存储。
所以unordered_map在理想情况下各种操作的时间复杂度为O(1)，当发生哈希碰撞时，时间复杂度将有所退化。
3. set：
set所支持的操作：
==> Member functions:
(constructor)
(destructor)
operator=
==> Iterators:
begin();
end();
cbegin();
cend();
==> Capacity:
empty();
size();
max_size();
==> Modifiers:
insert();
erase();
swap();
clear();
emplace();
emplace_hint();
==> Operations:
find();
count();
lower_bound();
upper_bound();
equal_range();
转载：https://blog.csdn.net/ArtAndLife/article/details/116673530