順序容器
- 元素在順序容器中的順序與加入容器時的位置相對應
- 關(guān)聯(lián)容器中元素的位置由元素相關(guān)聯(lián)的關(guān)鍵字值決定
順序容器概述
- 所有順序列表都提供了快速順序訪問元素的能力，但是，這些容器在以下方面都有不同程度的性能折中
- [x] 向容器添加或從容器中刪除元素的代價
- [x] 非順序訪問容器中元素的代價
vector //可變大小數(shù)組坞古，支持快速隨機訪問，在尾部之外的位置插入或刪除元素可能很慢
deque //雙端隊列，支持快速隨機訪問揩局，在頭尾位置插入/刪除速度很快
list //雙向鏈表，只支持雙向順序訪問掀虎，在list中任何位置進行插入/刪除都很快
forward_list //單向鏈表凌盯，只支持單向順序訪問，在鏈表任何位置進行插入/刪除都很快
array //固定大小數(shù)組烹玉，支持快速隨機訪問驰怎，不能添加或刪除元素
string //與vector相似的容器，但專門用于保存字符二打，隨機訪問快县忌，在尾部插入/刪除速度快
- 除了對固定大小的array外，其他容器都提供高效继效、靈活的內(nèi)存管理
- 容器保存元素的策略對容器操作的效率有著固有的症杏，甚至是重大的影響，在某些情況下瑞信，存儲策略還會影響特定容器是否支持特定操作
-
string和vector將元素保存在連續(xù)的內(nèi)存空間中厉颤，由于元素是連續(xù)存儲的，由元素的下標來計算其地址是十分快速的喧伞，但是走芋，在這兩種容器的中間位置添加或刪除元素就會非常耗時
- 與內(nèi)置數(shù)組相比，array是一種更安全潘鲫，更容器使用的數(shù)組類型
- 通常翁逞，使用vector是最好的選擇
- 選擇容器的基本原則
- [x] 除非有很好的理由選擇其他容器，否自使用vector
- [x] 如果程序要求隨機訪問溉仑，使用vector或deque
- [x] 如果程序要求在容器的中間插入或刪除元素挖函，應該使用list或forward_list
- [x] 如果程序需要在頭尾插入或刪除元素，但不會在中間位置進行插入或刪除操作浊竟，使用deque
- 如果不確定使用哪種容器怨喘，那么可以在程序中只使用vector和list公共的操作:使用迭代器，不使用下標操作振定，避免隨機訪問必怜，這樣在必要時選擇使用vector或list都很方便
容器庫概覽
- 每個容器都定義在一個頭文件中，文件名與類型名相同
- 順序容器幾乎可以保存任意類型的元素后频，包括元素類型可以是另一個容器
vector<vector<string>> lines; //vector的vector
迭代器
-
forward_list迭代器不支持遞減運算符(--)
- 迭代器范圍的概念是標準庫的基礎
- 一個迭代器范圍由一對迭代器表示梳庆，兩個迭代器分別指向同一個容器中首元素或者是尾元素之后的位置暖途，它們標記了容器中元素的一個范圍
begin和end成員
- begin和end有多個版本:帶r的版本返回反向迭代器,以c開頭的版本返回cosnt迭代器
list<string> a;
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin(); //list<string>::const_reverse_iterator
容器定義和初始化
- 每個容器類型都定義了一個默認的構(gòu)造函數(shù)膏执，除array之外驻售，其他容器的默認構(gòu)造函數(shù)都會創(chuàng)建一個指定類型的空容器，且都可以接受指定容器大小和元素初始值的參數(shù)
- 當將一個容器初始化為另一個容器的拷貝時更米，兩個容器的容器類型和元素類型必須相同
- 只有順序容器的構(gòu)造函數(shù)才接受大小參數(shù)欺栗，關(guān)聯(lián)容器并不支持
- 當定義一個array時，必須指定元素類型和容器大小
array<int,10> temp;
賦值和swap
- 賦值相關(guān)運算會導致指向左邊容器內(nèi)部的迭代器征峦、引用和指針失效迟几，而swap操作將容器內(nèi)容交換不會導致指向容器的迭代器、引用和指針失效(容器類型為array和string的情況除外)
容器大小操作
- [x] size 返回容器中元素的數(shù)目
- [x] empty 當size為0時返回true眶痰，反之返回false
- [x] max_size 返回一個大于或等于該類型容器所能容納的最大元素數(shù)的值
- [x] forward_list支持max_list和empty瘤旨，但不支持size
關(guān)系運算符
- 除無序關(guān)聯(lián)容器外的所有容器都支持關(guān)系運算符，關(guān)系運算符左右兩邊的運算對象必須是相同類型的容器竖伯，且必須保存相同類型的元素
vector<int> v1 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
vector<int> v3 = {1,3,5,7};
vector<int> v4 = {1,3,5,7,9,12};
v1 < v2 //true v1和v2在元素[2]處不同存哲，v1[2]小于v2[2]
v1 < v3 //false 所有元素相等，但v3中元素數(shù)目少
v1 == v4 //true 每個元素相等七婴，且v1和v4大小相同
v1 == v2 //false v2元素數(shù)目比v1少
- 只有當其元素運算符也定義了相應的比較運算符時祟偷，我們才可以使用關(guān)系運算符來比較兩個容器
順序容器操作
- 順序容器和關(guān)聯(lián)容器的不同之處在于兩者組織元素的方式，這些不同之處直接關(guān)系到了元素如何存儲打厘、訪問修肠、添加以及刪除
順序容器添加元素
- 除了array外，所有標準庫容器都提供靈活的內(nèi)存管理户盯，在運行時可以動態(tài)添加或刪除元素來改變?nèi)萜鞔笮?/li>
- 向一個vector嵌施、string或deque插入元素會使所有指向容器的迭代器、引用和指針失效
- 將元素插入到vector莽鸭、deque和string中的任何位置都是合法的吗伤，然而，這樣做可能會很耗時
- C++11引入了三個新成員
- [x] emplace_front對應push_fromt
- [x] emplace對應insert
- [x] emplace_back對應push_back
- emplace函數(shù)在容器中直接構(gòu)造元素硫眨，傳遞給emplace函數(shù)的參數(shù)必須與元素類型的構(gòu)造函數(shù)相匹配足淆，并且emplace操作比相對應的push操作更快
訪問元素
- 對一個空容器調(diào)用front和back，就像使用一個越界的下標一樣礁阁，是一種嚴重的程序設計錯誤
- 訪問成員函數(shù)返回的是引用
if(!c.empty()){
c.front() = 42; //將42賦予c中的第一個元素
auto & v = c.back(); //獲得指向最后一個元素的引用
v = 1024; //改變c中的元素
auto v2 = c.back(); //v2不是一個引用巧号，它是c.back()的一個拷貝
v2 = 0; //未改變c中的元素
}
- [x] `string`、`vector`姥闭、`deque`丹鸿、 `array`這幾個容器都提供快速隨機訪問
刪除元素
- 刪除元素的成員函數(shù)并不檢查其參數(shù)，在刪除元素之前棚品，程序猿必須確保它是存在的
-
vector和string不支持pop_front
- 成員函數(shù)erase從容器中指定位置刪除元素卜高，返回指向刪除的最后一個元素之后的位置的迭代器
- ww36可以用resize來增大或縮小容器弥姻，但array不支持resize
向容器中添加或刪除元素的操作可能會使指向容器元素的指針、引用掺涛、迭代器失效，失效的指針疼进、引用薪缆、迭代器將不再表示任何元素，使用它們是嚴重的程序設計錯誤由于向迭代器添加元素和從迭代器刪除元素的代碼可能會使迭代器失效伞广，因此必須保證每次改變?nèi)萜鞯牟僮髦蠖颊_地重新定位迭代器拣帽，對于vector、string嚼锄、deque尤為重要- 不要保存end返回地迭代器
- [x] 添加或刪除元素地循環(huán)程序必須反復調(diào)用end减拭，而不能在循環(huán)之前保存end返回的迭代器
vector對象是如何增長的
- 當不得不獲取新的內(nèi)存空間時，vector和string地實現(xiàn)通常會分配比新地空間需求更大的內(nèi)存空間区丑，容器預留這些空間作為備用
- capacity函數(shù)表示在不分配新的內(nèi)存的情況下vector或string最多可以保存多少個元素
- size函數(shù)表示vector或string當前已經(jīng)保存的元素的數(shù)量
- 可以調(diào)用shrink_to_fit函數(shù)來要求vector將超出當前大小的多余內(nèi)存退回給系統(tǒng)
- 每個vector實現(xiàn)都可以選擇自己的內(nèi)存分配策略拧粪，但是必須遵守的一條原則是:只有當迫不得已時才可以分配新的內(nèi)存空間
- 通過在一個初始為空的vector上調(diào)用n次push_back來創(chuàng)建一個n個元素的vector，所花費的時間不能超過n的常數(shù)倍
額外的string操作
- 通常當我們從一個const char *創(chuàng)建string時沧侥，指針指向的數(shù)組必須以空字符結(jié)尾
substr操作
string s("hello world");
string s2 = s.substr(0,5); //s2 = hello
數(shù)值轉(zhuǎn)換
int i = 42;
string s = to_string(i); //將整數(shù)i轉(zhuǎn)換為字符表示形式
double d = stod(s); //將字符串s轉(zhuǎn)換為浮點數(shù)
