除了順序容器外,标準庫還定義了三個順序容器擴充卡:stack、queue和priority_queue。擴充卡是标準庫中的一個通用概念。容器、疊代器和函數都有擴充卡。本質上,一個擴充卡是一種機制。能使某種事物的行為看起來像另外一種事物一樣。一個容器擴充卡接受一種已有的容器類型,使其行為看起來像一種不同的類型。例如,stack擴充卡接受一個順序容器(除array或forward_list外),并使其操作起來像一個stack一樣。下表列出了所有擴充卡都支援的操作和類型:
是以容器擴充卡都支援的操作和類型
size_type 一種類型,足以儲存目前類型的最大對象的大小
value_type 元素類型
container_type 實作擴充卡的底層容器類型
A a; 建立一個名為a的空擴充卡
A a(c); 建立一個名為a的擴充卡,帶有容器c的一個拷貝
關系運算符 每個擴充卡都支援所有關系運算符:==、!=、<、<=、>和>=,這些運算符傳回底層容器的比較結果
a.empty() 若a包含任何元素,傳回false,否則傳回true
a.size() 傳回a中的元素數目
swap(a,b) 交換a和b的内容,a和b必須有相同的類型,包括底層容器類型也必須相同
a.swap(a,b)
定義一個擴充卡
每個擴充卡都定義了兩個構造函數:預設構造函數建立以空對象,接受一個容器的構造函數拷貝該容器來初始化擴充卡。例如,假定deq是一個deque<int>,我們可以用deq來初始化一個新的stack,如下所示:
stack<int> stk(deq); //從deq拷貝元素到stk
預設情況下,stack和queue是基于deque實作的,priority_queue是在vector之上實作的。我們可以在建立一個擴充卡時将一個命名的順序容器作為第二個類型參數,來重載預設容器類型:
//vector上實作的空棧
stack<string,vector<string>> str_stk; //預設是在deque上實作的,這裡顯示的指定為在vector上實作
//str_stk2在vector上實作,初始化時儲存svec的拷貝
stack<string,vector<string>> str_stk2(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頭檔案中。下表列出了stack支援的操作。下面的程式展示了如何使用stack:
棧操作
棧預設是基于deque實作,也可以在list或vector上實作
s.pop() 删除棧頂元素,但不傳回該元素的值
s.push(item) 建立一個新元素壓人棧頂,該元素通過拷貝或移動item而來,或者由args構造
s.emplace(args)
s.top() 傳回棧頂元素,但不将元素彈出棧
每個容器擴充卡都基于底層類型的操作定義了自己的特殊操作。我們隻能使用擴充卡操作,而不能使用底層容器類型的操作。例如:
intStack.push(ix);
此語句試圖在intStack的底層deque對象上調用push_back。雖然stack是基于deque實作的,但我們不能直接使用deque操作。不能在一個stack上調用push_back,而必須使用stack自己的操作——push。
隊列擴充卡
queue和priority_queue擴充卡定義在queue頭檔案中。下表列出了它所支援的操作:
queue和priority_queue的操作
queue預設基于deque實作,priority_queue預設基于vector實作;
queue也可以由list或vector實作,priority_queue也可以用deque實作
q.pop() 傳回queue的首元素或priority_queue的最高優先級的元素,但不删除此元素
q.front() 傳回首元素或尾元素,但不删除此元素
q.back() 隻适用于queue
q.top() 傳回最高優先級元素,但不删除該元素,隻适用于priority_queue
q.push(item) 在queue末尾或priority_queue中恰當的位置建立一個元素。其值為item,或者由args構造
q.emplace(args)
标準庫queue使用一種先進先出的存儲和通路政策。進入隊列的對象被放置在隊尾,而離開隊列的對象則從隊首删除。
priority_queue允許我們為隊列中的元素建立優先級。新加入的元素會排在所有優先級比它低的已有元素之前。