关联性容器

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

关联容器类似于C++中的无序关联容器。差别为：

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

成员函数

	set	map	multiset	multimap	描述
	(constructor) （页面存档备份，存于互联网档案馆）	(constructor) （页面存档备份，存于互联网档案馆）	(constructor) （页面存档备份，存于互联网档案馆）	(constructor) （页面存档备份，存于互联网档案馆）	构造
	(destructor) （页面存档备份，存于互联网档案馆）	(destructor) （页面存档备份，存于互联网档案馆）	(destructor) （页面存档备份，存于互联网档案馆）	(destructor) （页面存档备份，存于互联网档案馆）	析构
	operator=	operator=	operator=	operator=	容器赋值
	get_allocator	get_allocator	get_allocator	get_allocator	返回分配器，用于给容器的成员分配空间
Element access	不適用	at	不適用	不適用	访问特定元素，带边界检查
	不適用	operator[]	不適用	不適用	访问特定元素，不带边界检查
Iterators	begin	begin	begin	begin	返回容器开始处的迭代器
	end	end	end	end	返回容器结束处的迭代器
	rbegin	rbegin	rbegin	rbegin	返回容器逆向开始处的逆向迭代器
	rend	rend	rend	rend	返回容器逆向结束处的逆向迭代器
Capacity	empty	empty	empty	empty	检查容器是否为空
	size	size	size	size	返回容器内元素数量
	max_size	max_size	max_size	max_size	返回容器内元素最大可能处理
Modifiers	clear	clear	clear	clear	清空容器内容
	insert	insert	insert	insert	插入元素
	emplace	emplace	emplace	emplace	原地构造元素 (C++11)
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	使用hint 原地构造元素(C++11)
	erase	erase	erase	erase	擦除元素
	swap	swap	swap	swap	与另一个容器交换内容
Lookup	count	count	count	count	返回匹配特点键值的元素数量
	find	find	find	find	搜到特定键值的元素
	equal_range	equal_range	equal_range	equal_range	返回匹配特定键值的所有元素
	lower_bound	lower_bound	lower_bound	lower_bound	返回键值不小于特定值的第一个元素的迭代器
	upper_bound	upper_bound	upper_bound	upper_bound	返回键值大于特定值的第一个元素的迭代器
Observers	key_comp	key_comp	key_comp	key_comp	返回键值比较函数
	value_comp	value_comp	value_comp	value_comp	返回值比较函数。在set与multiset，该函数 equivalent to key_comp, 因为元素只有值.

用法

下述例子展示如何用map<string, int>计数word的次数。用word为键值，次数为值。

#include <iostream>
#include <string>
#include <map>

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

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

    while (std::cin >> s && s != "end")
        std::cout << s << ' ' << wordcounts[s] << '\n';
}

执行时，用户线输入一系列word，最后以"end"结束输入。然后输入word可查询它出现的次数。

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

#include <iostream>
#include <map>
#include <utility> // make_pair

int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;

    // insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('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 << "Size of my_map: " << my_map.size() << '\n';

    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> 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 << "Value is: " << iter->second << '\n';
    else
        std::cout << "Key is not in my_map" << '\n';

    // clear the entries in the map
    my_map.clear();
}

迭代器

map<Key,T>::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<const Key,T>

#include <iostream>
#include <string>
#include <map>

int main()
{
    std::map <std::string, int> 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 << "Who(key = first): " << element.first;
        std::cout << " Score(value = second): " << element.second << '\n';
    }

    return 0;
}

参见

• 容器_(数据类型)
• 标准模板库