关联性容器

关联容器是指C++标准模板库中的一套类模板，实现了有序关联数组。可用于存放任意数据类型的元素。C++标准中定义的关联容器有： set, map, multiset, multimap。

关联容器类似于C++中的无序关联容器。差别为：
*关联容器是红黑树实现，无序关联容器是哈希表实现。
*关联容器保证按键值有序遍历，因此可以做范围查找，而无序关联容器不可以。关联支持一些导航类的操作，如求出给定键最邻近的键，最大键、最小键操作。
*关联容器的迭代器不会失效，除非所指元素被删除。无序关联容器的iterator在修改元素时可能会失效。所以对关联容器的遍历与修改在一定程度上可并行
*哈希表查找时候要算hash，这个最坏时间复杂度是O(key的长度)；基于比较的有序关联容器通常只使用头几个字符进行比较

成员函数
用法
下述例子展示如何用map计数word的次数。用word为键值，次数为值。

#include
#include
#include

int main()
{
std::map wordcounts;
std::string s;

while (std::cin >> s && s != "end")
++wordcounts[s];

while (std::cin >> s && s != "end")
std::cout
执行时，用户线输入一系列word，最后以"end"结束输入。然后输入word可查询它出现的次数。

下例展示用insert函数、find函数：

#include
#include
#include // make_pair

int main()
{
typedef std::map MapType;
MapType my_map;

// insert elements using insert function
my_map.insert(std::pair('a', 1));
my_map.insert(std::pair('b', 2));
my_map.insert(std::pair('c', 3));
my_map.insert(MapType::value_type('d', 4)); // all standard containers provide this typedef
my_map.insert(std::make_pair('e', 5)); // can also use the utility function make_pair
my_map.insert({'f', 6}); // using C++11 initializer list

//map keys are sorted automatically from lower to higher.
//So, my_map.begin() points to the lowest key value not the key which was inserted first.
MapType::iterator iter = my_map.begin();

// erase the first element using the erase function
my_map.erase(iter);

// output the size of the map
std::cout > c;

// find will return an iterator to the matching element if it is found
// or to the end of the map if the key is not found
iter = my_map.find(c);
if (iter != my_map.end() )
std::cout second
迭代器
map::iterator it; // declares a map iterator
it->first; // the key value
it->second; // the mapped value
(*it); // the "element value", which is of type: pair

#include
#include
#include

int main()
{
std::map data{
{ "Bobs score", 10 },
{ "Martys score", 15 },
{ "Mehmets score", 34 },
{ "Rockys score", 22 },
{ "Rockys score", 23 } /overwrites the 22 as keys are identical /
};

// Iterate over the map and print out all key/value pairs.
for (const auto& element : data)
{
std::cout

参见
*容器_(数据类型)
*标准模板库
参考文献