List (STL)

list 是C++标准程序库中的一个类，可以简单视之为双向链表，以线性列的方式管理对象集合。list 的特色是在集合的任何位置增加或删除元素都很快，但是不支持随机访问。list 是C++标准程序库提供的众多容器（container）之一，除此之外还有vector、set、map、…等等。list 以模板方式实现(即泛型)，可以处理任意类型的变量，包括用户自定义的数据型态，例如：它可以是一个放置整数（int）型态的 list、也可以是放置字符串（char 或 string）型态的 list、或者放置用户自定类别（user-defined class）的 list。

C++标准库

设计

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;

外部链接
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.