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可能不是一个好想法。
0
本文由kedixa发表于个人博客,
转载请注明作者及出处。
本文链接:https://blog.kedixa.top/2016/cpp-container-list/