C++ STL序列容器簡介（C++ primer，P697）

STL序列容器簡介

包含以下内容：

• 容器的概念
• 序列容器的基本要求與可選要求
• 幾種序列容器特點與基本操作

容器的概念

STL具有容器概念和容器類型；

容器概念是指具有名稱（序列/關聯容器）的通用類别；

容器類型是指可用于建立具體容器對象的模闆；

是以，序列容器是一類容器類型的統稱；

容器是存儲其它對象的對象，不能将任何資料類型存儲到容器中。

序列容器的基本要求與可選要求

序列容器有七種：vector、deque、queue、priority_queue、list、forward_list、stack；

注意，array不是STL容器；

序列容器通用要求：

• 初始化
• 插入
• 擦除

  //初始化重要的兩個方式
   X a(n, t);
   X b(a.begin(), a.end());
  
   //插入重要的兩個方式
   a.insert(a.begin(), t);
   a.insert(a.begin(), b.begin(), b.end());
   
   //擦除區間
   a.erase(a.begin(), a.end());
             

序列可選要求：

• front()、back()
  • 傳回開頭、結尾的元素，注意是元素
• push_back、pop_back、push_front、pop_front
  • 在開頭/結尾進行插入/删除操作
  • vector不推薦在頭插入删除
  • list、deque都可以（list指雙連結清單）
• a[n]、 a . at(n)
  • 傳回第n個元素
  • at具有邊界檢查，如果越界會有out_of_range異常

幾種序列容器的特點與基本操作

vector —— 最簡單的序列容器

除非需要在頭部插入、删除元素，其餘推薦使用vector

vector強調快速随機通路

• < vector >頭檔案
• 尾部插入/删除為固定時間操作
• 頭部/中間插入/删除為線性時間操作
• 支援反轉（rbegin、rend）
• 支援随機通路

deque —— 雙端隊列

頻繁在頭插入删除元素，可以使用deque

• < deque >頭檔案
• 支援随機通路（比vector稍慢）
• 頭尾插入/删除都是固定時間操作
• 中間插入/删除為線性時間（比vector稍慢）
• 支援反轉

list —— 雙連結清單

任意一處插入/删除都是固定時間；

list強調快速随機插入/删除；

• < list >頭檔案
• 不支援随機通路、數組表示法
• 有merge(合并)、sort(排序)、unique(删除重複元素)方法（primer，P699）

forward_list —— 單連結清單

• < forward_list >頭檔案
• 隻能正向疊代
• 不可反轉

queue —— 隊列

底層預設為deque；

先入先出，是以隻能在頭删除元素、尾添加元素

• < queue >頭檔案
• 不允許随機通路
• 不允許周遊
• empty()、size()、front()、back()、push()、pop()方法
• pop()直接删除頭，是以需要先用front檢視頭

priority_queue —— 優先隊列

底層預設為vector；

最大的元素将被移到隊首；

• < queue >頭檔案

stack —— 棧，先入後出

底層預設為vector；

• < stack >頭檔案
• empty()、size()、top()、push()、pop()方法
• pop()直接删除尾，是以需要用top()檢視尾

array —— 非STL容器

固定大小，無法調整

• < array >頭檔案
• 無push、insert等方法
• 有at()等方法