C++拾遺（七）——關聯容器，拾遺關聯容器

C++拾遺（七）——關聯容器，拾遺關聯容器

　　關聯容器（Associative containers）支持通過鍵來高效地查找和讀取元素。兩個基本的關聯容器類型是 map 和set。map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的數據。set僅包含一個鍵，並有效地支持關於某個鍵是否存在的查詢。set 和 map 類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。如果一個鍵必須對應多個實例，則需使用 multimap 或 multiset，這兩種類型允許多個元素擁有相同的鍵。

map

關聯數組：元素通過鍵來存儲和讀取

set

大小可變的集合，支持通過鍵實現的快速讀取

multimap

支持同一個鍵多次出現的 map 類型

multiset

支持同一個鍵多次出現的 set 類型

 

pair 類型

• pair 包含兩個數據值。與容器一樣，pair 也是一種模板類型。但又與之前介紹的容器不同，在創建 pair 對象時，必須提供兩個類型名：pair 對象所包含的兩個數據成員各自對應的類型名字，這兩個類型不必相同。
• 與其他標准庫類型不同，對於 pair 類，可以直接訪問其數據成員：其成員都是僅有的，分別命名為 first 和 second。只需使用普通的點操作符——成員訪問標志即可訪問其成員：

  1 string firstBook;
  2 // access and test the data members of the pair
  3 if (author.first == "James" && author.second == "Joyce")
  4     firstBook = "Stephen Hero";

• 除了構造函數，標准庫還定義了一個 make_pair 函數，由傳遞給它的兩個實參生成一個新的 pair 對象。

 

map 類型

• map 是鍵－值對的集合。map 類型通常可理解為關聯數組（associative array）：可使用鍵作為下標來獲取一個值，正如內置數組類型一樣。而關聯的本質在於元素的值與某個特定的鍵相關聯，而並非通過元素在數組中的位置來獲取。
• 在使用關聯容器時，它的鍵不但有一個類型，而且還有一個相關的比較函數。默認情況下，標准庫使用鍵類型定義的 < 操作符來實現鍵（key type）的比較。所用的比較函數必須在鍵類型上定義嚴格弱排序（strict weak ordering）。所謂的嚴格弱排序可理解為鍵類型數據上的“小於”關系。用做 map 對象的鍵時，可使用任意一個鍵值來訪問相應的元素。
• map 對象的元素是鍵－值對，也即每個元素包含兩個部分：鍵以及由鍵關聯的值。map 的 value_type 就反映了這個事實。該類型比前面介紹的容器所使用的元素類型要復雜得多：value_type 是存儲元素的鍵以及值的 pair 類型，而且鍵為 const。在學習 map 的接口時，需謹記 value_type 是 pair 類型，它的值成員可以修改，但鍵成員不能修改。

map<K,V>::key_type  在 map 容器中，用做索引的鍵的類型 map<K,V>::mapped_type   在 map 容器中，鍵所關聯的值的類型 map<K,V>::value_type   一個 pair 類型，它的 first 元素具有 const map<K,V>::key_type 類型，而 second 元素則為 map<K,V>::mapped_type 類型

 

• 定義了 map 容器後，下一步工作就是在容器中添加鍵－值元素對。該項工作可使用 insert 成員實現；或者，先用下標操作符獲取元素，然後給獲取的元素賦值。在這兩種情況下，一個給定的鍵只能對應於一個元素這一事實影響了這些操作的行為。
• 使用下標訪問 map 對象

  map <string, int> word_count; // empty map
  
  // insert default initialzed element with key Anna; then assign 1 to its value
  
  word_count["Anna"] = 1;

　　對於 map 容器，如果下標所表示的鍵在容器中不存在，則添加新元素，這一特性可使程序驚人地簡練：

1 // count number of times each word occurs in the input
3 map<string, int> word_count; // empty map from string to int
5 string word;
6 
7 while (cin >> word)
8　　 ++word_count[word];

• map::insert 的使用

   1 // count number of times each word occurs in the input
   2 map<string, int> word_count; // empty map from string to int
   3 string word;
   4 
   5 while (cin >> word) {
   6 // inserts element with key equal to word and value 1;
   7 // if word already in word_count, insert does nothing
   8 pair<map<string, int>::iterator, bool> ret =
   9     word_count.insert(make_pair(word, 1));
  10 
  11 if (!ret.second) 
  12 // word already in word_count
  13     ++ret.first->second; // increment counter
  14 }

• map 對象的迭代遍歷

   1 // get iterator positioned on the first element
   2 map<string, int>::const_iterator
   3     map_it = word_count.begin();
   4 
   5 // for each element in the map
   6 while (map_it != word_count.end()) {
   7 // print the element key, value pairs
   8     cout << map_it->first << " occurs "
   9             << map_it->second << " times" << endl;
  10     ++map_it; // increment iterator to denote the next element
  11 }

set 類型

• set 容器只是單純的鍵的集合。set 不支持下標操作符，而且沒有定義 mapped_type 類型。在 set 容器中，value_type 不是 pair 類型，而是與 key_type 相同的類型。它們指的都是 set 中存儲的元素類型。這一差別也體現了 set 存儲的元素僅僅是鍵，而沒有所關聯的值。與 map 一樣，set 容器存儲的鍵也必須唯一，而且不能修改。

multimap 和 multiset 類型

• map 和 set 容器中，一個鍵只能對應一個實例。而 multiset 和 multimap類型則允許一個鍵對應多個實例。
• 注意到，關聯容器 map 和 set 的元素是按順序存儲的。而 multimap 和multset 也一樣。因此，在 multimap 和 multiset 容器中，如果某個鍵對應多個實例，則這些實例在容器中將相鄰存放。以下介紹查找元素的幾種策略。
• 使用 find 和 count 操作

   1 // author we'll look for
   2 string search_item("Alain de Botton");
   3 
   4 // how many entries are there for this author
   5 typedef multimap<string, string>::size_type sz_type;
   6 sz_type entries = authors.count(search_item);
   7 // get iterator to the first entry for this author
   8 multimap<string,string>::iterator iter =
   9 authors.find(search_item);
  10 
  11 // loop through the number of entries there are for this autho
  12 for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) 
  13     cout <<iter->second << endl; // print each title

• 另一個更優雅簡潔的方法是使用兩個未曾見過的關聯容器的操作：lower_bound 和 upper_bound。m.lower_bound(k) 返回一個迭代器，指向鍵不小於 k 的第一個元素m.upper_bound(k) 返回一個迭代器，指向鍵大於 k 的第一個元素。

   1 // definitions of authors and search_item as above
   2 // beg and end denote range of elements for this author
   3 typedef multimap<string, string>::iterator authors_it;
   4 
   5 authors_it beg = authors.lower_bound(search_item),
   6     end = authors.upper_bound(search_item);
   7 
   8 // loop through the number of entries there are for this author
   9 while (beg != end) 
  10 {
  11     cout << beg->second << endl; // print each title
  12     ++beg;
  13 }

• 最後，更為簡潔的是使用equal_range操作。m.equal_range(k) 返回一個迭代器的 pair 對象。它的 first 成員等價於 m.lower_bound(k)。而 second 成員則等價於 m.upper_bound(k)

  // definitions of authors and search_item as above
  // pos holds iterators that denote range of elements for this key
  pair<authors_it, authors_it>
  
  pos = authors.equal_range(search_item);
  
  // loop through the number of entries there are for this author
  while (pos.first != pos.second)
   {
      cout << pos.first->second << endl; // print each title
      ++pos.first;
  }