C++ primer筆記----關聯容器

1、 關聯容器與順序容器有着根本的不同；關聯容器的元素是按關鍵詞來儲存和通路的，順序容器是按他們在容器中的位置來順序通路

2、關鍵詞在關聯容器中起到重要的作用，map中的元素是（關鍵字—值）對，關鍵詞起到索引的作用，值是與索引相關聯的資料。set每個元素隻包含一個關鍵字，支援高效的關鍵詞查找

3、标準庫提供8個關聯容器，主要是map/set，是否重複關鍵字，順序儲存容器與否

4、map的定義及使用

1：包含map頭檔案，2：指定關鍵詞和值的類型，3：關鍵詞可作為下标，索引對應值

5、size_t是一種機器相關的無符号類型，它被設計的足夠大以便能儲存記憶體中的任意對象的大小，在使用數組下标時，經常會用到此類型

6、對map對象進行下标操作，如若關鍵字不在map中，下标運算符會在map中建立一個新元素(關鍵詞)，對應值為預設初始化值。

7、從map對象中提取一個元素時，會得到一個pair對象，其儲存兩個public資料對象，first為其關鍵字，second為其對應值。

8、這幾個容器的主要用法：

map：存儲字典型資料

set：壞值檢驗，隻有關鍵字的好處

list：任意位置任意删除添加資料

deque：資訊處理，隻在頭部

vector：相關聯資料，順序處理

9、set的定義與使用，與map值差一個值而已，它隻有關鍵字

10、set對find()的使用，傳回一個疊代器，如果給定的關鍵詞在set中，疊代器指向該關鍵詞，如不在，則傳回尾後疊代器

11、頭檔案：

#inlude <cctype.h>

ispunct() 函數用來檢測一個字元是否為标點符号或特殊字元，其原型為：int ispunct(int c);

12、關聯容器不支援順序容器的位置相關操作，如：push_back、push_front，因為其是按關鍵字存儲的

13、關聯容器的疊代器都是雙向的，還有一些關于哈希性能的操作

14、multimap和multiset允許多個元素具有相同的關鍵字，是以給multiset和multimap中傳入相同的元素，是可行的，而set、map會忽略相同關鍵字的元素

15、set和list的差別是set中的元素不可以重複、且有序。

16、pair，标準庫類型，儲存在頭檔案utility中。儲存兩個資料成員，類似容器。

17、關聯容器額外的類型别名：使用作用域運算符來提取一個類型的成員

key_type：表示此容器類型的關鍵字類型

mapped_type：每個關鍵字關聯的類型，隻适用于map

value_type：對于set，與key_type相同，對于map，為

pair<const key_type，mapped_type>

18、當解引用一個關聯容器的疊代器時，我們會得到一個類型為容器的value_type的值的引用;map的value_type是一個pair，我們可以改變pair的值，但是不能改變關鍵字成員的值

19、set的疊代器是const的，關鍵字是const

20、insert有兩個版本，分别接受一對疊代器，或是一個初始化器清單

21、對一個map進行insert操作時，必須記住元素類型是pair，可以在insert的參數清單中建立一個pair，在參數清單中使用花括号初始化

22、insert()在關聯容器中添加一個元素或者一個元素範圍，由于map和set沒有重複關鍵字，是以插入相同的元素不會産生任何影響

23、insert的傳回值依賴于容器類型與元素類型，對于不包含重複關鍵字的容器，insert傳回一個pair，第一個成員是指向具有指定關鍵字的元素，第二個元素是一個bool值，指出插入元素是已經在元素中還是插入成功，若關鍵詞已在容器中，insert什麼都不做，第二個參數變為false

24、遞增計數器：ret.first是pair的第一個成員，是map的疊代器，->之後，解引用疊代器，提取的是map中的元素，也就是一個pair，找到此元素的第二個值，進行遞增操作

25、和順序容器一樣，我們可以向erase()傳入一個疊代器或者一個疊代器對來删除元素，函數傳回void，還有一個版本的erase()接收一個

key_type

的參數，删除每個關鍵詞為參數的元素，傳回一個size_type，指出被删除元素的數量

26、set不支援下标操作，map和unordered_map支援下标操作，multimap和unordered_multimap也沒有下标操作，因為有相同的元素

27、map的下标操作接受一個索引(關鍵詞)，擷取的是此關鍵詞相關聯的值(即mapped_type值)，但是若map中無此關鍵詞，則它會建立一個新的元素并插入到map中，關聯值将進行值初始化

28、c.at(k)：通路關鍵詞為k的元素，若k不在c中，抛出out_of_range異常；c[k]傳回關鍵字為k的元素；如果k不在c中，添加一個關鍵字為k的元素，對其進行值初始化。

29、map的下标操作（傳回mapped_type）與解引用疊代器*(傳回value_type)傳回值不同

30、對于map和set中的元素查找以及計數使用find和count，都接受關鍵字，find傳回關鍵字指向的元素的疊代器或者尾後疊代器，count傳回關鍵字的數量

31、map的下标操作可能會造成副作用，插入我們不想插入的元素，可以用find代替尋找元素

32、lower_bound和upper_bound找不到關鍵詞的話，會指向一個不影響排序的關鍵詞插入位置；如果兩者都傳回相同的疊代器，則給定關鍵字不在容器中

33、equal_range()函數，接收一個關鍵字，傳回一個疊代器pair，若關鍵字存在，第一個疊代器指向該關鍵字比對的元素，第二個關鍵字指向最後一個元素比對之後的位置，如關鍵字不存在，兩個疊代器都指向關鍵字可以插入的位置

34、無序版本優勢：當容器中key沒有明顯的順序關系時更有用,且不需要耗費多餘的時間來維護容器中的key序列

有序版本優勢：當容器中key有明顯的順序關系時更有用,且我們不需要考慮排序問題,容器自動維護序列(字典序)

35、map的key_value是有序的，set本身就是有序的，有序容器的操作可以用于無序容器

36、無序容器通路元素時，首先計算元素的哈希值，它指出應該搜尋那個桶，因為容器将具有一個特定哈希值的所有元素都儲存在一個桶中