9.3順序容器操作

順序容器和關聯容器的不同之處在于兩者組織元素的方式。這些不同之處直接關系到了元素如何存儲、訪問、添加以及刪除。上一節介紹了所有容器都支持的操作（羅列于表9.2（第295頁））。本章剩余部分將介紹順序容器所特有的操作。

9.3.1向順序容器添加元素

除array外，所有標準庫容器都提供靈活的內存管理。在運行時可以動態添加或刪除元素來改變容器大小。表9.5列出了向順序容器（非array）添加元素的操作。

當我們使用這些操作時，必須記得不同容器使用不同的策略來分配元素空間，而這些策略直接影響性能。在一個vector或string的尾部之外的任何位置，或是一個deque的首尾之外的任何位置添加元素，都需要移動元素。而且，向一個vector或string添加元素可能引起整個對象存儲空間的重新分配。重新分配一個對象的存儲空間需要分配新的內存，并將元素從舊的空間移動到新的空間中。

使用push_back

在3.3.2節(第90頁)中，我們看到push_back將一個元素追加到一個vector的尾部。除array和forward_list之外，每個順序容器(包括string類型)都支持push_back
例如，下面的循環每次讀取一個string到word中，然后追加到容器尾部：
//從標準輸入讀取數據，將每個單詞放到容器末尾
string word;while(cin>>word)container.push_back(word);
對push_back的調用在container尾部創建了一個新的元素，將container的size增大了.該元素的值為word的一個拷貝。container的類型可以是list、vector或deque
由于string是一個字符容器，我們也可以用push_back在string末尾添加字符：

void pluralize(size_tent,string&word)
{
if(ent>1)
word.push_back(*sr);//等價于word+='s'
}

容器元素是拷貝

當我們用一個對象來初始化容器時，或將一個對象插入到容器中時，實際上放入到容器中的是對象值的一個拷貝，而不是對象本身。就像我們將一個對象傳遞給非引用參數(參見3.2.2節，第79頁)一樣，容器中的元素與提供值的對象之間沒有任何關聯。隨后對容器中元素的任何改變都不會影響到原始對象，反之亦然。

使用push_front

除了push_back,list,forward_list和deque容器還支持名為push_front的類似操作。此操作將元素插入到容器頭部
list<int>ilist;//將元素添加到ilist開頭
for(size_tix=0;ix!=4;++ix)ilist.push_front(ix);
此循環將元素0、1、2、3添加到ilist頭部。每個元素都插入到list的新的開始位置(newbeginning)。即，當我們插入1時，它會被放置在0之前，2被放置在1之前，依此類推。因此，在循環中以這種方式將元素添加到容器中，最終會形成逆序。在循環執行完畢后，ilist保存序列3、2、1、0。注意，deque像vector一樣提供了隨機訪問元素的能力，但它提供了vector所不支持的push_front。deque保證在容器首尾進行插入和刪除元素的操作都只花費常數時間。與vector一樣，在deque首尾之外的位置插入元素會很耗時。

在容器中的特定位置添加元素

push_back和push_front操作提供了一種方便地在順序容器尾部或頭部插入單個元素的方法。insert成員提供了更一般的添加功能，它允許我們在容器中任意位置插入0個或多個元素。
vector、deque、list和string都支持insert成員。forward_list提供了特殊版本的insert成員，我們將在9.3.4節(第312頁)中介紹。每個insert函數都接受一個迭代器作為其第一個參數。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一個位置。由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器開始位置插入元素是很有用的功能，所以insert函數將元素插入到迭代器所指定的位置之前。
例如，下面的語句slist.insert(iter,"Hello!");//將"Hello!添加到iter之前的位置
將一個值為"Hello"的string插入到iter指向的元素之前的位置。雖然某些容器不支持push_front操作，但它們對于insert操作并無類似的限制(插入開始位置)，比如vector。因此我們可以將元素插入到容器的開始位置，而不必擔心容器是否支持push_front：
vector<string>svec;list<string>slist;
//等價于調用slist.push_front("Hello!'*);slist.insert(slist.begin(),"Hello!");//vector不支持push_front,但我們可以插入到begin()之前
//警告：插入到vector末尾之外的任何位置都可能很慢 svec.insert(svec.begin(),"Hello!");

插入范圍內元素

除了第一個迭代器參數之外，insert函數還可以接受更多的參數，這與容器構造函數類似。其中一個版本接受一個元素數目和一個值，它將指定數量的元素添加到指定位置之前，這些元素都按給定值初始化：
svec.insert(svec.end(),10,"Anna");
這行代碼將10個元素插入到svec的末尾，并將所有元素都初始化為string"Anna"?接受一對迭代器或一個初始化列表的insert版本將給定范圍中的元素插入到指定位置之前：
vector<string>v={"quasin","simba',"frollo","nscarH");
//將v的最后兩個元素添加到slist的開始位置
slist.insert(slist.begin(),v.end()-2, v.end());
slist.insert(slist.end(),("these",“words”，"will",ngon,natn,"the",“end”});
slist.insert(slist.begin(), slist.begin(), slist.end);??/ / 運行時錯誤：迭代器表示要拷貝的范圍，不能指向與目的位置相同的容器
如果我們傳遞給insert 一對迭代器，它們不能指向添加元素的目標容器。在新標準下，接受元素個數或范圍的insert版本返回指向第一 "新加入元素的迭代器。(在舊版本的標準庫中，這些操作返回void。)如果范圍為空，不插入任何元素.insert操作會將第一個參數返回。

?使用 insert 的返回值

通過使用insert 的返回值，可以在容器中一個特定位置反復插入元素：
list<string> 1st; auto iter = 1st.begin(); while (cin ? word) iter = 1st. insert (iter, word) ; // 等價于調用 push_front
在循環之前，我們將iter初始化為lst.begin()。第一次調用insert會將我們剛剛讀入的string插入到iter所指向的元素之前的位置。insert返回的迭代器恰好指向這個新元素。我們將此迭代器賦予iter并重復循環，讀取下一個單詞。只要繼續有單詞讀入，每步while循環就會將一個新元素插入到iter之前，并將iter改變為新加入元素的位置。此元素為(新的)首元素。因此，每步循環將一個新元素插入到list首元素之前的位置。

使用emplace操作

新標準引入了三個新成員emplace_front、emplace和emplace_back這些操作構造而不是拷貝元素。這些操作分別對應push_front、insert和push_back,允許我們將元素放置在容器頭部、一個指定位置之前或容器尾部。當調用push或insert成員函數時，我們將元素類型的對象傳遞給它們，這些對象被拷貝到容器中。而當我們調用一個emplace成員函數時，則是將參數傳遞給元素類型的構造函數。
emplace成員使用這些參數在容器管理的內存空間中直接構造元素。之前的是(push_front、insert和push_back)對元素的拷貝，浪費內存。例如，假定c保存Sales_data(參見7.1.4節，第237頁)元素：
//在c的末尾構造一個Sales_data對象
c.emplace_back("978-0590353403",25,15.99);??//使用三個參數的Sales_data構造函數
c.push_back(M978-0590353403n,25,15.99);? ? ?//錯誤：沒有接受三個參數的push_back版本
c.push_back(Sales_data(H978-0590353403n,25,15.99));? ??//正確：創建一個臨時的Sales_data對象傳遞給push_back
其中對emplace_back的調用和第二個push_back調用都會創建新的Sales_data對象。在調用emplace_back時，會在容器管理的內存空間中直接創建對象。而調用push_back則會創建一個局部臨時對象，并將其壓入容器中。emplace函數的參數根據元素類型而變化，參數必須與元素類型的構造函數相匹配:
//iter指向c中一個元素，其中保存了Salesdata元素
c.emplace_back();//使用Sales_data的默認構造函數
c.emplace(iter,”999-999999999”)；//使用Sales_data(string)
//使用Sales_data的接受一個ISBN、一個count和一個price的構造函數 c.emplace_front("978-0590353403**,25,15.99);
emplace函數在容器中直接構造元素”傳遞給emplace函數的參數必須與元素類型的構造函數相匹配“

9.3.2訪問元素擊

表9.6列出了我們可以用來在順序容器中訪問元素的操作。如果容器中沒有元素，訪問操作的結果是未定義的。包括array在內的每個順序容器都有一個front成員函數，而除forward_list
之外的所有順序容器都有一個back成員函數。這兩個操作分別返回首元素和尾元素的引用：
//在解引用一個迭代器或調用front或back之前檢查是否有元素
if(!c.empty())(
//val和val_2是c中第一個元素值的拷貝
auto val=*c.begin(),val2=c.front();
//val3和va_4是c中最后一個元素值的拷貝
auto last=c.end();auto val3=*(--last);//不能遞減forward_list迭代器
auto val4=c.back();//forward_list不支持
此程序用兩種不同方式來獲取c中的首元素和尾元素的引用。直接的方法是調用front和back。而間接的方法是通過解引用begin返回的迭代器來獲得首元素的引用，以及通過遞減然后解引用end返回的迭代器來獲得尾元素的引用。
這個程序有兩點值得注意：迭代器end指向的是容器尾元素之后的(不存在的)元素。為了獲取尾元素，必須首先遞減此迭代器。另一個重要之處是，在調用front和back（或解引用begin和end返回的迭代器）之前，要確保c非空。如果容器為空，if中操作的行為將是未定義的。

訪問成員函數返回的是引用

在容器中訪問元素的成員函數（即，front、back、下標和at）返回的都是引用。如果容器是一個const對象，則返回值是const的引用。如果容器不是const的，則返回值是普通引用，我們可以用來改變元素的值：
if(!c.empty())(
c.front()=42;? ? ? ? ? ? //將42賦予c中的第一個元素
auto&v=c.back();? ? //獲得指向最后一個元素的引用? &v指向c存儲的最后一個位置空間
v=1024;? ? ? ? ? ? ? ? ? //改變c中的元素
auto v2=c.back();? ?//v2不是一個引用，它是c.back（）的一個拷貝，將c存儲的最后一個空間的數據復制一份到v2
v2=0;}? ? ? ? ? ? ? ? ? ? //未改變c中的元素
與往常一樣，如果我們使用auto變量來保存這些函數的返回值(auto只需要一個元素，不需要很多)，并且希望使用此變量來改變元素的值，必須記得將變量定義為引用類型。

下標操作和安全的隨機訪問

提供快速隨機訪問的容器（string、vector、deque和array）也都提供下標運算符（參見3.3.3節，第91頁）。就像我們已經看到的那樣，下標運算符接受一個下標參數，返問容器中該位置的元素的引用。給定下標必須"在范圍內”（即，大于等于0,且小于容器的大小）。保證下標有效是程序員的責任，下標運算符并不檢查下標是否在合法范圍內。使用越界的下標是一種嚴重的程序設計錯誤，而且編譯器并不檢查這種錯誤。
如果我們希望確保下標是合法的，可以使用at成員函數。at成員函數類似下標運算符，但如果下標越界，at會拋出一個out_of_range異常（參見5.6節，第173頁）：
vector<string>svec;//空vector
cout<<svec[0];//運行時錯誤：svec中沒有元素！
cout<<svec.at（0）;//拋出一個out_of_range異常

9.3.3刪除元素

與添加元素的多種方式類似，(非array)容器也有多種刪除元素的方式。表9.7列出了這些成員函數

pop_front和pop_back成員函數

pop_front和pop_back成員函數分別刪除首元素和尾元素。與vector和string不支持push_front一樣，這些類型也不支持pop_front。類似的，forward_list不支持pop_back。與元素訪問成員函數類似，不能對一個空容器執行彈出操作。
這些操作返回void。如果你需要彈出的元素的值，就必須在執行彈出操作之前保存它：

while(!list.empty()){process(ilist.front());// 對ilist的首個元素進行一些處理ilist.pop_front();// 完成之后刪除首個元素
}

從容器內部刪除一個元素

成員函數erase從容器中指定位置刪除元素。我們可以刪除由一個迭代器指定的單個元素，也可以刪除由一對迭代器指定的范圍內的所有元素。兩種形式的erase都返回指向刪除的(最后一個)元素之后位置的迭代器。即，若j是i之后的元素，那么erase(i)將返回指向j的迭代器，和insert相反，假設在i之前添加j，insert添加返回的是指向j的迭代器。
例如，下面的循環刪除一個list中的所有奇數元素

list <int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it : lst.begin()
while(it != lst.end()){if(*it % 2)it = lst.erase(it);else++it;
}

每個循環步中，首先檢查當前元素是否是奇數。如果是，就刪除該元素，并將it設置為我們所刪除的元素之后的元素。如果*it為偶數，我們將it遞增，從而在下一步循環檢查下一個元素。

刪除多個元素

接受一對迭代器的erase版本允許我們刪除一個范圍內的元素：
//刪除兩個迭代器表示的范圍內的元素
//返回指向最后一個被刪元素之后位置的送代器
elem1=slist.erase(elem1,elem2);//調用后，elem1==elem2
迭代器elem1指向我們要刪除的第一個元素，elem2指向我們要刪除的最后一個元素之后的位置。
為了刪除一個容器中的所有元素，我們既可以調用clear,也可以用begin和end獲得的迭代器作為參數調用erase：
slist.clear();//刪除容器中所有元素
slist.erase(slist.begin(),slist.end());//等價調用

9.3.4特殊的forwardJist操作

為了理解forward_list為什么有特殊版本的添加和刪除操作，考慮當我們從一個單向鏈表中刪除一個元素時會發生什么。如圖9.1所示，刪除一個元素會改變序列中的鏈接。
在此情況下，刪除elem3也會改變elem2,elem2原來指向elem3.但刪除elem3后，elem2指向了elem4

當添加或刪除一個元素時，刪除或添加的元素之前的那個元素的后繼會發生改變。為了添加或刪除一個元素，我們需要訪問其前驅，以便改變前驅的鏈接。但是，forward_list是單向鏈表。在一個單向鏈表中，沒有簡單的方法來獲取一個元素的前驅。出于這個原因，在一個forward_list中添加或刪除元素的操作是通過改變給定元素之后的元素來完成的。這樣，我們總是可以訪問到被添加或刪除操作所影響的元素。
由于這些操作與其他容器上的操作的實現方式不同，forward_list并未定義insert、emplace和erase,而是定義了名為insert_after、emplace_after和erase_after的操作（參見表9.8）。例如，在我們的例子中，為了刪除elem3,應該用指向elem2的迭代器調用erase_after。為了支持這些操作，forward_list也定義了before_begin,它返回一個首前（off-the-beginning）迭代器。這個迭代器允許我們在鏈表首元素之前并不存在的元素"之后”添加或刪除元素（亦即在鏈表首元素之前添加刪除元素）。

當在forward_list中添加或刪除元素時，我們必須關注兩個迭代器-----個指向我們要處理的元素，另一個指向其前驅。例如，可以改寫第312頁中從list中刪除奇數元素的循環程序，將其改為從forward_list中刪除元素：

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // 表示flst的首前元素
auto curr = flst.begin() ;//表示flst的第一個元素while(curr != flst.end){if(*flst % 2)curr = flst.erase_after(prev);else{prev = curr;//移動迭代器curr 指向下一個元素 prev 指向curr之前的元素++curr;}
}

此例中，curr表示我們要處理的元素，prev表示curr的前驅。調用begin來初始化curr,這樣第一步循環就會檢查第一個元素是否是奇數。我們用before_begin來初始化prev,它返回指向curr之前不存在的元素的迭代器。當找到奇數元素后，我們將prev傳遞給erase_after,此調用將prev之后的元素刪除，即，刪除curr指向的元素。然后我們將curr重置為erase_after的返回值,使得curr指向序列中下一個元素，prev保持不變，仍指向(新)curr之前的元素。如果curr指向的元素不是奇數，在else中我們將兩個迭代器都向前移動。

9.3.5改變容器大小

如表9.9所描述，我們可以用resize來增大或縮小容器，與往常一樣，array不支持resize。如果當前大小大于所要求的大小，容器后部的元素會被刪除；如果當前大小小于新大小，會將新元素添加到容器后部：
list<int>ilist(10,42);//10個int：每個的值都是42
ilist.resize(15);//將5個值為0的元素添加到ilist的末尾
ilist.resize(25,-1);//將10個值為的元素添加到ilist的末尾從ilist末尾
ilist.resize(5);//刪除20個元素
resize操作接受一個可選的元素值參數，用來初始化添加到容器中的元素。如果調用者未提供此參數，新元素進行值初始化(參見3.3.1節，第88頁)。如果容器保存的是類類型元素，且resize向容器添加新元素，則我們必須提供初始值，或者元素類型必須提供一個默認構造函數

9.3.6容器操作可能使迭代器失效

向容器中添加元素和從容器中刪除元素的操作可能會使指向容器元素的指針、引用或迭代器失效。一個失效的指針、引用或迭代器將不再表示任何元素。使用失效的指針、引用或迭代器是一種嚴重的程序設計錯誤，很可能引起與使用未初始化指針一樣的問題（參見2.3.2節，第49頁）

在向容器添加元素后：

如果容器是vector或string,且存儲空間被重新分配，則指向容器的迭代器、指針和引用都會失效（空間重新分配，比如當前空間太小了，增大空間，但是空間不足，需要將整個容器移到別的地方重新開辟，指向先前的地址的迭代器、指針和引用就會失效）。如果存儲空間未重新分配，指向插入位置之前的元素的迭代器、指針和引用仍有效，但指向插入位置之后元素的迭代器、指針和引用將會失效（和前面一樣，如果增大的空間不是很大，在原有的空間后面追加開辟空間，先前的仍然保留）。
對于deque,插入到除首尾位置之外的任何位置都會導致迭代器、指針和引用失效。如果在首尾位置添加元素，迭代器會失效，但指向存在的元素的引用和指針不會失效。
對于list和forward_list,指向容器的迭代器（包括尾后迭代器和首前迭代器）、指針和引用仍有效。
當我們從一個容器中刪除元素后，指向被刪除元素的迭代器、指針和引用會失效，這應該不會令人驚訝。畢竟，這些元素都已經被銷毀了。當我們刪除一個元素后：
對于list和forward_list,指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指針仍有效。
對于deque,如果在首尾之外的任何位置刪除元素，那么指向被刪除元素外其他元素的迭代器、引用或指針也會失效。如果是刪除deque的尾元素，則尾后迭代器也會失效，但其他迭代器、引用和指針不受影響；如果是刪除首元素，這些也不會受影響。
對于vector和string,指向被刪元素之前元素的迭代器、引用和指針仍有效。注意：當我們刪除元素時，尾后迭代器總是會失效。
因此必須保證每次改變容器的操作之后都正確地重新定位迭代器。這個建議對vector、string和deque尤為重要。

編寫改變容器的循環程序

添加/刪除vector、string或deque元素的循環程序必須考慮迭代器、引用和指針可能失效的問題。程序必須保證每個循環步中都更新迭代器、引用或指針。如果循環中調用的是insert或erase,那么更新迭代器很容易。這些操作都返回迭代器，我們可以用來更新：

//傻瓜循環 刪除偶數元素 復制每個奇數元素
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();//使用begin，而不是cbegin，因為需要改變元素
while(iter != vi.end){if(*iter % 2){iter = vi.insert(iter,*iter);//復制當前元素iter += 2;//跳過當前元素 以及插入到他之前的元素}else{iter = vi.erase(iter);//刪除偶數元素//不需要移動迭代器 iter刪除元素之后 指向刪除元素之后的元素}
}

此程序刪除vector中的偶數值元素，并復制每個奇數值元素。我們在調用insert和 erase后都更新迭代器，因為兩者都會使迭代器失效。在調用erase后，不必遞增迭代器，因為erase返回的迭代器已經指向序列中下一個元素。調用insert后，需要遞增迭代器兩次。記住，insert在給定位置之前插入新元素，然后返回指向新插入元素的迭代器。因此，在調用insert后，iter指向新插入元素，位于我們正在處理的元素之前。我們將迭代器遞增兩次，恰好越過了新添加的元素和正在處理的元素，指向下一個未處理的元素。

不要保存end返回的迭代器

當我們添加/刪除vector或 string的元素后，或在deque中首元素之外任何位置添加/刪除元素后，原來end返回的迭代器總是會失效。因此，添加或刪除元素的循環程序必須反復調用end,而不能在循環之前保存end返回的迭代器，一直當作容器末尾使用。通常C++標準庫的實現中end()操作都很快，部分就是因為這個原因。例如，考慮這樣一個循環，它處理容器中的每個元素，在其后添加一個新元素。我們希望循環能跳過新添加的元素，只處理原有元素。在每步循環之后，我們將定位迭代器，使其指向下一個原有元素。如果我們試圖“優化”這個循環，在循環之前保存end ()返回的迭代器，一直用作容器末尾，就會導致一場災難：

//災難 此循環的行為是未定義的
auto begin = v.begin();
auto end = v.end(); //保存尾迭代器的數值是一個壞主意
while(begin != end){//做一些處理//傳入新值，對begin進行重新賦值 否則他會失效++begin;// 向前移動begin 因為我們想在這個元素之后插入元素begin = v.insert(begin,42);++begin;//向前移動，跳過新加入的元素
}

此代碼的行為是未定義的。在很多標準庫實現上，此代碼會導致無限循環。問題在于我們將 end操作返回的迭代器保存在一個名為end的局部變量中。在循環體中，我們向容器中添加了一個元素，這個操作使保存在end中的迭代器失效了。這個迭代器不再指向v 中任何元素，或是v 中尾元素之后的位置。
如果在一個循環中插入/刪除deque、string或vector中的元素，不要緩存end返回的迭代器。必須在每次插入操作后重新調用end(),而不能在循環開始前保存它返回的迭代器：

//更安全的做法是 每個循環添加/刪除元素之后 都重新計算end
while(begin != end){++begin();// 向前移動begin 因為想在此元素之后插入元素begin = v.insert(begin,42);//插入新值++begin;//向前移動begin 跳過新加入的元素
}