一突委、容器——C++ primer 6th P713

儲存其他對象的對象逆巍，且該對象有處理“其他對象”的方法惧辈。
1）容器優(yōu)點

• 容器類為解決對特定代碼重用。
• 可自行擴展铆遭。
• 容器類自動申請和釋放內存.

基本容器特征 C++ primer P695

c++11 新增容器要求 P696

1.1 序列容器（sequence）

序列中的元素有確定的順序

• 迭代器至少是正向迭代器：保證元素按特定順序排序硝桩。
• 要求其元素線性順序排列：存在首、尾元素枚荣，其余元素前后分別只有一個元素亿柑。

序列的要求

表中 t 表示類型為T（儲存在容器中的值類型）的值， n 表示整數(shù)棍弄， p、q疟游、i 和 j 表示迭代器呼畸。

序列可選要求

• 表中操作復雜度為固定。
• vector 未定義在頭部操作（插入颁虐、刪除）——操作復雜度為線性蛮原。
• list不支持數(shù)組表示法[ ]和隨機訪問.at( )。
• vector另绩、list是可反轉容器儒陨。

1）向量vector（線性表順序儲存）

• 可直接訪問元素花嘶。
• 線性順序結構，支持[ ]和vector.at()蹦漠。
• 動態(tài)內存分配椭员。
• 內部插入、刪除效率低笛园。通常在后端進行追加和刪除隘击。

2) 雙向鏈表 list

中間每個元素都與前后元素鏈接⊙忻可以雙向遍歷鏈表埋同。

• 鏈表不支持隨機訪問，不能用非成員函數(shù)的sort(),因此該類中定義了成員函數(shù)sort()棵红。
• 單鏈表forward_list(C++11)凶赁。

list成員函數(shù)

3）雙端隊列 deque（double-ended queue）

• deque雙端隊列:允許在兩端插入和刪除元素。

雙端隊列的一些操作

4）適配器類（挖坑逆甜，目前僅了解）

• queue隊列:是一種操作受限制的線性表——只允許在隊首（front）刪除元素虱肄、隊尾（rear）添加元素。
  給底層類（默認queue）提供隊列接口忆绰。

queue的操作

• priorty_queue:支持操作與queue相同浩峡。該模板類中最大的元素移到隊首。错敢？翰灾？？如何移

• stack 棧：給底層類（默認vector）提供棧接口稚茅。

stack的操作

1.2 關聯(lián)式容器

關聯(lián)容器將值和鍵關聯(lián)在一起纸淮，并使用鍵來查找值。

• 優(yōu)點：對元素快速訪問亚享。
• 關聯(lián)容器允許插入新元素咽块，但不能指定插入位置：通常有用于確定數(shù)據(jù)放置位置的算法。
• 通常使用樹結構實現(xiàn)欺税。

1）集合set侈沪、multiset

#include<set>
其值類型與鍵相同，鍵是唯一的晚凿。

• set :鍵就是值亭罪。
• multiset ：多個值的鍵相同。

2）map歼秽、multimap

#include<map>
其值類型與鍵不相同应役，鍵是唯一的。

• map ：每個鍵只對應一個值。
• multimap ：每個鍵與多個值相關聯(lián)箩祥。

3）無序關聯(lián)容器unordered_（C++11）

• 關聯(lián)容器：基于樹結構的院崇。
• 無序關聯(lián)容器：基于數(shù)據(jù)結構哈希表的，旨在提高添加袍祖、刪除元素的速度及提高查找算法效率底瓣。
  unordered_set 和 unordered_multiset
unordered_map 和 unordered_multimap

二、STL函數(shù)——適用于容器的非成員函數(shù)

#include<algorithm>

books對象容器的源結構類型

• for_each():將被指向函數(shù)應用于容器區(qū)間中的各個元素盲泛。要求元素隨機訪問濒持。

for(vector<Review>::iterator pr=books.begin();pr<books.end();pr++)
   ShowReview(*pr);

• 避免顯示調用迭代器，可寫為for_each(books.begin(),books.end(),ShowReview);
• 可替換為基于范圍的for循環(huán)：
  for(auto x : books) ShowReview(x);
  x類型為Review,循環(huán)一次將books中每個Review對象傳遞給ShowReview()寺滚。
• 不同于for_each(),基于范圍for循環(huán)可使用引用&修改容器內容:
  for(auto & x : books) InflateReview(x);

• random_shuffle():接受兩個指定區(qū)間的迭代器參數(shù)柑营，并隨機排列該區(qū)間中的元素。

• sort():排序時使用內置操作符<進行比較;若對用戶自定義對象使用sort()村视，則必須定義能夠處理該類型對象的operator<()函數(shù)（操作符重載）;要求元素隨機訪問

c++ primer P681 全排序

c++ primer P681 完整弱排序

（1）sort(a.begin(),a.end()); //對a中的從a.begin()（包括它）到a.end()（不包括它官套，超尾元素）的元素進行從小到大排列
（2）reverse(a.begin(),a.end()); //元素倒置，但不排列.
（3）find(a.begin(),a.end(),10); //a中查找10蚁孔，若存在返回其在向量中的位置

三奶赔、迭代器

模板使算法獨立于存儲的數(shù)據(jù)類型；迭代器使獨立于使用的容器類型杠氢。

注意：迭代器不是常量站刑，是廣義指針：能夠遍歷容器的對象。

實現(xiàn)find函數(shù)鼻百，迭代器需具備的特征：

• 能對迭代器*解引用操作绞旅，訪問其引用的值。
• 能將一個迭代器賦給另一個温艇；迭代器之間能夠比較因悲。
• 能夠使用迭代器遍歷容器的所有元素——++運算符。C++將operator++前綴版本勺爱，operator++(int)后綴版本晃琳。

• s.end():返回一個指向超尾位置（末尾后一位）的迭代器。
• auto ：自動類型推斷琐鲁，簡化

vector<double> s;
auto pd = s.begin(); //替代 vector<double>::iterater pd=s.begin(); 

1）迭代器功能分類

排序算法需要通過隨機訪問迭代器來訪問容器中的元素卫旱，因此有的容器就不支持排序算法。

常用的迭代器按功能強弱分為輸入围段、輸出顾翼、正向、雙向蒜撮、隨機訪問五種，這里只介紹常用的三種。

• 正向迭代器段磨。假設 p 是一個正向迭代器取逾，則 p 支持以下操作：++p，p++苹支，*p砾隅。此外，兩個正向迭代器可以互相賦值债蜜，還可以用==和!=運算符進行比較晴埂。

• 雙向迭代器。雙向迭代器具有正向迭代器的全部功能寻定。除此之外儒洛，若 p 是一個雙向迭代器，則--p和p--都是有定義的狼速。--p使得 p 朝和++p相反的方向移動琅锻。

• 隨機訪問迭代器。隨機訪問迭代器具有雙向迭代器的全部功能向胡。若 p 是一個隨機訪問迭代器恼蓬，i 是一個整型變量或常量，則 p 還支持以下操作：

p+=i：使得 p 往后移動 i 個元素僵芹。
p-=i：使得 p 往前移動 i 個元素处硬。
p+i：返回 p 后面第 i 個元素的迭代器。
p-i：返回 p 前面第 i 個元素的迭代器拇派。
p[i]：返回 p 后面第 i 個元素的引用荷辕。

隨機訪問迭代器: p1、p2

• p1<p2 ：p1 經過若干次（至少一次）++操作后攀痊，就會等于 p2桐腌。 可用 <、>苟径、<=案站、>= 運算符進行比較。
• p2-p1 ：返回值是 p2 所指向元素和 p1 所指向元素的序號之差（p2 和 p1 之間的元素個數(shù)減一）棘街。
  注：++i比 i++執(zhí)行速度更快庶香。

表1：不同容器的迭代器的功能