一個容器就是一些特定類型對象的集合。順序容器(sequentialcontainer)為程序員提供了控制元素存儲和訪問順序的能力。這種順序不依賴于元素的值，而是與元素加入容器
時的位置相對應。與之相對的，我們將在第11章介紹的有序和無序關聯容器，則根據關鍵字的值來存儲元素。
標準庫還提供了三種容器適配器，分別為容器操作定義了不同的接口，來與容器類型適配。我們將在本章末尾介紹適配器。

9.1順序容器概述

表9.1列出了標準庫中的順序容器，所有順序容器都提供了快速順序訪問元素的能力。但是，這些容器在以下方面都有不同的性能折中：
向容器添加或從容器中刪除元素的代價
非順序訪問容器中元素的代價

除了固定大小的array外，其他容器都提供高效、靈活的內存管理。我們可以添加和刪除元素，擴張和收縮容器的大小。容器保存元素的策略對容器操作的效率有著固有的，有時是重大的影響。在某些情況下，存儲策略還會影響特定容器是否支持特定操作。
例如，string和vector將元素保存在連續的內存空間中。由于元素是連續存儲的，由元素的下標來計算其地址是非常快速的。但是，在這兩種容器的中間位置添加或刪除元素就會非常耗時：在一次插入或刪除操作后，需要移動插入/刪除位置之后的所有元素，來保持連續存儲。而且，添加一個元素有時可能還需要分配額外的存儲空間。在這種情況下，每個元素都必須移動到新的存儲空間中。
list和forward_list兩個容器的設計目的是令容器任何位置的添加和刪除操作都很快速。作為代價，這兩個容器不支持元素的隨機訪問：為了訪問一個元素，我們只能遍歷整個容器。而且，與vector、deque和array相比，這兩個容器的額外內存開銷也很大。
deque是一個更為復雜的數據結構。與string和vector類似，deque支持快速的隨機訪問。與string和vector一樣’在deque的中間位置添加或刪除兀素的代價（可能）很高。但是，在deque的兩端添加或刪除元素都是很快的，與list或forward_list添加刪除元素的速度相當。
forward_list和array是新C++標準增加的類型。與內置數組相比，array是一種更安全、更蓉易使用的數組類型。與內置數組類似，array對象的大小是固定的。因此，言array不支持添加和刪除元素以及改變容器大小的操作。forward_list的設計目標是達到與最好的手寫的單向鏈表數據結構相當的性能。因此，forward_list沒有size操作，因為保存或計算其大小就會比手寫鏈表多出額外的開銷。對其他容器而言，size保證是一個快速的常量時間的操作
通常，使用vector是最好的選擇，除非你有很好的理由選擇其他容器
以下是一些選擇容器的基本原則:
除非你有很好的理由選擇其他容器，否則應使用vector0
如果你的程序有很多小的元素，且空間的額外開銷很重要，則不要使用list或forward_list
如果程序要求隨機訪問元素，應使用vector或deque。
如果程序要求在容器的中間插入或刪除元素，應使用list或forward_list
如果程序需要在頭尾位置插入或刪除元素，但不會在中間位置進行插入或刪除操作，則使用dequeo
如果程序只有在讀取輸入時才需要在容器中間位置插入元素，隨后需要隨機訪問元素，則首先，確定是否真的需要在容器中間位置添加元素。當處理輸入數據時，通常可以很容易地向vector追加數據，然后再調用標準庫的sort函數（我們將在10.2.3節介紹sort（第343頁））來重排容器中的元素，從而避免在中間位置添加元素。如果必須在中間位置插入元素，考慮在輸入階段使用list,一旦輸入完成，將list中的內容拷貝到一個vector中。
如果程序既需要隨機訪問元素，又需要在容器中間位置插入元素，那該怎么辦？答案取決于在list或forward_list中訪問元素與vector或deque中插入/刪除元素的相對性能。一般來說，應用中占主導地位的操作（執行的訪問操作更多還是插入/刪除更多）決定了容器類型的選擇。在此情況下，對兩種容器分別測試應用的性能可能就是必要的了。
如果你不確定應該使用哪種容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下標操作，避免隨機訪問。這樣，在必要時選擇使用vector或list都很方便

9.2容器庫概覽

容器類型上的操作形成了一種層次：
某些操作是所有容器類型都提供的（參見表9.2,第295頁）。
另外一些操作僅針對順序容器（參見表9.3,第299頁）、關聯容器（參見表11.7,第388頁）或無序容器（參見表11.8,第395頁）。
還有一些操作只適用于一小部分容器。
在本節中，我們將介紹對所有容器都適用的操作。本章剩余部分將聚焦于僅適用于順序容器的操作。關聯容器特有的操作將在第11章介紹。
一般來說，每個容器都定義在一個頭文件中，文件名與類型名相同。即，deque定義在頭文件deque中，list定義在頭文件list中，以此類推。容器均定義為模板類（參見3.3節，第86頁）。例如對vector,我們必須提供額外信息來生成特定的容器類型。對大多數，但不是所有容器，我們還需要額外提供元素類型信息：
list<Sales_data>//保存Sales_data對象的list
deque<double>//保存double的deque

對容器可以保存的元素類型的限制

順序容器幾乎可以保存任意類型的元素。特別是，我們可以定義一個容器，其元素的類型是另一個容器。這種容器的定義與任何其他容器類型完全一樣：在尖括號中指定元素
類型（此種情況下，是另一種容器類型）：
vector<vector<string>>Lines;//vector的vector? ? ? 此處lines是一個vector,其元素類型是string的vector。
雖然我們可以在容器中保存幾乎任何類型，但某些容器操作對元素類型有其自己的特殊要求。我們可以為不支持特定操作需求的類型定義容器，但這種情況下就只能使用那些沒有特殊要求的容器操作了。
例如，順序容器構造函數的一個版本接受容器大小參數（參見3.3.1節，第88頁），它使用了元素類型的默認構造函數。但某些類沒有默認構造函數。我們可以定義一個保存這種類型對象的容器，但我們在構造這種容器時不能只傳遞給它一個元素數目參數：
假定noDefault是一個沒有默認構造函數的類型
vector<noDefault> vl （10, init） ; // 正確：提供了元素初始化器
vector<noDefault> v2 （10） ; / / 錯誤：必須提供一個元素初始化器
當后面介紹容器操作時，我們還會注意到每個容器操作對元素類型的其他限制。

9.2.1迭代器

與容器一樣，迭代器有著公共的接口：如果一個迭代器提供某個操作，那么所有提供相同操作的迭代器對這個操作的實現方式都是相同的。例如，標準容器類型上的所有迭代器都允許我們訪問容器中的元素，而所有迭代器都是通過解引用運算符來實現這個操作的。類似的，標準庫容器的所有迭代器都定義了遞增運算符，從當前元素移動到下一個元素。
表3.6（第96頁）列出了容器迭代器支持的所有操作，其中有一個例外不符合公共接口特點一forward_list迭代器不支持遞減運算符（--）。表3.7（第99頁）列出了迭代器支持的算術運算，這些運算只能應用于string、vector、deque和array的迭代器。我們不能將它們用于其他任何容器類型的迭代器。
一個迭代器范圍（iteratorrange）由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者是尾元素之后的位置（onepastthelastelement）這兩個迭代器通常被稱為begin和end,或者是first和last（可能有些誤導），它們標記了容器中元素的一個范圍。雖然第二個迭代器常常被稱為last,但這種叫法有些誤導，因為第二個迭代器從來都不會指向范圍中的最后一個元素，而是指向尾元素之后的位置。迭代器范圍中的元素包含first所表示的元素以及從first開始直至last（但不包含last）之間的所有元素。這種元素范圍被稱為左閉合區間。其標準數學描述為[begin,end）。表示范圍自begin開始，于end之前結束。迭代器begin和end必須指向相同的容器。end可以與begin指向相同的位置，但不能指向begin之前的位置。

對構成范圍的迭代器的要求

如果滿足如下條件，兩個迭代器begin和end構成一個迭代器范圍。它們指向同一個容器中的元素，或者是容器最后一個元素之后的位置，且我們可以通過反復遞增begin來到達end。換句話說，end不在begin之前。

使用左閉合范圍蘊含的編程假定

標準庫使用左閉合范圍是因為這種范圍有三種方便的性質。假定begin和end構成一個合法的迭代器范圍，則
如果begin與end相等，則范圍為空
如果begin與end不等，則范圍至少包含一個元素，且begin指向該范圍中的第一個元素
我們可以對begin遞增若干次，使得begin=end
這些性質意味著我們可以像下面的代碼一樣用一個循環來處理一個元素范圍，而這是安全的：
while(begin!=end){*begin=val;//正確：范圍非空，因此begin指向一個元素
++begin;//移動迭代器，獲取下一個元素}
給定構成一個合法范圍的迭代器begin和end,若begin=end,則范圍為空。在此情況下，我們應該退出循環。如果范圍不為空，begin指向此非空范圍的一個元素。因此，在while循環體中，可以安全地解引用begin,因為begin必然指向一個元素。最后，由于每次循環對begin遞增一次，我們確定循環最終會結束。

9.2.2容器類型成員

每個容器都定義了多個類型，如表9.2所示(第295頁)。我們已經使用過其中三種：sizetype(參見3.2.2節，第79頁)、iterator和const_iterator(參見3.4.1節，第97頁)。
除了已經使用過的迭代器類型，大多數容器還提供反向迭代器。簡單地說，反向迭代器就是一種反向遍歷容器的迭代器，與正向迭代器相比，各種操作的含義也都發生了顛倒。
例如，對一個反向迭代器執行++操作，會得到上一個元素。
剩下的就是類型別名了，通過類型別名，可以在不了解容器中元素類型的情況下使用它。(類型別名類似typedef，將一個使用多個容器嵌套而成的自定義的類型起一個統一的名字，都叫value_type)如果需要元素類型，可以使用容器的value_type。如果需要元素類型的一個引用，可以使用reference或const_:refe:rence。這些元素相關的類型別名在泛型編程中非常有用
為了使用這些類型，我們必須顯式使用其類名：
list<string>::iterator iter;? ? ? ?//iter是通過list<string>定義的一個迭代器類型? ? ? ? operator 如< <= > >=
vector<int>::difference_type count;? ? ?//count是通過vector<int>定義的一個difference_type類型? ? ? 容器內，兩個元素之間的距離差值；it2 - it1返回值為difference_type
參考鏈接?https://blog.csdn.net/pzhw520hchy/article/details/80368869??
這些聲明語句使用了作用域運算符（參見1.2節，第7頁）來說明我們希望使用list<string>類的iterator成員及vector<int>類定義的difference_type

9.2.3begin和end成員

begin和end操作（參見341節，第95頁）生成指向容器中第一個元素和尾元素之后位置的迭代器。這兩個迭代器最常見的用途是形成一個包含容器中所有元素的迭代器范圍。
如表9.2（第295頁）所示，begin和end有多個版本：帶r的版本返回反向迭代器（我們將在10.4.3節（第363頁）中介紹相關內容）；以c開頭的版本則返回const迭代器：
list<string>a=（"Milton","Shakespeare","Austen"};
auto itl=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
不以c開頭的函數都是被重載過的。也就是說，實際上有兩個名為begin的成員。一個是const成員（參見7.1.2節，第231頁），返回容器的const_iterator類型。另一個是非常量成員，返回容器的iterator類型。rbegin,end和rend的情況類似。當我們對一個非常量對象調用這些成員時，得到的是返回iterator的版本。只有在對一個const對象調用這些函數時，才會得到-個const版本。與const指針和引用類似,可以將一個普通的iterator轉換為對應的const_iterator，但反之不行。
以c開頭的版本是C++新標準引入的，用以支持auto（參見2.5.2節，第61頁）與begin和end函數結合使用。過去，沒有其他選擇，只能顯式聲明希望使用哪種類型的迭代器：
//顯式指定類型
list<string>::iterator it5=a.begin();
list<string>::const_iterator it6=a.begin（）;//是iterator還是const_iterator依賴于a的類型
auto it7=a.begin（）;//僅當a是const時，是const_iterator
auto it8=a.cbegin（）;//it8是const_iterator
當auto與begin或end結合使用時，獲得的迭代器類型依賴于容器類型，與想要如何使用迭代器毫不相干。但以c開頭的版本還是可以獲得const_iterator的，而不管容器的類型是什么
當不需要寫訪問時，應使用cbegin 和 cend? ? ? ?這個不對元素進行更改，僅僅是訪問

9.2.4容器定義和初始化咆

每個容器類型都定義了一個默認構造函數（參見7.1.4節，第236頁）。除array之外，其他容器的默認構造函數都會創建一個指定類型的空容器，且都可以接受指定容器大小和元素初始值的參數

C c1 = c2;//拷貝初始化
C c1(c2);//賦值初始化

將一個容器初始化為另一個容器的拷貝

將一個新容器創建為另一個容器的拷貝的方法有兩種：可以直接拷貝整個容器，或者（array除外）拷貝由一個迭代器對指定的元素范圍。
為了創建一個容器為另一個容器的拷貝，兩個容器的類型及其元素類型必須匹配。不過，當傳遞迭代器參數來拷貝一個范圍時，就不要求容器類型是相同的了。而且，新容器和原容器中的元素類型也可以不同，只要能將要拷貝的元素轉換（參見4.11節，第 141頁）為要初始化的容器的元素類型即可。
//每個容器有三個元素，用給定的初始化器進行初始化
list<string>authors=（"Milton'*,"Shakespeare**,"Austen**};
vector<const char*>articles={"a","an”，"the”};
list<string>list2(authors);//正確??類型匹配
deque<string>authList(authors);//錯誤? ?容器類型不匹配
vector<string>words(articles);//錯誤? ??容器類型必須匹配
forward_list<string>words(articles.begin(),articles.end());//正確：可以將const char*元素轉換為string
當將一個容器初始化為另一個容器的拷貝時，兩個容器的容器類型和元素類型都必須相同
接受兩個迭代器參數的構造函數用這兩個迭代器表示我們想要拷貝的一個元素范圍。與以往一樣，兩個迭代器分別標記想要拷貝的第一個元素和尾元素之后的位置。新容器的大小與范圍中元素的數目相同。新容器中的每個元素都用范圍中對應元素的值進行初始化。
由于兩個迭代器表示一個范圍，因此可以使用這種構造函數來拷貝一個容器中的子序列。例如，假定迭代器it表示authors中的一個元素，我們可以編寫如下代碼
//拷貝元素，直到（但不包括）it指向的元素
deque<string>authList（authors.begin（）,it）;? ?

列表初始化

在新標準中，我們可以對一個容器進行列表初始化（參見3.3.1節，第88頁）
//每個容器有三個元素，用給定的初始化器進行初始化
list<string>authors=（nMiltonn,"Shakespeare",''Austen"};
vector<constchar*>articles={"a”，"an","the"};
當這樣做時，我們就顯式地指定了容器中每個元素的值。對于除array之外的容器類型,初始化列表還隱含地指定了容器的大小：容器將包含與初始值一樣多的元素。

與順序容器大小相關的構造函數

除了與關聯容器相同的構造函數外，順序容器（array除外）還提供另一個構造函數,它接受一個容器大小和一個（可選的）元素初始值。如果不提供元素初始值，則標準庫會創建一個值初始化器（參見3.3.1節，第88頁）
vector<int>ivec(10,-1)；??//10個int元素，每個都初始化為-1
list<string>svec(10,"hi!");? ?//10個strings:每個都初始化為"hi!”
forward_list<int>ivec(10);? ?//10個元素，每個都初始化為0
deque<string>svec(10);??//10個元素，每個都是空string
如果元素類型是內置類型或者是具有默認構造函數（參見9.2節，第294頁）的類類型，可以只為構造函數提供一個容器大小參數。如果元素類型沒有默認構造函數，除了大小參數外，還必須指定一顯式的元素初始值。
有順序容器的構造函數才接受大小參數，關聯容器并不支持

標準庫array具有固定大小

與內置數組一樣，標準庫array的大小也是類型的一部分。當定義一個array時，除了指定元素類型，還要指定容器大小：
array<int,42>//類型為：保存42個int的數組
array<string,10>//類型為：保存10個string的數組
為了使用array類型，我們必須同時指定元素類型和大小：
array<int,10>::size_type i;//數組類型包括元素類型和大小
array<int>::size_typej;//錯誤：array<int>不是一個類型
由于大小是array類型的一部分，array不支持普通的容器構造函數。這些構造函數都會確定容器的大小，要么隱式地，要么顯式地。而允許用戶向一個array構造函數傳遞大小參數，最好情況下也是多余的，而且容易出錯。
array大小固定的特性也影響了它所定義的構造函數的行為。與其他容器不同，一個默認構造的array是非空的：它包含了與其大小一樣多的元素。這些元素都被默認初始化（參見2.2.1節，第40頁），就像一個內置數組（參見3.5.1節，第102頁）中的元素那樣。如果我們對array進行列表初始化，初始值的數目必須等于或小于array的大小。如果初始值數目小于array的大小，則它們被用來初始化array中靠前的元素，所有剩余元素都會進行值初始化（參見3.3.1節，第88頁）。在這兩種情況下，如果元素類型是一個類類型，那么該類必須有一個默認構造函數，以使值初始化能夠進行：
array<int,10>ial;//10個默認初始化的int
array<int,10>ia2={0,1,2,3,4,5,6,7,8,9）;//列表初始化
array<int,10>ia3={42};//ia3[0]為42,剩余元素為0
值得注意的是，雖然我們不能對內置數組類型進行拷貝或對象賦值操作（參見3.5.1節，第102頁），但array并無此限制：
int digs[10]={0,1,2,3,4,5,6,7,8,9};
intcpy[10]=digs;//錯誤：內置數組不支持拷貝或賦值
array<int,10>digits={0,1,2,3,4,5,6,7,8,9};
array<int,10>copy=digits;//正確:只要數組類型匹配即合法
與其他容器一樣,array也要求初始值的類型必須與要創建的容器類型相同。此外,array還要求元素類型和大小也都一樣，因為大小是array類型的一部分。

9.2.5賦值和swap

表9.4中列出的與賦值相關的運算符可用于所有容器。賦值運算符將其左邊容器中的全部元素替換為右邊容器中元素的拷貝：
cl=c2;//將cl的內容替換為c2中元素的拷貝
cl=（a,b,c）;//賦值后，cl大小為3
第一個賦值運算后，左邊容器將與右邊容器相等。如果兩個容器原來大小不同，賦值運算后兩者的大小都與右邊容器的原大小相同。第二個賦值運算后，cl的size變為3,即花括號列表中值的數目
與內置數組不同，標準庫array類型允許賦值。賦值號左右兩邊的運算對象必須具有相同的類型：
array<int,10>al={0,1,2,3,4,5,6,7,8,9};
array<int,10>a2={0};//所有元素值均為0
al=a2;//替換al中的元素
a2={0};//錯誤：不能將一個花括號列表賦予數組
由于右邊運算對象的大小可能與左邊運算對象的大小不同，因此array類型不支持assign,也不允許用花括號包圍的值列表進行賦值

vector::assign()? ?用來構造一個vector函數，類似于copy函數

使用assign（僅順序容器）

賦值運算符要求左邊和右邊的運算對象具有相同的類型。它將右邊運算對象中所有元素拷貝到左邊運算對象中。順序容器（array除外）還定義了一個名為assign的成員，允許我們從一個不同但相容的類型賦值，或者從容器的一個子序列賦值。assign操作用參數所指定的元素（的拷貝）替換左邊容器中的所有元素。例如，我們可以用assgin實現將一個vector中的一段char*值賦予一個list中的string：
list<string>names;
vector<const char*>oldstyle;
names=oldstyle;//錯誤：容器類型不匹配
names.assign(oldstyle.cbegin(),oldstyle.cend());??//正確：可以將const char*轉換為string
這段代碼中對assign的調用將names中的元素替換為迭代器指定的范圍中的元素的拷貝。assign的參數決定了容器中將有多少個元素以及它們的值都是什么。
由于其舊元素被替換，因此傳遞給assign的迭代器不能指向調用assign的容器
assign的第二個版本接受一個整型值和一個元素值。它用指定數目旦具有相同給定值的元素替換容器中原有的元素：
// 等價于 slistl. clear ();
// 后跟slistl. insert (slistl. begin () , 10, "Hiya ! n );
list<string> slistl (1) ; // 1 個元素，為空
string slistl .assign (10, "Hiya"?) ; // 10 個元素，每個都是 "Hiya!”

使用swap

swap操作交換兩個相同類型容器的內容。調用swap之后，兩個容器中的元素將會交換；
vector<string>svecl(10);//10個元素的vector
vector<string>svec2(24);//24個元素的vector
swap(svecl,svec2);
調用swap后，svecl將包含24個string元素,svec2將包含10個string。除array外，交換兩個容器內容的操作保證會很快--元素本身并未交換，swap只是交換了兩個容器的內部數據結構。
除array外，swap不對任何元素進行拷貝、刪除或插入操作，因此可以保證在常數時間內完成
元素不會被移動的事實意味著，除string外，指向容器的迭代器、引用和指針在swap操作之后都不會失效。它們仍指向swap操作之前所指向的那些元素。但是，在swap之后，這些元素已經屬于不同的容器了。例如，假定iter在swap之前指向svecl[3]的string,那么在swap之后它指向svec2[3]的元素。與其他容器不同，對一個string調用swap會導致迭代器、引用和指針失效。與其他容器不同，swap兩個array會真正交換它們的元素。因此，交換兩個array所需的時間與array中元素的數目成正比。
因此，對于array,在swap操作之后，指針、引用和迭代器所綁定的元素保持不變,但元素值已經與另一個array中對應元素的值進行了交換。在新標準庫中，容器既提供成員函數版本的swap,也提供非成員版本的swap。而早期標準庫版本只提供成員函數版本的swap。非成員版本的swap在泛型編程中是非常重要的。統一使用非成員版本的swap是一個好習慣。

9.2.6容器大小操作

除了一個例外，每個容器類型都有三個與大小相關的操作。成員函數size（參見3.2.2節，第78頁）返回容器中元素的數目；empty當size為0時返回布爾值true,否則返回false；max_size返回一個大于或等于該類型容器所能容納的最大元素數的值。
forward_list支持max_size和empty,但不支持size,原因我們將在下一節解釋。

9.2.7關系運算符

每個容器類型都支持相等運算符（==和!=）；除了無序關聯容器外的所有容器都支持關系運算符（＞、＞=、＜、＜=）。關系運算符左右兩邊的運算對象必須是相同類型的容器，且必須保存相同類型的元素。即，我們只能將一個vector＜int＞與另一個vector＜int＞進行比較，而不能將一個vector＜int＞與一個list＜int＞或一個vector＜double＞進行比較。
比較兩個容器實際上是進行元素的逐對比較。這些運算符的工作方式與string的關系運算（參見3.2.2節，第79頁）類似：
如果兩個容器具有相同大小且所有元素都兩兩對應相等，則這兩個容器相等；否則兩個容器不等。
如果兩個容器大小不同，但較小容器中每個元素都等于較大容器中的對應元素，則較小容器小于較大容器。
如果兩個容器都不是另一個容器的前綴子序列，則它們的比較結果取決于第一個不相等的元素的比較結果。
下面的例子展示了這些關系運算符是如何工作的：

容器的關系運算符使用元素的關系運算符完成比較

只有當其元素類型也定義了相應的比較運算符時，我們才可以使用關系運算符來比較兩個容器
容器的相等運算符實際上是使用元素的==運算符實現比較的，而其他關系運算符是使用元素的運算符。如果元素類型不支持所需運算符，那么保存這種元素的容器就不能使用相應的關系運算。例如，我們在第7章中定義的Sales_data類型并未定義==和〈運算。因此，就不能比較兩個保存Salesdata元素的容器