天天看點
傳回

《C++Primer》第九章-順序容器-學習筆記(3)-容器擴充卡&棧&隊列《C++Primer》第九章-順序容器-學習筆記(3)-容器擴充卡&棧&隊列

《C++Primer》第九章-順序容器-學習筆記(3)-容器擴充卡&棧&隊列

文章目錄

  • 《C++Primer》第九章-順序容器-學習筆記(3)-容器擴充卡&棧&隊列
    • 容器擴充卡
        • 擴充卡的初始化
        • 覆寫基礎容器類型
        • 擴充卡的關系運算
      • 棧擴充卡
      • 隊列和優先級隊列
    • 小結
    • 參考資料
    • 注解

日志：

1，2020-03-12 筆者送出文章的初版V1.0

作者按：

最近在學習C++ primer，初步打算把所學的記錄下來。

傳送門/推廣

《C++Primer》第二章-變量和基本類型-學習筆記(1)

《C++Primer》第三章-标準庫類型-學習筆記(1)

《C++Primer》第八章-标準 IO 庫-學習筆記(1)

《C++Primer》第十二章-類-學習筆記(1)

容器擴充卡

除了順序容器，标準庫還提供了三種

順序容器擴充卡

：

隊列(queue)

、

優先級隊列(priority_queue)

和

棧（stack）

。

擴充卡（adaptor）

是标準庫中通用的概念，包括

容器擴充卡

、

疊代器擴充卡

和

函數擴充卡

。

擴充卡

本質上是使一事物的行為類似于另一事物的行為的一種機制。 容器擴充卡讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實作。例如，stack（棧）擴充卡可使任何一種順序容器以棧的方式工作。表 9.22 列出了所有容器擴充卡通用的操作和類型。

表 1. 擴充卡通用的操作和類型：

操作和類型 作用
size_type 一種類型，足以存儲此擴充卡類型最大對象的

長度
value_type 元素類型
container_type 基礎容器的類型，擴充卡在此容器類型上實作
A a; 建立一個新空擴充卡，命名為 a
A a( c ); 建立一個名為 a 的新擴充卡，初始化為容器 c 的副本
關系操作符 所有擴充卡都支援全部關系操作符：==、 !=、 <、 <=、 >、>=

使用擴充卡時，必須包含相關的頭檔案：

#include <stack> // stack adaptor
#include <queue> // both queue and priority_queue adaptors

擴充卡的初始化

所有擴充卡都定義了兩個構造函數：

預設構造函數

用于建立空對象，而

帶一個容器參數的構造函數

将參數容器的副本作為其基礎值。例如，假設 deq deque 類型的容器，則可用 deq 初始化一個新的棧，如下所示：

stack<int> stk(deq); // copies elements from deq into stk
//帶一個容器參數的構造函數`将參數容器的副本作為其基礎值

覆寫基礎容器類型

預設的

stack 和 queue

都

基于 deque 容器實作

，

priority_queue

則

基于 vector 容器實作

。在建立擴充卡時，通過将一個順序容器指定為擴充卡的第二個類型實參，可覆寫其關聯的基礎容器類型：

// empty stack implemented on top of vector
stack< string, vector<string> > str_stk;  //将一個順序容器指定為擴充卡的第二個類型實參，可覆寫stack關聯的基礎容器類型deque
// str_stk2 is implemented on top of vector and holds a copy of svec
stack<string, vector<string> > str_stk2(svec);

對于給定的擴充卡，其關聯的容器必須滿足一定的限制條件。

  • stack 擴充卡所關聯的基礎容器可以是任意一種順序容器類型。是以，stack 棧可以建立在vector、list 或者 deque 容器之上。
  • queue 擴充卡要求其關聯的基礎容器必須提供 push_front 運算，是以隻能建立在 list 或deque容器上，而不能建立在vector 容器上。
  • priority_queue 擴充卡要求提供随機通路功能，是以可建立在vector 或 deque 容器上，但不能建立在 list 容器上。

擴充卡的關系運算

兩個相同類型的擴充卡可以做相等、不等、小于、大于、小于等于以及等于關系比較，隻要基礎元素類型支援等于和小于操作符既可。這些關系運算由元素依次比較來實作。第一對不相等的元素将決定兩者之間的小于或大于關系。

棧擴充卡

表 2列出了棧提供的所有操作。

表 2. 棧容器擴充卡支援的操作：

棧容器擴充卡操作 作用
s.empty() 如果棧為空，則傳回 true，否則傳回 stack
s.size() 傳回棧中元素的個數

s.pop()

 		删除棧頂元素的值，但不傳回其值

s.top()

 		傳回棧頂元素的值，但不删除該元素

s.push(item)

 		在棧頂壓入新元素

棧容器擴充卡支援的操作程式執行個體：

// number of elements we'll put in our stack
const stack<int>::size_type stk_size = 10;  //打算放入10個元素到棧中
stack<int> intStack; // empty stack  初始化一個棧
// fill up the stack
int ix = 0;
while (intStack.size() != stk_size) 
// use postfix increment; want to push old value onto intStack
	intStack.push(ix++); // intStack holds 0...9 inclusive  
int error_cnt = 0;  //用來檢查元素錯誤的數量
// look at each value and pop it off the stack
while (intStack.empty() == false)
 {
	int value = intStack.top();
// read the top element of the stack
	if (value != --ix) 
	{
		cerr << "oops! expected " << ix<< " received " << value << endl;
		++error_cnt; 
	}
	intStack.pop(); // pop the top element, and repeat
}
cout << "Our program ran with "<< error_cnt << " errors!" << endl;

聲明語句：

将 intStack 定義為一個存儲整型元素的空棧。第一個 while 循環在該棧中添加了 stk_size 個元素，元素初值是從 0 開始依次遞增 1 的整數。第二個while 循環疊代周遊整個棧，檢查其棧頂（top）的元素值，然後棧頂元素出棧，直到棧變空為止。

所有容器擴充卡都根據其基礎容器類型所支援的操作來定義自己的操作。預設情況下，棧擴充卡建立在 deque 容器上，是以采用 deque 提供的操作來實作棧功能。例如，執行下面的語句：

// use postfix increment; want to push old value onto intStack
intStack.push(ix++); // intStack holds 0...9 inclusive

這個操作通過調用 push_back 操作實作，而該 intStack 所基于的 deque對象提供。盡管棧是以 deque 容器為基礎實作的，但是程式員不能直接通路deque 所提供的操作。例如，不能在棧上調用push_back 函數，而是必須使用棧所提供的名為 push 的操作。

隊列和優先級隊列

标準庫隊列使用了先進先出（FIFO）的存儲和檢索政策。進入隊列的對象被放置在尾部，下一個被取出的元素則取自隊列的首部。标準庫提供了兩種風格的隊列：

FIFO 隊列（FIFO queue，簡稱 queue）

，以及

優先級隊列（priority queue）

。

priority_queue

允許使用者為隊列中存儲的元素設定優先級。這種隊列不是直接将新元素放置在隊列尾部，而是放在比它優先級低的元素前面。标準庫預設使用元素類型的

<

操作符來确定它們之間的優先級關系。

優先級隊列的一個執行個體是

機場行李檢查隊列

。30 分鐘後即将離港的航班的乘客通常會被移到隊列前面，以便他們能在飛機起飛前完成檢查過程。使用優先級隊列的程式示例是

作業系統的調試表

，它決定在大量等待程序中下一個要執行的程序。

要使用FIFO 隊列與優先級隊列，必須包含 queue 頭檔案。表 3列出了隊列和優先級隊列所提供的所有操作。

表 3. 隊列和優先級隊列支援的操作：

隊列和優先級隊列操作 作用
q.empty() 如果隊列為空，則傳回 true，否則傳回 false
q.size() 傳回隊列中元素的個數
q.pop() 删除隊首元素，但不傳回其值
q.front() 傳回隊首元素的值，但不删除該元素。（該操作隻适用于隊列）
q.back() 傳回隊尾元素的值，但不删除該元素。（該操作隻适用于隊列）
q.top() 傳回具有最高優先級的元素值，但不删除該元素。（該操作隻适用于優先級隊列）
q.push(item) 對于 queue，在隊尾壓入一個新元素，對于 priority_quue，在基于優先級的适當位置插入新元素

小結

C++ 标準庫定義了一系列順序容器類型。容器是用于存儲某種給定類型對象的模闆類型。在順序容器中，所有元素根據其位置排列和通路。順序容器共享一組通用的已标準化的接口：如果兩種順序容器都提供某一操作，那麼該操作具有相同的接口和含義。

所有容器都提供（有效的）動态記憶體管理。程式員在容器中添加元素時，不必操心元素存放在哪裡。容器自己實作其存儲管理。

最經常使用的容器類型是

vector

，它支援對元素的快速随機通路。可高效地在 vector 容器尾部添加和删除元素，而在其他任何位置上的插入或删除運算則要付出比較昂貴的代價。

deque 類

與 vector 相似，但它還支援在 deque 首部的快速插入和删除運算。

list 類隻支援元素的順序通路，但在 list 内部任何位置插入和删除元素都非常快速。

容器定義的操作非常少，隻定義了構造函數、添加或删除元素的操作、設定容器長度的操作以及傳回指向特殊元素的疊代器的操作。其他一些有用的操作，如排序、查找，則不是由容器類型定義，而是由第十一章介紹的标準算法定義。

在容器中添加或删除元素可能會使已存在的疊代器失效。當混合使用疊代器操作和容器操作時，必須時刻留意給定的容器操作是否會使疊代器失效。許多使一個疊代器失效的操作，例如 insert 或 erase，将傳回一個新的疊代器，讓程式員保留容器中的一個位置。使用改變容器長度的容器操作的循環必須非常小心其疊代器的使用。

參考資料

【1】C++ Primer 中文版（第四版·特别版）

注解

c++ 程式設計語言 容器擴充卡 優先級隊列 vector
上一篇: 《c++primer》第九章·順序容器9.1 順序容器概述9.2 容器庫概覽9.3 順序容器操作9.4 vector對象是如何增長的9.5 額外的string 操作
下一篇: 我的《C++primer筆記》第九章：順序容器

繼續閱讀