關聯性容器
關聯容器是指C++標準模板庫中的一套類模板,實現了有序關聯數組。[1]可用於存放任意數據類型的元素。C++標準中定義的關聯容器有: set
, map
, multiset
, multimap
。
關聯容器類似於C++中的無序關聯容器。差別為:
- 關聯容器是紅黑樹實現,無序關聯容器是哈希表實現。
- 關聯容器保證按鍵值有序遍歷,因此可以做範圍查找,而無序關聯容器不可以。關聯支持一些導航類的操作,如求出給定鍵最鄰近的鍵,最大鍵、最小鍵操作。
- 關聯容器的迭代器不會失效,除非所指元素被刪除。無序關聯容器的iterator在修改元素時可能會失效。所以對關聯容器的遍歷與修改在一定程度上可並行
- 哈希表查找時候要算hash,這個最壞時間複雜度是O(key的長度);基於比較的有序關聯容器通常只使用頭幾個字符進行比較
成員函數
編輯用法
編輯下述例子展示如何用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;
}
參見
編輯參考文獻
編輯- ^ ISO/IEC 14882:2011 draft specification (PDF). . p. 797, § 23.4.4 [2018-11-28]. (原始內容 (PDF)存檔於2011-03-13).