C++标準庫順序容器

C++ primer 第九章 順序容器筆記

C++順序容器 sequential container

提供控制元素存儲和通路的順序功能。

ps. 與之相對的還有有序和無序關聯容器，通過key值來存儲元素。

順序容器類型

---------------------------------------------------------------------------------------

• vector 可變大小數組
  • 快速随機通路
  • 尾部以外其他位置插入/删除元素可能很慢
• string 存放字元串可變大小容器（與vector類似）
  • 支援快速随機通路
  • 在尾部插入/删除快

string 和 vector 在連續的記憶體空間裡存儲元素，下标計算位址極快。

中間位置添加删除需要移動後面的所有元素保持連續存儲，是以非常耗時。

添加新元素有可能需要配置設定額外的存儲空間，可能需要移動所有元素到新的存儲空間中。

---------------------------------------------------------------------------------------

• list 雙向連結清單
  • 隻支援雙向順序通路
  • 任意位置插入/删除元素都快
• forward_list 單向連結清單
  • 隻支援單向順序通路
  • 任意位置插入/删除元素都快

連結清單容器任何位置添加删除都很快速。

然而不支援元素随機通路，隻能通過周遊整個容器通路一個元素。

相比vector，deque，array，額外記憶體開銷大。

forward_list是新C++标準增加的類型，沒有size操作。

---------------------------------------------------------------------------------------

• deque 雙端隊列
  • 快速随機通路
  • 頭尾插入/删除速度快

deque支援快速随機通路。兩端添加删除元素極快。

在中間添加删除代價可能很大。

---------------------------------------------------------------------------------------

• array 固定大小數組
  • 支援快速随機通路
  • 不能添加/删除元素

array是新C++标準增加的類型，比内置數組更安全易用。

大小固定，不可添加删除元素。

---------------------------------------------------------------------------------------

總結：

• 快速随機通路：vector，string，deque，array
• 極慢周遊通路：連結清單
• 中間位置增删：連結清單快，vector，string，deque慢， array不支援
• 頭尾位置增删：連結清單快，deque快，尾部位置vector，string不保證快，array不支援

選擇容器原則

• 除特殊理由，通常使用vector
• 空間額外開銷重要時，不使用連結清單list和forward_list
• 需要随機通路，使用vector或者deque
• 中間插入，用連結清單
• 頭尾插入，用deque
• 程式初需要讀取輸入并在容器中間位置插入時，而後需要快速随機通路的話：
  1. 讀取資料加入vector中，而後調用sort，避免中間位置的添加
  2. 輸入階段使用連結清單list中，輸入完成拷貝到vector中

容器都是模版類

vector\<int> ivec(10, -1);
list\<string> svec(10, "hi!");
list\<string> svec = {"abc", "def"};
forward_list\<int> ivec(10);
deque\<sting> svec(svec1);
array\<string, 10>;
           

容器通用操作

• 容器定義的類型
  • iterator 疊代器
  • const_iterator 僅能讀取元素的疊代器
  • size_type 無符号整數類型
  • difference_type 帶符号整數類型，兩個疊代器間的距離
  • value_type 元素類型
  • reference 元素左值類型，含義為value_type &
  • const_reference
• 構造函數
  • C c； 構造空容器
  • C c1(c2); c2拷貝給c1
  • C c(begin, end); 疊代器b和e指定的範圍内的元素拷貝給c
  • C c{a, b, c, …}; 清單初始化c
• 指派與swap
  • c1 = c2; c1元素替換給c2
  • c1 = {a, b, c, …}；c1元素替換
  • a.swap(b) 等價于swap(a, b) 交換a和b的元素
• 大小
  • c.size() 傳回元素個數，不支援forward_list
  • c.max_size() c中可儲存最大元素數目
  • c.empty() 是否存儲元素 true 或 false

• 添加/删除元素

  不同容器接口不同

• 關系運算符

  ==， != 所有容器都支援

  <=, >=, <, > 無序關聯容器不支援

• 擷取疊代器

  c.begin()

  c.end()

  c.cbegin() 傳回const_iterator

  c.cend()

• 反向容器的成員 （不支援forward_list）

  reverse_iterator 反向疊代器

  const_reverse_iterator

  c.rbegin() 傳回尾元素疊代器

  c.rend() 傳回首元素之前位置的疊代器

  c.crbegin()

  c.crend()