RobbEr's Blog

Welcome

STL-list

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

简介

list 是 STL 库实现的一个双向链表，可以高效的插入和删除数据，这意味着 list 中的元素可以分散的存储在空间中，而不是必须存储在一块连续的空间中

list是序列式容器，但不支持随机访问

类模板

1
2
3
4
template <
    class T,                        //数据类型
    class _Alloc = allocator<T>     //分配器
> list;

成员函数

迭代器相关

  1. begin() - 返回指向 list 第一个元素的迭代器
  2. end() - 返回指向 list 中最后一个元素之后的理论元素的迭代器
  3. rbegin() - 返回指向 list 中最后一个元素的反向迭代器（反向开始）
  4. rend() – 返回一个反向迭代器，指向 list 中第一个元素之前的理论元素
  5. cbegin() - 返回指向 list 中第一个元素的const迭代器 (C++11)
  6. cend() - 返回一个const迭代器，指向 list 中最后一个元素之后的理论元素 (C++11)
  7. crbegin() – 返回指向 list 中最后一个元素的const反向迭代器（反向开始） (C++11)
  8. crend() - 返回指向 list 中第一个元素之前的理论元素的const反向迭代器 (C++11)

容量相关

  1. size() - 返回 list 中元素数 O(1)
  2. max_size() - 返回 list 可以容纳的最大元素数 O(1)
  3. resize() - 调整 list 可存储数量
  4. empty() - 当前 list 是否为空 O(1)

元素访问相关

  1. front() - 返回对 list 中第一个元素的引用 O(1)
  2. back() - 返回对 list 中最后一个元素的引用 O(1)

修改器相关

  1. assgin() - 用新的容器替换此容器
  2. clear() - 清空所有元素，size()置 0
  3. insert() - 插入一个或多个元素到指定位置
  4. erase() - 删除指定位置元素
  5. push_front() - 头部插入元素 O(1)
  6. pop_front() - 删除头部元素 O(1)
  7. push_back() - 尾部插入元素 O(1)
  8. pop_back() - 删除尾部元素 O(1)
  9. swap() - 交换元素
  10. emplace() - 插入一个元素到指定位置，调用构造函数 (C++11)
  11. emplace_front() - 插入一个元素到头部，调用构造函数 (C++11)
  12. emplace_back() - 插入一个元素到尾部，调用构造函数 (C++11)

容器操作

  1. merge() - 合并两个 list
  2. splice() - 从一个 list 中移动元素
  3. remove() & remove_if() - 移除满足要求的元素
  4. reverse() - 反转 list
  5. unique() - 删除重复的元素
  6. sort() - 对 list 进行排序

list迭代器详解

deque 的所有迭代器都是双向迭代器

1. 正向迭代器

此迭代器是由 begin(), end() 所返回的，其对其的操作为正向，且当 deque 元素不为 const 时可以更改其指向的值，即：

1
2
3
4
list<int> v{ 1,2,3,4,5,6 };
auto i = v.begin(); //*i为1
i++;                //*i为2
*i = 100;           //*i为100

2. 反向迭代器

此迭代器由 rbegin(), rend() 所返回，对其的操作为反向，且也满足当 deque 元素不为 const时可以更改其指向的值，即：

1
2
3
4
list<int> v{ 1,2,3,4,5,6 };
auto i = v.rbegin();//*i为6
i++;                //*i为5
*i = 100;           //*i为100

3. const迭代器

此迭代器由 cbegin(), cend(), crbegin(), crend() 返回，只能对其操作，不能更改其指向的值，即：

1
2
3
4
list<int> v{ 1,2,3,4,5,6 };
auto i = v.cbegin();//*i为1
i++;                //*i为2
*i = 100;           //error！

list的特性

list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 nullptr，因为它前面没有元素；同样，尾部元素的后向指针也总为 nullptr

基于这样的存储结构，list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势，即它可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高

list 容器的缺点是，它不能像 array 和 vector 那样，通过位置直接访问元素

举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置

并且 list 在插入时其迭代器不会失效，只有删除了元素后对应迭代器才会失效