C++ STL关联式容器

C++ STL关联式容器教程

STL 中的关联式容器主要包括 map、multimap、set 以及 multiset。和 序列式容器 不同的是，关联式容器在存储元素时还会为每个元素在配备一个键，整体以键值对的方式存储到容器中。

相比序列式容器，关联式容器可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。相比其它类型容器，关联式容器查找、访问、插入和删除指定元素的效率更高。

STL关联式容器详解

说明

关联式类容器在存储元素值的同时，还会为各元素额外再配备一个值（又称为 “键”，其本质也是一个 C++ 基础数据类型或自定义类型的元素），它的功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。

弃用序列式容器，转而选用关联式容器存储元素，往往就是看中了关联式容器可以快速查找、读取或者删除所存储的元素，同时该类型容器插入元素的效率也比序列式容器高。

也就是说，使用关联式容器存储的元素，都是一个一个的 “键值对”（ <key,value> ），这是和序列式容器最大的不同。除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。

注意，关联式容器所具备的这些特性，归咎于 STL 标准库在实现该类型容器时，底层选用了 “红黑树” 这种数据结构来组织和存储各个键值对。

分类

关联式容器名称	特点
map	定义在 <map> 头文件中，使用该容器存储的数据，其各个元素的键必须是唯一的（即不能重复），该容器会根据各元素键的大小，默认进行升序排序（调用 std::less<T>）。
set	定义在 <set> 头文件中，使用该容器存储的数据，各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。该容器会自动根据各个元素的键（其实也就是元素值）的大小进行升序排序（调用 std::less<T>）。
multimap	定义在 <map> 头文件中，和 map 容器唯一的不同在于，multimap 容器中存储元素的键可以重复。
multiset	定义在 <set> 头文件中，和 set 容器唯一的不同在于，multiset 容器中存储元素的值可以重复（一旦值重复，则意味着键也是重复的）。

技术细节

除此之外，C++ 11 还新增了 4 种哈希容器，即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说，它们也属于关联式容器，但由于哈希容器底层采用的是哈希表，而不是红黑树。

案例

关联式容器使用

使用 map 关联式容器

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
    cout << "嗨客网(www.haicoder.net)\n" << endl;
    map<string, string> mymap;
    mymap["name"] = "haicoder";
    mymap["url"] = "www.haicoder.net";
    mymap["age"] = "110";
    for (map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    {
        cout << it->first << " => " << it->second << '\n';
    }
}

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

我们定义了一个关联式容器 map，并存入了三个元素，接着，我们使用迭代器访问了其中的所有元素。

C++ STL关联式容器总结

STL 中的关联式容器主要包括 map、 multimap、set 以及 multiset。和序列式容器不同的是，关联式容器在存储元素时还会为每个元素在配备一个键，整体以键值对的方式存储到容器中。