9.6容器適配器

除了順序容器外，標準庫還定義了三個順序容器適配器：stack、queue和priority_queue
適配器(adaptor)是標準庫中的一個通用概念。容器、迭代器和函數<369I
都有適配器。本質上，一個適配器是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型。
例如，stack適配器接受一個順序容器(除array或forward_list外)，并使其操作起來像一個stack一樣(外層包裝)。表9.17列出了所有容器適配器都支持的操作和類型。

定義一個適配器

每個適配器都定義兩個構造函數：默認構造函數創建一個空對象，接受一個容器的構造函數拷貝該容器來初始化適配器。例如，假定deq是一個deque<int>,我們可以用deq來初始化一個新的stack,如下所示：
stack<int>stk(deq);//從deq拷貝元素到stk
默認情況下，stack和queue是基于deque實現的，priority_queue是在vector之上實現的。我們可以在創建一個適配器時將-個命名的順序容器作為第二個類型參數，來重載默認容器類型。
//在vector_h實現的空棧
stack<string,vector<string>> str_stk;
stack<string,vector<string>>str_stk2(svec);? ?//str_stk2在vector上實現，初始化時保存svec的拷貝
對于一個給定的適配器，可以使用哪些容器是有限制的。所有適配器都要求容器具有添加和刪除元素的能力。因此，適配器不能構造在array之上。類似的，我們也不能用forward_list來構造適配器，因為所有適配器都要求容器具有添加、刪除以及訪問尾元素的能力。
stack只要求push_back、pop_back和back操作，因此可以使用除array和forward_list之外的任何容器類型來構造stack。
queue適配器要求back、push_back、front和push_front,因此它可以構造于list或deque之上，但不能基于vector構造。
priority_queue除了front、push_back和pop_back操作之外還要求隨機訪問能力，因此它可以構造于vector或deque之上，但不能基于list構造。

棧適配器

stack類型定義在stack頭文件中。表 9.18列出了 stack所支持的操作。下面的程序展示了如何使用stack：
stack<int> intStack; // 空棧
/ / 填滿棧
for (size_t ix = 0; ix != 10; ++ix)
intStack.push (ix) ; // intStack 保存 0 到 9 十個數
while (! intStack. empty () ) ( // intStack 中有值就繼續循環
int value = intStack.top();
/ / 使用棧頂值的代碼
intStack.pop () ; / / 彈出棧頂元素，繼續循環
}
其中，聲明語句
stack<int> intStack; // 空棧
定義了一個保存整型元素的棧intStack,初始時為空。for循環將10個元素添加到棧中，這些元素被初始化為從0 開始連續的整數。while循環遍歷整個stack,獲取top 值，將其從棧中彈出，直至棧空。

每個容器適配器都基于底層容器類型的操作定義了自己的特殊操作。我們只可以使用適配器操作，而不能使用底層容器類型的操作。例如，
intStack.push(ix);//intStack保存0到9十個數
此語句試圖在intStack的底層deque對象上調用push_back
雖然stack是基于deque實現的，但我們不能直接使用deque操作。不能在一個stack調用push_back,而必須使用stack自己的操作push

隊列適配器

queue和 priority_queue適配器定義在queue頭文件中。表 9.19列出了它們所支持的操作。

標準庫queue使用一種先進先出（first-in,first-out,FIFO）的存儲和訪問策略。進入隊列的對象被放置到隊尾，而離開隊列的對象則從隊首刪除。飯店按客人到達的順序來為他們安排座位，就是一個先進先出隊列的例子。
priority_queue允許我們為隊列中的元素建立優先級。新加入的元素會排在所有優先級比它低的已有元素之前。飯店按照客人預定時間而不是到來時間的早晚來為他們安排座位，就是一個優先隊列的例子。默認情況下，標準庫在元素類型上使用〈運算符來確定相對優先級。我們將在11.2.2節（第378頁）學習如何重載這個默認設置。

小結

標準庫容器是模板類型，用來保存給定類型的對象。在一個順序容器中，元素是按順序存放的，通過位置來訪問。順序容器有公共的標準接口：如果兩個順序容器都提供一個特定的操作，那么這個操作在兩個容器中具有相同的接口和含義。
所有容器（除arrav外）都提供高效的動態內存管理。我們可以向容器中添加元素，不必擔心元素存儲在哪里。容器負責管理自身的存儲。vector和string都提供更細致的內存管理控制，這是通過它們的reserve和capacity成員函數來實現的.
很大程度，容器只定義了極少的操作。每個容器都定義了構造函數、添加和刪除元素的操作、確定容器大小的操作以及返回指向特定元素的迭代器的操作。其他一些有用的操作，如排序或搜索，并不是由容器類型定義的，而是由標準庫算法實現的，我們將在第I0章介紹這些內容。
當我們使用添加和刪除元素的容器操作時，必須注意這些操作町能使指向容器中元素的迭代器、指針或引用失效。很多會使迭代器失效的操作，如insert和erase,都會返回一個新的迭代器，來帶助程序員維護容器中的位置。如果循環程序中使用了改變容器大小的操作，就要尤其小心其中迭代器、指針和引用的使用。

術語表

適配器（adaptor）標準陣類型、函數或送代器，它們接受一個類型、函數或迭代器，使其行為像另外一個類型、函數或迭代器-樣。標準應提供了：一種順序容器適配器：stack,queue和priority_queue每個適配器都在其底層順序容器類型之上定義了一個新的接口。
數組（array）固定大小的順序容器。為了定義一個array,除了元素類型之外還必須給定大小.array中的元素可以用其位置下標來訪問。array支持快速的隨機訪問
begin容器操作，返回個指向容器首元素的迭代器，如果容器為空，則返回尾后迭代器。是否返回const迭代器依賴于容器的類型。
cbegin容器操作，返回一個指向容器首元素的const_iterator,如果容器為空，則返回尾后迭代器
cend容器操作，返回個指向容器尾元素之后（不存在:的）的const_iterator.
容器 container 保存-組給定類型對象的類型。每個標準庫容器類型都是一個模板類型。為了定義一個容器，我們必須指定保存在容器中的元素的類型。除了array之外，標準庫容器都是大小可變的。
deque順序容器。deque中的元素可以通過位置下標來訪問。支持快速的隨機訪問。deque各方面都和vector類似,唯一的差別是，deque支持在容器頭尾位置的快速插入和刪除，而目.在兩端插入或刪除元素都不會導致重新分配空間.
end容器操作，返回-個指向容器尾元素之后（不存在的）元素的迭代器。是否返回const迭代器依賴于容器的類型
forward_ist順序容器，表示一個單向鏈表。forward_listr的元素只能順序訪問。從一個給定元素開始，為了訪問另-個元素，我們只能遍歷兩者之間的所有元素。forward_list上的迭代器不支持遞減運算（一）.forward_list支持任意位置的快速插入（或刪除）操作。與其他容器不同，插入和刪除發生在一個給定的迭代器之后的位置。因此，除了通常的尾后迭代器之外，forward_list還有一個“首前”迭代器。在添加新元素后，原有的指向forward_list的迭代器仍有效。在刪除元素后，只有原來指向被刪元素的迭
代器才會失效。
迭代器范圍（iteratorrange）由一對迭代器指定的元素范圍。第一個迭代器表示序列中第一個元素，第二個迭代器指向最后-個元素之后的位置。如果范圍為空，則兩個迭代器是相等的（反之亦然，如果兩個迭代器不等，則它們表示一個非空范圍）.如果范圍非空，則必須保證，通過反復遞增第一個迭代器，可以到達第二個迭代器。通過遞增迭代器，序列中每個元素都能被訪問到。
左閉合區間（left-inclusiveinterval）值范圍，包含首元素，但不包含尾元素。通常表示為［i,j）表示序列從i開始（包含）直至j結束（不包含）。list順序容器，表示一個雙向鏈表。list中的元素只能順序訪問。從一個給定元素開始，為了訪問另一個元素，我們只能遍歷兩者之間的所有元素。list上的迭代器既支持遞增運算（++）,也支持遞減運算（--）olist支持任意位置的快速插入（或刪除）操作。當加入新元素后，迭代器仍然有效。當刪除元素后，只有原來指向被刪除元素的迭代器才會失效。
首前迭代器（off-the-beginningiterator）表示一個forwardlist開始位置之前（不存在的）元素的迭代器。是forward_list的成員函數before_begin的返回值。與end（）迭代器類似，「不能被解引用。
尾后迭代器（off-the-enditerator）表示范圍中尾元素之后位置的迭代器。通常被稱為“末尾迭代器"（enditerator）。
priority_queue順序容器適配器，生成一個隊列，插入其中的元素不放在末尾，而是根據特定的優先級排列。默認情況下，優先級用元素類型上的小于運算符確定。
queue順序容器適配器，生成一個類型，使我們能將新元素添加到末尾，從頭部刪除元素。
順序容器（sequentialcontainer）保存相同類型對象有序集合的類型。順序容器中的元素通過位置來訪問。
stack順序容器適配器，生成一個類型，使我們只能在其一端添加和刪除元素。
vector順序容器。vector中的元素可以通過位置下標訪問。支持快速的隨機訪問。我們只能在vector末尾實現高效的元素添加/刪除。向vector添加元素可能導致內存空間的重新分配，從而使所有指向vector的迭代器失效。在vector內部添加（或刪除）元素會使所有指向插入（刪除）點之后元素的迭代器失效