關聯容器是指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 返回值比較函數。在setmultiset,該函數
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;
}

參見

編輯

參考文獻

編輯
  1. ^ ISO/IEC 14882:2011 draft specification (PDF). . p. 797, § 23.4.4 [2018-11-28]. (原始內容 (PDF)存檔於2011-03-13).