List (STL)

C++ STL

listC++標準程式庫中的一個,可以簡單視之為雙向連結串列,以線性列的方式管理物件集合。list 的特色是在集合的任何位置增加或刪除元素都很快,但是不支持隨機存取。list 是C++標準程式庫提供的眾多容器(container)之一,除此之外還有vector、set、map、…等等。list 以模板方式實現(即泛型),可以處理任意型別的變數,包括使用者自定義的資料型態,例如:它可以是一個放置整數(int)型態的 list、也可以是放置字串(char 或 string)型態的 list、或者放置使用者自定類別(user-defined class)的 list。

設計编辑

list 被定義在 <list> 標頭檔中。一如其他STL元件,list屬於std名稱空間。

list 內部以資料結構的雙向連結串列實做,內部元素 記憶體各處,互相以link串接起來,每個元素都只知道其前一個元素以及下一個元素的位置。故要走訪整個list,必須從第一個元素開始逐個往下尋訪,不支持隨機存取(Random Access)。 list 的強項是高效的插入以及刪除,於list插入或刪除時只需要改動元素的link欄位,不需要搬動元素,代價相對便宜。

list 在經常需要於集合內部任意位置(即除了頭尾以外的其他位置) 頻繁增刪元素的工作上表現優秀。若僅需要於集合尾端增刪元素,那應該優先考慮vector容器,若僅於頭尾二端增刪元素,那應該優先考慮deque容器。


成員函數概觀编辑

  • 迭代 (Iterator)
    • list.begin() 回傳指向第一個元素的 Iterator。
    • list.end() 回傳指向最末元素的下一個位置的 Iterator。
    • list.rbegin() 回傳指向最末個元素的反向 Iterator。
    • list.rend() 回傳指向第一個元素的前一個位置的反向 Iterator。
  • Capacity/Size:
    • list.empty() 若list內部為空,則回傳true值。
    • list.size() 回傳list內實際的元素個數。
    • list.resize() 重新分派list的長度。
  • 存取元素的方法
    • list.front() 存取第一個元素。
    • list.back() 存取最末個元素。
  • Modify methods
    • list.push_front() 增加一個新的元素在 list 的前端。
    • list.pop_front() 刪除 list 的第一個元素。
    • list.push_back() 增加一個新的元素在 list 的尾端。
    • list.pop_back() 刪除 list 的最末個元素。
    • list.insert() - 插入一個或多個元素至 list內的任意位置。
    • list.erase() - 刪除 list中一個或多個元素。
    • list.clear() - 清空所有元素。
  • 重新配置/重設長度
    • list.reserve() - 如有必要,可改變 list的容量大小(配置更多的記憶體)。
    • list.resize() - 改變 list目前持有的元素個數。

使用說明编辑

宣告编辑

std::list<T> mylist;

外部链接编辑