list的介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，让其更简单高效。与其他的序列式容器相比(vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息。使用 list 时必须加上头文件#include<list>和using namespace std;

list的基本使用

list的构造

构造函数接口说明list()构造空的listlist(size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素list(const list& x)拷贝构造函数list(InputIterator first, InputIterator last)用[first, last)区间中的元素构造list list<int> l1; // 构造空的l1 list<int> l2(4, 100); // l2中放4个值为100的元素 list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3 list<int> l4(l3); // 用l3拷贝构造l4 int arr[] = { 16,2,77,29 }; // 以数组为迭代器区间构造l5 list<int> l5(arr, arr + sizeof(arr) / sizeof(arr[0]));

list迭代器的使用

函数声明接口说明begin + endbegin返回第一个元素的迭代器 + end返回最后一个元素下一个位置的迭代器rbegin + rendrbegin返回最后一个元素的reverse_iterator + rend返回第一个元素上一个位置的reverse_iterator

#include <iostream> #include <list> using namespace std; void PrintList(const list<int>& l) { list<int>::const_iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } cout << endl; } int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0])); // 使用正向迭代器正向打印list中的元素 list<int>::iterator it1 = l.begin(); while (it1 != l.end()) { cout << *it1 << " "; ++it1; } cout << endl; // 使用反向迭代器逆向打印list中的元素 list<int>::reverse_iterator it2 = l.rbegin(); while (it2 != l.rend()) { cout << *it2 << " "; ++it2; } cout << endl; //使用const迭代器正向打印list中的元素 PrintList(l); return 0; }

list的空间

函数声明接口说明empty检测list是否为空，是返回true，否则返回falsesize返回list中有效节点的个数

list的元素访问

函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用

list的增删操作

函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在 pos 位置中插入值为val的元素erase删除 pos 位置的元素swap交换两个list中的元素clear清空list中的有效元素 #include <iostream> #include <list> #include <vector> using namespace std; void PrintList(list<int>& l) { for (auto& e : l) { cout << e << " "; } cout << endl; } //push_back、pop_back、push_front、pop_front void TestList1() { int arr[] = { 1, 2, 3 }; list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0])); // 在list的尾部插入4，头部插入0 l.push_back(4); l.push_front(0); PrintList(l); // 删除list尾部节点和头部节点 l.pop_back(); l.pop_front(); PrintList(l); } //insert、erase void TestList2() { int arr[] = { 1, 2, 3 }; list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0])); // 获取链表中第二个节点 auto pos = ++l.begin(); cout << *pos << endl; // 在pos前插入值为4的元素 l.insert(pos, 4); PrintList(l); // 在pos前插入5个值为5的元素 l.insert(pos, 5, 5); PrintList(l); // 在pos前插入[v.begin(), v.end)区间中的元素 vector<int> v{ 7, 8, 9 }; l.insert(pos, v.begin(), v.end()); PrintList(l); // 删除pos位置上的元素 l.erase(pos); PrintList(l); // 删除list中[begin, end)区间中的元素，即删除list中的所有元素 l.erase(l.begin(), l.end()); PrintList(l); } //resize、swap、clear void TestList3() { int arr[] = { 1, 2, 3 }; list<int> l1(arr, arr + sizeof(arr) / sizeof(arr[0])); PrintList(l1); // 交换l1和l2中的元素 list<int> l2; l1.swap(l2); PrintList(l1); PrintList(l2); // 将l2中的元素清空 l2.clear(); cout << l2.size() << endl; }

list的迭代器失效

和vector不同的是，list插入数据时不会引起迭代器失效，因为每个节点之间都是相互独立的且不需要扩容，则迭代器的指向不会被改变。erase数据时迭代器会失效，删除数据后，节点被释放，迭代器的指向非法，需要重新赋值。

list的模拟实现（造轮子）

#pragma once #include <iostream> #include <cassert> using namespace std; namespace MakeList { template<class T> struct ListNode { ListNode* _prev; ListNode* _next; T _data; ListNode(const T& data = T()) : _prev(nullptr) , _next(nullptr) , _data(data) {} }; template<class T, class Ref, class Ptr> struct ListIterator { typedef ListIterator<T, Ref, Ptr> Self; typedef ListNode<T> Node; Node* _node; ListIterator(Node* node) : _node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } Self operator--() { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(Self it) { return _node != it._node; } bool operator==(Self it) { return _node == it._node; } }; template<class T> class list { public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; private: typedef ListNode<T> Node; public: iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } list() : _head(nullptr) { _head = new Node; _head->_next = _head; _head->_prev = _head; } ~list() { clear(); delete _head; _head = nullptr; } //拷贝构造 list(const list<T>& l) : _head(nullptr) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto e : l) { push_back(e); } } //赋值运算符传统写法 //list<T>& operator=(const list<T>& l) //{ // if (this != &l) // { // clear(); // for (auto e : l) // { // push_back(e); // } // } // return *this; //} //赋值运算符现代写法 list<T>& operator=(list<T> l) { std::swap(_head, l._head); return *this; } void clear() { iterator it = begin(); while (it != end()) { erase(it++); } } void push_back(const T& val) { Node* tail = _head->_prev; Node* new_node = new Node(val); tail->_next = new_node; new_node->_prev = tail; _head->_prev = new_node; new_node->_next = _head; } void pop_back() { assert(_head->_prev != nullptr); Node* tail = _head->_prev; Node* prev = tail->_prev; delete tail; _head->_prev = prev; prev->_next = _head; } void push_front(const T& val) { Node* cur = _head->_next; Node* new_node = new Node(val); _head->_next = new_node; new_node->_prev = _head; new_node->_next = cur; cur->_prev = new_node; } void pop_front() { assert(_head->_next != nullptr); Node* cur = _head->_next; Node* next = cur->_next; delete cur; _head->_next = next; next->_prev = _head; } iterator insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = cur->_prev; Node* new_node = new Node(val); prev->_next = new_node; new_node->_prev = prev; new_node->_next = cur; cur->_prev = new_node; return pos; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; prev->_next = next; next->_prev = prev; return iterator(next); } private: Node* _head; }; }