C++ STL之 map\set\multimap\multiset

C++ map,set内部資料結構

  1）Set是一種關聯容器，它用于存儲資料，并且能從一個資料集合中取出資料。它的每個元素的值必須唯一，而且系統會根據該值來自動将資料排序。每個元素的值不能直接被改變。【重點】内部結構采用紅黑樹的平衡二叉樹。multiset 跟set 類似，唯一的差別是允許鍵值重複！！！

如： 為何map和set的插入删除效率比用其他序列容器高？

       為何每次insert之後，以前儲存的iterator不會失效？

       為何map和set不能像vector一樣有個reserve函數來預配置設定資料？

        當資料元素增多時（10000到20000個比較），map和set的插入和搜尋速度變化如何？

或許有得人能回答出來大概原因，但要徹底明白，還需要了解STL的底層資料結構。 C++ STL 之是以得到廣泛的贊譽，也被很多人使用，不隻是提供了像vector, string, list等友善的容器，更重要的是STL封裝了許多複雜的資料結構算法和大量常用資料結構操作。vector封裝數組，list封裝了連結清單，map和 set封裝了二叉樹等，在封裝這些資料結構的時候，STL按照程式員的使用習慣，以成員函數方式提供的常用操作，如：插入、排序、删除、查找等。讓使用者在 STL使用過程中，并不會感到陌生。 C++ STL中标準關聯容器set, multiset, map, multimap内部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統計性能要好于一般的平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，将其稱為AVL-樹)，是以被STL選擇作為了關聯容器的内部結構。本文并不會介紹詳細AVL樹和RB樹的實作以及他們的優劣，關于RB樹的詳細實作參看紅黑樹: 理論與實作(理論篇)。本文針對開始提出的幾個問題的回答，來向大家簡單介紹map和set的底層資料結構。

為何map和set的插入删除效率比用其他序列容器高？ 大部分人說，很簡單，因為對于關聯容器來說，不需要做記憶體拷貝和記憶體移動。說對了，确實如此。map和set容器内所有元素都是以節點的方式來存儲，其節點結構和連結清單差不多，指向父節點和子節點。

結構圖可能如下：

     A

    /  /

  B    C

 / /   / /

D  E F  G

是以插入的時候隻需要稍做變換，把節點的指針指向新的節點就可以了。删除的時候類似，稍做變換後把指向删除節點的指針指向其他節點就OK了。這裡的一切操作就是指針換來換去，和記憶體移動沒有關系。 為何每次insert之後，以前儲存的iterator不會失效？ 看見了上面答案的解釋，你應該已經可以很容易解釋這個問題。iterator這裡就相當于指向節點的指針，記憶體沒有變，指向記憶體的指針怎麼會失效呢(當然 被删除的那個元素本身已經失效了)。相對于vector來說，每一次删除和插入，指針都有可能失效，調用push_back在尾部插入也是如此。因為為了 保證内部資料的連續存放，iterator指向的那塊記憶體在删除和插入過程中可能已經被其他記憶體覆寫或者記憶體已經被釋放了。即使時push_back的時 候，容器内部空間可能不夠，需要一塊新的更大的記憶體，隻有把以前的記憶體釋放，申請新的更大的記憶體，複制已有的資料元素到新的記憶體，最後把需要插入的元素放 到最後，那麼以前的記憶體指針自然就不可用了。特别時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。 為何map和set不能像vector一樣有個reserve函數來預配置設定資料？ 我以前也這麼問，究其原理來說時，引起它的原因在于在map和set内部存儲的已經不是元素本身了，而是包含元素的節點。也就是說map内部使用的Alloc并不是map聲明的時候從參數中傳入的Alloc。例如： map, Alloc > intmap; 這時候在intmap中使用的allocator并不是Alloc, 而是通過了轉換的Alloc，具體轉換的方法時在内部通過Alloc::rebind重新定義了新的節點配置設定器，詳細的實作參看徹底學習STL中的Allocator。其實你就記住一點，在map和set内面的配置設定器已經發生了變化，reserve方法你就不要奢望了。 當資料元素增多時（10000和20000個比較），map和set的插入和搜尋速度變化如何？ 如果你知道log2的關系你應該就徹底了解這個答案。在map和set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結 果，有32個元素，最多比較5次。那麼有10000個呢？最多比較的次數為log10000，最多為14次，如果是20000個元素呢？最多不過15次。 看見了吧，當資料量增大一倍的時候，搜尋次數隻不過多了1次，多了1/14的搜尋時間而已。你明白這個道理後，就可以安心往裡面放入元素了。 最後，對于map和set Winter還要提的就是它們和一個c語言包裝庫的效率比較。在許多unix和linux平台下，都有一個庫叫isc，裡面就提供類似于以下聲明的函數: void tree_init(void **tree); void *tree_srch(void **tree, int (*compare)(), void *data); void tree_add(void **tree, int (*compare)(), void *data, void (*del_uar)()); int tree_delete(void **tree, int (*compare)(), void *data,void (*del_uar)()); int tree_trav(void **tree, int (*trav_uar)()); void tree_mung(void **tree, void (*del_uar)()); 許多人認為直接使用這些函數會比STL map速度快，因為STL map中使用了許多模闆什麼的。其實不然，它們的差別并不在于算法，而在于記憶體碎片。如果直接使用這些函數，你需要自己去new一些節點，當節點特别多， 而且進行頻繁的删除和插入的時候，記憶體碎片就會存在，而STL采用自己的Allocator配置設定記憶體，以記憶體池的方式來管理這些記憶體，會大大減少記憶體碎 片，進而會提升系統的整體性能。Winter在自己的系統中做過測試，把以前所有直接用isc函數的代碼替換成map，程式速度基本一緻。當時間運作很長 時間後（例如背景服務程式），map的優勢就會展現出來。從另外一個方面講，使用map會大大降低你的編碼難度，同時增加程式的可讀性。何樂而不為？

10.3 MAP使用

10.3.1. map 對象的定義

map<k, v> m;                  建立一個名為 m 的空 map 對象，其鍵和值的類型分别為 k 和 v

map<k, v> m(m2);           建立 m2 的副本 m，m 與 m2 必須有相同的鍵類型和值類型

map<k, v>  m(b, e);         建立 map 類型的對象 m，存儲疊代器 b 和 e 标記的範圍内所有元素的副本。元素的類型必須能轉換為 pair<const k, v>

10.3.2. map 定義的類型

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 類型。value_type 是存儲元素的鍵以及值的 pair 類型，而且鍵為 const。

map 疊代器進行解引用将産生 pair 類型的對象，對疊代器進行解引用将獲得一個 pair 對象，它的 first 成員存放鍵，為const，而 second 成員則存放值。

map<string, int>::iterator map_it = word_count.begin();   map_it->first;  map_it->second;

map 類額外定義了兩種類型：key_type 和 mapped_type；

如 map<string, int>::key_type；

10.3.3. 給 map 添加元素

定義了 map 容器後，下一步工作就是在容器中添加鍵－值元素對。該項工作可使用 insert 成員實作；或者，先用下标操作符擷取元素，然後給擷取的元素指派。在這兩種情況下，一個給定的鍵隻能對應于一個元素這一事實影響了這些操作的行為。

10.3.4. 使用下标通路 map 對象

map <string, int> word_count;

word_count["Anna"] = 1;

1. 在 word_count 中查找鍵為 Anna 的元素，沒有找到。

2. 将一個新的鍵－值對插入到 word_count 中。它的鍵是 const string 類型的對象，儲存 Anna。而它的值則采用值初始化，這就意味着在本例中值為 0。

3. 将這個新的鍵－值對插入到 word_count 中。

4. 讀取新插入的元素，并将它的值賦為 1。

使用下标通路 map 與使用下标通路數組或 vector 的行為截然不同：用下标通路不存在的元素将導緻在 map 容器中添加一個新元素，它的鍵即為該下标值。

map<string, int> word_count; // empty map from string to int

string word;

while (cin >> word)

++word_count[word];

10.3.5. map::insert 的使用

m.insert(e)                   e是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，則插入一個值為 e.second 的新元素；如果該鍵在 m 中已存在，則保持 m 不變。該函數傳回一個pair 類型對象，包含指向鍵為 e.first 的元素的 map 疊代器，以及一個 bool 類型的對象，表示是否插入了該元素

m.insert(beg,end)          beg 和 end 是标記元素範圍的疊代器，其中的元素必須為m.value_type 類型的鍵－值對。對于該範圍内的所有元素，如果它的鍵在 m 中不存在，則将該鍵及其關聯的值插入到 m。傳回 void 類型

m.insert(iter,e)              e 是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，則建立新元素，并以疊代器 iter 為起點搜尋新元素存儲的位置。傳回一個疊代器，指向 m 中具有給定鍵的元素

word_count.insert(map<string, int>::value_type("Anna", 1));

在添加新 map 元素時，使用 insert 成員可避免使用下标操作符所帶來的副作用：不必要的初始化。

傳遞給 insert 的實參相當笨拙。可用兩種方法簡化：使用 make_pair:

word_count.insert(make_pair("Anna", 1));

或使用 typedef

typedef map<string,int>::value_type valType;

word_count.insert(valType("Anna", 1));

檢測 insert 的傳回值

1)

如果試圖插入的元素所對應的鍵已在容器中，則 insert 将不做任何操作.

2)

但是，帶有一個鍵－值 pair 形參的 insert 版本将傳回一個值：包含一個疊代器和一個 bool 值的 pair 對象，其中疊代器指向 map 中具有相應鍵的元素，而 bool 值則表示是否插入了該元素。如果該鍵已在容器中，則其關聯的值保持不變，傳回的 bool 值為 false。在這兩種情況下，疊代器都将指向具有給定鍵的元素。

map<string, int> word_count; // empty map from string to int

string word;

while (cin >> word) {

// inserts element with key equal to word and value 1;

// if word already in word_count, insert does nothing

pair<map<string, int>::iterator, bool> ret =

word_count.insert(make_pair(word, 1));

if (!ret.second) // word already in word_count

++ret.first->second; // increment counter

}

操作：

++((ret.first)->second); // equivalent expression

10.3.6. 查找并讀取 map 中的元素

m.count(k)              傳回 m 中 k 的出現次數

m.find(k)                 如果 m 容器中存在按 k 索引的元素，則傳回指向該元素的疊代器。如果不存在，則傳回超出末端疊代器（第 3.4 節）

對于 map 對象，count 成員的傳回值隻能是 0 或 1。map 容器隻允許一個鍵對應一個執行個體，是以 count 可有效地表明一個鍵是否存在。而對于 multimaps容器，count 的傳回值将有更多的用途.

int occurs = 0;

if (word_count.count("foobar"))

occurs = word_count["foobar"];

在執行 count 後再使用下标操作符，實際上是對元素作了兩次查找。如果希望當元素存在時就使用它，則應該用 find 操作。

int occurs = 0;

map<string,int>::iterator it = word_count.find("foobar");

if (it != word_count.end())

occurs = it->second;

10.3.7. 從 map 對象中删除元素

1）參數為疊代器的時候，map 容器的 erase 操作傳回 void，而順序容器的 erase 操作則傳回一個疊代器，指向被删除元素後面的元素。

2）參數為key_type時候，erase 函數傳回被删除元素的個數。對于 map 容器，該值必然是 0 或 1。如果傳回 0，則表示欲删除的元素在 map 不存在。

m.erase(k)                              删除 m 中鍵為 k 的元素。傳回 size_type 類型的值，表示删除的元素個數

m.erase(p)                              從 m 中删除疊代器 p 所指向的元素。p 必須指向 m 中确實存在的元素，而且不能等于 m.end()。傳回 void

m.erase(b,e)                           從 m 中删除一段範圍内的元素，該範圍由疊代器對 b 和 e 标記。b 和 e 必須标記 m 中的一段有效範圍：即 b 和 e 都必須指向m

中的元素或最後一個元素的下一個位置。而且，b 和 e 要麼相等（此時删除的範圍為空），要麼 b 所指向的元素必須出現在 e 所指向的元素之前。傳回 void 類型

10.4.1. set 容器的定義和使用

在 set 中添加元素

1）

set<string> set1; // empty set

set1.insert("the"); // set1 now has one element

set1.insert("and"); // set1 now has two elements

2）

set<int> iset2; // empty set

iset2.insert(ivec.begin(), ivec.end());

調用 insert 函數時，提供一對疊代器實參，插入其标記範圍内所有的元素。該版本的 insert 函數類似于形參為一對疊代器的構造函數——對于一個鍵，僅插入一個元素：

與 map 容器的操作一樣，帶有一個鍵參數的 insert 版本傳回 pair 類型對象，包含一個疊代器和一個 bool 值，疊代器指向擁有該鍵的元素，而 bool 值表明是否添加了元素。

使用疊代器對的 insert 版本傳回 void 類型。

從 set 中擷取元素

iset.find(1) // returns iterator that refers to the element with key == 1

iset.find(11) // returns iterator == iset.end()（假設最多隻有十個元素，從1到10）

iset.count(1) // returns 1

iset.count(11) // returns 0

set 容器不提供下标操作符。為了通過鍵從 set 中擷取元素，可使用 find運算。如果隻需簡單地判斷某個元素是否存在，同樣可以使用 count 運算，傳回 set 中該鍵對應的元素個數。當然，對于 set 容器，count 的傳回值隻能是1（該元素存在）或 0（該元素不存在）：

正如不能修改 map 中元素的鍵部分一樣，set 中的鍵也為 const。

set<int>::iterator set_it = iset.find(1);

*set_it = 11; // error: keys in a set are read-only

cout << *set_it << endl; // ok: can read the key

10.5. multimap 和 multiset 類型

multimap 和 multiset 所支援的操作分别與 map 和 set 的操作相同，隻有一個例外：multimap 不支援下标運算。不能對 multimap 對象使用下标操作，

因為在這類容器中，某個鍵可能對應多個值。

10.5.1 删除操作：

帶有一個鍵參數的 erase 版本将删除擁有該鍵的所有元素，并傳回删除元素的個數。而帶有一個或一對疊代器參數的版本隻删除指定的元素，并傳回 void類型：

multimap<string, string> authors;

string search_item("Kazuo Ishiguro");

multimap<string, string>::size_type cnt =authors.erase(search_item);

10.5.2. 在 multimap 和 multiset 中查找元素

1）使用 find 和 count 操作

使用 find 和 count 可有效地解決問題。count 函數求出某鍵出現的次數，而 find 操作則傳回一個疊代器，指向第一個擁有正在查找的鍵的執行個體：

typedef multimap<string, string>::size_type sz_type;

sz_type entries = authors.count(search_item);

multimap<string,string>::iterator iter =authors.find(search_item);

for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter)

cout <<iter->second << endl; // print each title

2）另一個更優雅簡潔的方法是使用兩個未曾見過的關聯容器的操作：lower_bound 和 upper_bound。

m.lower_bound(k)                      傳回一個疊代器，指向鍵不小于 k（>=k） 的第一個元素

m.upper_bound(k)                      傳回一個疊代器，指向鍵大于 k (> k) 的第一個元素

m.equal_range(k)                      傳回一個疊代器的 pair 對象它的 first 成員等價于 m.lower_bound(k)。而 second 成員則等價于 m.upper_bound(k)

如果該鍵k不在 multimap 中，這兩個操作将傳回同一個疊代器，指向依據元素的排列順序該鍵應該插入的位置。

如果所查找的元素擁有 multimap 容器中最大的鍵，那麼的該鍵上調用 upper_bound 将傳回超出末端疊代器。如果所查找的鍵不存在，而且比 multimap 容器中所有的鍵都大，則 low_bound 也将傳回超出末端疊代器。

typedef multimap<string, string>::iterator authors_it;

authors_it beg = authors.lower_bound(search_item),

end = authors.upper_bound(search_item);// loop through the number of entries there are for this author

while (beg != end)

{

cout << beg->second << endl; // print each title

++beg;

}

若該鍵沒有關聯的元素，則 lower_bound 和 upper_bound 傳回相同的疊代器：都指向同一個元素或同時指向 multimap 的超出末端位置。它們都指向在保

持容器元素順序的前提下該鍵應被插入的位置。