撰写C++中的list是一个双向链表，也是一种序列容器，它可以在任何位置高效地插入和删除元素，支持正向迭代和反向迭代。在list中，每个元素保存在一个结点中，相邻的结点使用指针连接起来（前一个结点的后向指针指向后一个结点，后一个结点的前向指针指向前一个结点）。因此，要想找到位于第i个位置的元素，需要从第一个元素开始，顺着指针依次找下去，导致该操作的时间复杂度为O(n)。
list包含在<list>头文件中，它是一个类模板，因此在定义list类的对象时，需要指明容器需要保存的对象的类型（除特殊情况外，本文均以int类型为例）。对于标注C++11的内容，需要支持C++11标准的编译器来编译。
构造与析构
- list() 默认构造函数，构造一个空的容器，不包含任何元素；
- list(size_type n, value_type &val) 填充构造函数，构造一个含有n个val的容器；
- list(iterator first, iterator last) 范围构造函数，构造一个包含[first, last)的容器；
- list(const list<value_type> &x) 复制构造函数，构造一个与x相同的容器；
- list(list<value_type> &&x) （C++11）移动构造函数，如果指定的分配器与x相同，则直接引用x中的内容，而不是逐个分配；
- list(initializer_list<value_type> il) （C++11）初始化列表构造函数；
- ~list() 析构函数，释放内存并销毁对象。
#include <list>
using std::list;
int main()
{
list<int> l1; // 空容器
list<int> l2(4, 1); // 4个1
list<int> l3(l2.begin(), l2.end()); // 和l2相同
list<int> l4(l3); // 和l3相同
list<int> l5(std::move(l4)); // 执行后l4为空
list<int> l6({1, 2, 3, 4});
}
迭代器
- begin() 返回第一个元素的迭代器；
- end() 返回最后一个元素后面的迭代器（而不是最后一个元素）；
- rbegin() 返回最后一个元素的反向迭代器；
- rend() 返回第一个元素前面的迭代器；
- cbegin()、cend()、crbegin()、crend()（C++11） 表示对应的常量（const）迭代器。
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main()
{
list<int> ls({1, 2, 3, 4});
cout << "The list contains:";
for(auto it = ls.begin(); it != ls.end(); ++it)
cout << ' ' << *it;
cout << endl;
cout << "The reversed list contains:";
for(auto it = ls.rbegin(); it != ls.rend(); ++it)
cout << ' ' << *it;
cout << endl;
return 0;
}
/*
The list contains: 1 2 3 4
The reversed list contains: 4 3 2 1
*/
容量相关
- size() 获取容器中元素个数；
- max_size() 返回在当前的系统环境下，容器最多可以容纳的元素个数，但并不一定可以达到这么多；
- empty() 若容器为空则返回true，否则返回false。
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main()
{
list<int> ls({1, 2, 3, 4});
cout << "ls contains " << ls.size() << " elements.\n";
if(ls.empty()) cout << "ls is empty.\n";
else cout << "ls is not empty.\n";
return 0;
}
/*
ls contains 4 elements.
ls is not empty.
*/
元素访问
- front() 返回第一个元素的引用；
- back() 返回最后一个元素的引用。
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main()
{
list<int> ls({1, 2, 3, 4});
ls.front() = 4;
ls.back() = 1;
cout << "The front of ls is " << ls.front() << ".\n";
cout << "The back of ls is " << ls.back() << ".\n";
return 0;
}
/*
The front of ls is 4.
The back of ls is 1.
*/
增删元素
- assign(…) 为容器重新赋值；（使用…表示有多种参数不同的函数，在代码中给出示例）；
- emplace_front(Args&&… args) （C++11）使用args构造并在容器前插入元素，没有返回值；
- push_front(value_type &val) 在容器前增加元素；
- pop_front() 删除第一个元素；
- emplace_back(Args&&… args) （C++11）使用args构造并在容器后插入元素，没有返回值；
- push_back(value_type &val) 在容器后增加元素；
- pop_back() 删除最后一个元素；
- emplace(const_iterator pos, Args&&… args) （C++11）使用args构造并在pos位置插入元素，返回新元素的迭代器；
- insert(…) 在当前位置插入元素，返回第一个插入元素的迭代器；
- erase(…) 删除当前位置的元素，返回下一个元素的迭代器；
- swap(list<value_type> &ls) 交换两个容器的内容；
- resize(size_type n, const value_type &val) 将容器大小置为n，若n小于当前元素数量，则只保存前n个元素，若n大于当前元素数量，则使用val填充；
- clear() 清空容器。
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
void show(list<int> &ls)
{
for(auto i : ls)
cout << ' ' << i;
cout << endl;
}
int main()
{
list<int> ls({1, 2, 3, 4});
// assign:
list<int> ls2(2, 0);
cout << "Before assign, the elements in ls2 are: ";
show(ls2);
auto it = ls.end();
--it;
// assign(InputIterator first, InputIterator last)
ls2.assign(ls.begin(), it); // 1 2 3
// assign(size_type n, const value_type &val)
ls2.assign(4, 0); // 4个0
// assign(initializer_list<value_type> il) (C++11)
ls2.assign({3, 2, 1}); // 3 2 1 (C++11)
cout << "After assign, the elements in ls2 are: ";
show(ls2);
// 带有emplace的函数可参见vector，此处不再赘述
// https://blog.kedixa.top/2016/cpp-container-vector/
// insert
// insert(const_iterator it, const value_type &val)
ls2.insert(ls2.begin(), 4); // 4 3 2 1
// insert(const_iterator it, size_type n, const value_type &val)
ls2.insert(ls2.end(), 2, 0); // 4 3 2 1 0 0
// insert(const_iterator it, InputIterator first, InputIterator last)
ls2.insert(ls2.end(), ls.begin(), ls.end()); // 4 3 2 1 0 0 1 2 3 4
// insert(const_iterator it, value_type &&val) (C++11)
// 将val移动（move）到it位置，关于移动语义暂不讨论，省略
// insert(const_iterator it, initializer_list<value_type> il) (C++11)
it = ls2.begin();
++it;
ls2.insert(it, {5});
cout << "After insert, the elements in ls2 are: ";
show(ls2);
// erase
// erase(const iterator it) 删除it指向的内容
it = ls2.end();
--it;
ls2.erase(it);
// erase(const_iterator first, const_iterator last) 删除区间[first, last)
it = ls2.end();
--it, --it;
ls2.erase(ls2.begin(), it);
cout << "After erase, the elements in ls2 are: ";
show(ls2);
// swap
ls2.swap(ls); // 1 2 3 4
cout << "After swap, the elements in ls are: ";
show(ls);
// resize
ls2.resize(7, 10);
cout << "After swap and resize, the elements in ls2 are: ";
show(ls2);
ls2.clear(); // 清空容器
if(ls2.empty()) cout << "After clear, ls2 is empty.\n";
return 0;
}
/*
Before assign, the elements in ls2 are: 0 0
After assign, the elements in ls2 are: 3 2 1
After insert, the elements in ls2 are: 4 5 3 2 1 0 0 1 2 3 4
After erase, the elements in ls2 are: 2 3
After swap, the elements in ls are: 2 3
After swap and resize, the elements in ls2 are: 1 2 3 4 10 10 10
After clear, ls2 is empty.
*/
其他操作
- splice(…) 从另一个链表剪下一段并拼接到容器中；
- remove(const value_type &val) 删除所有值为val的元素；
- remove_if(Predicate pred) 删除所有使谓词为真的元素；
- unique(…)；
- merge(list<value_type> &b, Compare cmp) 需要两个链表都是有序的，将该链表与b归并，函数返回后b容器为空，该函数可以指定比较函数；
- sort(Compare cmp) 将链表排序，若不指定排序函数，则按照operator<排序；
- reverse() 反转链表。
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
void show(list<int> &ls)
{
for(auto i : ls)
cout << ' ' << i;
cout << endl;
}
bool is_odd(int i)
{
return i%2==1;
}
bool diff(int x, int y)
{
return y - x == 1;
}
int main()
{
list<int> ls({1, 2, 3, 4});
list<int> ls2;
// splice
// splice(const_iterator it, list &x) 将x的内容插入到迭代器it指向的位置
ls2.splice(ls2.end(), ls); // ls2: 1 2 3 4, ls为空
ls.swap(ls2);
// splice(const_iterator it, list &x, const_iterator i) 将i指向的内容插入到it指向的位置
ls2.splice(ls2.end(), ls, ls.begin()); // ls2: 1, ls: 2 3 4
// splice(const_iterator it, list &x, const_iterator first, const_iterator last)
// 将x的[first, last) 插入到 it指向的位置
ls2.splice(ls2.begin(), ls, ls.begin(), ls.end());
cout << "After splice, the elements in ls are: ";
show(ls);
cout << "After splice, the elements in ls2 are: ";
show(ls2);
// remove
ls2 = list<int>({1, 1, 2, 3, 4, 5});
ls2.remove(1); // 2 3 4 5
ls2.remove_if(is_odd); // 2 4
cout << "After remove, the elements in ls2 are: ";
show(ls2);
// unique
ls2 = list<int>({1, 1, 1, 2, 2, 3, 4, 6, 7});
// unique() 相邻的相同元素只保留一个
ls2.unique(); // 1 2 3 4 6 7
// unique(BinaryPredicate pred) 若pred(*it, *(it-1))返回真，则删除it指向的内容
ls2.unique(diff);
cout << "After unique, the elements in ls2 are: ";
show(ls2);
// merge
ls.assign({1, 3, 5});
ls2 = list<int>({2, 4});
ls2.merge(ls);
cout << "After merge, the elements in ls2 are: ";
show(ls2);
// reverse
ls2.reverse();
cout << "After reverse, the elements in ls2 are: ";
show(ls2);
// sort
ls2.sort();
cout << "After sort, the elements in ls2 are: ";
show(ls2);
return 0;
}
/*
After splice, the elements in ls are:
After splice, the elements in ls2 are: 2 3 4 1
After remove, the elements in ls2 are: 2 4
After unique, the elements in ls2 are: 1 3 6
After merge, the elements in ls2 are: 1 2 3 4 5
After reverse, the elements in ls2 are: 5 4 3 2 1
After sort, the elements in ls2 are: 1 2 3 4 5
*/
总结
list适用于需要频繁地在中间进行插入或删除操作的情况。当向某个位置插入元素时，该位置以及之后的元素仍保存原来的顺序，由于链表使用指针将所有元素“串”起来，因此插入操作只需要修改几个相邻的指针，不需要像vector那样移动元素，因此这个操作是常数复杂度。
需要谨记的是，如果需要随时获取位于某个下标的元素，list的效率会很差，需要从开始位置一个一个地找下去，如果需要频繁执行这样地操作，使用list可能不是一个好想法。
本文由kedixa发表于个人博客，
转载请注明作者及出处。
本文链接：https://blog.kedixa.top/2016/cpp-container-list/