關聯性容器

關聯容器是指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;
}

參見

• 容器_(數據類型)
• 標準模板庫