List (STL)
C++标准库 |
---|
list 是C++标准程式库中的一个类,可以简单视之为双向连结串列,以线性列的方式管理物件集合。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;