unordered 系列关联式容器
在 C++98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g N logN logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。
最好的查询是，进行很少的比较次数就能够将元素找到，因此在 C++11 中，STL 又提供了 4 个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
本文中只对 unordered_map 和 unordered_set 进行介绍，unordered_multimap 和 unordered_multiset的用法与 multimap 和 multiset 一样，大家可以自行查看文档学习。
unordered_set 的介绍：
构造一个 unordered_set 容器对象，根据使用的构造函数版本初始化其内容，我们主要掌握 3 种方式即可：
（1）构造一个某个类型的空容器
unordered_set<int> s1; // 构造int类型的空容器
（2）拷贝构造某类型容器
unordered_set<int> us2(us1); // 拷贝构造同类型容器us1的复制品
（3）使用迭代器区间进行初始化构造
构造一个 unordered_set 对象，其中包含范围 [first,last) 中每个元素的副本。
string str("helloworld");
unordered_set<char> us3(str.begin(), str.end()); // 构造string对象某段区间的复制品
unordered_set 的成员函数主要分为：迭代器，容量操作，修改操作。
需要注意的是，对于 unordered_set 而言，它存储的数据是无序的，并且它是一个单向迭代器。
我这里只列举几个常用的，其它的可以看 文档 学习。
在 unordered_set 中插入新元素。
每个元素只有在它不等同于容器中已经存在的任何其他元素时才会被插入，也就是说 unordered_set 中的每个元素是唯一的。
代码示例
void test_unordered()
{
unordered_set<int> us1;
// 插入元素
us1.insert(4);
us1.insert(5);
us1.insert(2);
us1.insert(2);
us1.insert(1);
us1.insert(3);
us1.insert(3);
// 遍历
for (auto e : us1)
{
cout << e << " ";
}
}
可以看到当插入重复元素时，set 是去掉了的，并且没有进行排序。
在容器中搜索值为 k 的元素，如果找到它，则返回一个迭代器，否则返回 unordered_set::end（容器末端之前的元素）的迭代器。
代码示例
void test_unordered()
{
unordered_set<int> us;
// 插入元素
us.insert(4);
us.insert(5);
us.insert(2);
us.insert(2);
us.insert(1);
us.insert(3);
us.insert(3);
unordered_set<int>::iterator pos = us.find(3);
if (pos != us.end())
{
cout << "3存在" << endl;
}
}
运行结果
从 unordered_set 容器中移除单个元素或一组元素（[first,last)）。
通过调用每个元素的析构函数，这有效地减少了容器的大小。
（1）从容器中删除单个元素（搭配 find 使用）
void test_unordered()
{
unordered_set<int> us;
// 插入元素
us.insert(4);
us.insert(5);
us.insert(2);
us.insert(2);
us.insert(1);
us.insert(3);
us.insert(3);
unordered_set<int>::iterator pos = us.find(3);
if (pos != us.end())
{
us.erase(pos); // 删除元素3
cout << "删除成功" << endl;
}
else
{
cout << "删除失败" << endl;
}
// 遍历
for (auto e : us)
{
cout << e << " ";
}
}
可以看到元素 3 已经被删除了
（2）从容器中删除单个元素（直接传要删除的元素）
void test_unordered()
{
unordered_set<int> us;
// 插入元素
us.insert(4);
us.insert(5);
us.insert(2);
us.insert(2);
us.insert(1);
us.insert(3);
us.insert(3);
us.erase(5); // 删除元素5
// 遍历
for (auto e : us)
{
cout << e << " ";
}
}
可以看到 5 已经被删除
那么它和第 1 种的区别是什么呢？
erase(x)：如果 x 存在就删除；如果不存在，不做任何改变erase(pos)：如果 x 存在就删除；如果不存在，此时 pos 位置指向 set::end 的迭代器，那么程序运行就会报错。其实这种方式本质上可以理解为 erase 去调用了 迭代器 和 find。
返回 unordered_set 容器中的元素数量。
代码示例
void test_unordered()
{
unordered_set<string> us;
// 构造元素
us = { "milk", "potatoes", "eggs" };
cout << "size: " << us.size() << endl;
// 插入元素
us.insert("pineapple");
cout << "size: " << us.size() << endl;
// 插入重复元素
us.insert("milk");
cout << "size: " << us.size() << endl;
}
运行结果
返回一个 bool 值，指示 unordered_set 容器是否为空，即其大小是否为 0。
这个函数不会以任何方式修改数组的内容。
代码示例
void test_unordered()
{
// us1构造3个元素
unordered_set<string> us1 = { "milk", "potatoes", "eggs" };
// us2构造一个空容器
unordered_set<string> us2;
cout << "us1 " << (us1.empty() ? "is empty" : "is not empty") << endl;
cout << "us2 " << (us2.empty() ? "is empty" : "is not empty") << endl;
}
运行结果
unordered_set 容器中的所有元素都将被删除。
即调用它们的析构函数，并将它们从容器中移除，使容器的大小为 0。
代码示例
void test_unordered()
{
unordered_set<string> us = { "chair", "table", "lamp", "sofa" };
// 遍历
for (const string& x : us)
{
cout << x << " ";
}
cout << endl;
// 清除容器中的所有元素
us.clear();
// 再重新插入一些元素
us.insert("bed");
us.insert("wardrobe");
us.insert("nightstand");
// 遍历
for (const string& x : us)
{
cout << x << " ";
}
}
运行结果
通过 ust 的内容交换容器的内容，ust 是另一个包含相同类型元素的 unordered_set 对象。大小可能不同。
这个函数在容器之间交换指向数据的内部指针，而不实际对单个元素执行任何复制或移动，允许常量时间执行，无论大小如何。
代码示例
void test_unordered()
{
unordered_set<string> us1 = { "iron","copper","oil" };
unordered_set<string> us2 = { "wood","corn","milk" };
// 交换容器的内容
us1.swap(us2);
// 遍历us1
for (const string& x1 : us1)
{
cout << x1 << " ";
}
cout << endl;
// 遍历us2
for (const string& x2 : us2)
{
cout << x2 << " ";
}
}
运行结果
在容器中搜索值为 k 的元素，并返回找到的元素数。
因为 unordered_set 容器不允许重复值，这意味着如果容器中存在具有该值的元素，则函数实际返回 1，否则返回 0。
代码示例
void test_unordered()
{
unordered_set<string> us = { "hat", "umbrella", "suit" };
// 容器中值为"hat"的元素个数
cout << us.count("hat") << endl;
// 容器中值为"red"的元素个数
cout << us.count("red") << endl;
}
运行结果
unordered_set 当中迭代器相关函数如下：
注意：set 是双向迭代器，而 unordered_set 是单向迭代器
unordered_multiset 的介绍：
注意，这个容器不是在它自己的头文件中定义的，而是与 unordered_set 共享头文件 <unordered_set>。
unordered_multise 容器与 unordered_set 容器的底层数据结构是一样的，都是哈希表。
其次，它们所提供的成员函数的接口都是基本一致的，这两种容器唯一的区别就是，unordered_multiset 容器允许键值冗余，即 unordered_multiset 容器当中存储的元素是可以重复的。
代码示例
void test_unordered()
{
unordered_multiset<int> ums;
// 插入元素
ums.insert(4);
ums.insert(5);
ums.insert(2);
ums.insert(2);
ums.insert(1);
ums.insert(3);
ums.insert(3);
// 遍历
for (auto e : ums)
{
cout << e << " ";
}
}
可以看到是存在多个相同元素的。
另外，它和 unordered_set 容器所提供的成员函数的接口都是基本一致的，所以就不全部列举了，只列举几个稍微有点小差别的函数接口。
在容器中搜索以 k 为键的元素，如果找到它，则返回第一个迭代器，否则返回 unordered_multiset::end（容器末尾以上的元素）的迭代器。
代码示例
void test_unordered()
{
unordered_multiset<int> ums;
ums.insert(4);
ums.insert(5);
ums.insert(6);
ums.insert(2);
ums.insert(2);
ums.insert(1);
ums.insert(3);
ums.insert(3);
// 遍历
for (auto e : ums)
{
cout << e << " ";
}
cout << endl;
// 容器中存在多个2，那么返回第一个2位置的迭代器
auto pos = ums.find(2);
// 打印2位置后面的所有元素（验证pos是否为第一个2位置的迭代器）
while (pos != ums.end())
{
cout << *pos << " ";
++pos;
}
}
可以看到确实是从第一个 2 开始打印的
在容器中搜索值为 k 的元素，并返回找到的元素个数。
代码示例
void test_unordered()
{
unordered_multiset<int> ums;
// 插入元素
ums.insert(4);
ums.insert(5);
ums.insert(2);
ums.insert(2);
ums.insert(2);
ums.insert(2);
ums.insert(1);
ums.insert(3);
ums.insert(3);
// 统计2的个数
cout << ums.count(2) << endl;
// 遍历
for (auto e : ums)
{
cout << e << " ";
}
}
运行结果
因为 unordered_multiset 容器允许键值冗余，从上面示例中可以看到，该成员函数 find 和 count 的意义与 unordered_set 容器中的是不同的。