【C++】list

---

1. 简单了解list

1. list的底层是带头双向循环列表。
2. 因此list支持任意位置的插入和删除，且效率较高。但其缺陷也很明显，由于各节点在物理空间是不连续的，所以不支持对任意位置的访问，效率低。
3. list的迭代器底层不仅仅是指针这么简单，因为其迭代器支持前后双向迭代，而其空间又不连续，所以其底层是对指针的封装。（后面讲）

2. list的常见接口

1. 构造

例子

2. 普通迭代器

与其他容器的迭代器一样，只不过list的底层实现更加复杂，现在暂且将其看成指针。
例子

//迭代器
void test3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}
//运行结果：
//1 2 3 4

3. 头插头删和尾插尾删

例子

void test2()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();lt.push_front(4);lt.push_front(3);lt.push_front(2);lt.push_front(1);for (auto e : lt){cout << e << " ";}cout << endl;
}
//运行结果：
//1 2 3 4
//1 2 3 4

4. 插入

例子

void test3()
{list<int> lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);//想在第二个位置插入2，怎么做//lt.insert(lt.begin()+1,2);//错误的，list的iterator没有重载+。这个等下讲原因。auto it = lt.begin();++it;lt.insert(it, 2);for (auto e : lt){cout << e << " ";}cout << endl;
}
//运行结果：
//1 2 3 4

这样确定插入位置太麻烦了，可以用find查找。

auto it = find(lt.begin(),lt.end(),3);
if (it != lt.end())
{lt.insert(it,2);
}

5. 删除

例子

	//删除偶数//删除后，迭代器还指向被删除空间，存在迭代器失效问题//所以要重新赋值it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){it = lt.erase(it);}else{++it;}}

6. front和back

例子

7. 逆置和排序

例子

void test5()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.reverse();for (auto e : lt){cout << e << " ";}cout << endl;lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;
}
//运行结果
//4 3 2 1
//1 2 3 4

拓展
（1）库里也有sort，为什么还要在list再写一个？C++库的sort不能用。
（2）这涉及到迭代器的分类。从功能上，由容器底层结构决定，迭代器有单项迭代器、双向迭代器和随机迭代器。单项迭代器只能++，向后迭代，例如forward_list/unordered_xxx的迭代器；双向迭代器能++/–，例如list/map/set；随机迭代器能+/-/++/–，例如string/vector/deque。
（3）有随机迭代器的容器能用随机的、双向的、单向的迭代器的库函数，有双向迭代器的容器能用双向的、单向的迭代器的库函数。
（4）list的迭代器类型是双向的，库函数sort的迭代器类型是随机的，所以list的数据排序不能用库函数sort。

8. 归并

例子

void test6()
{list<int> lt1;lt1.push_back(1);lt1.push_back(3);lt1.push_back(5);lt1.push_back(7);list<int>lt2;lt2.push_back(2);lt2.push_back(4);lt2.push_back(6);lt2.push_back(8);lt1.merge(lt2);for (auto e : lt1){cout << e << " ";}cout << endl;cout << "lt1的大小为：" << lt1.size() << endl;cout << "lt2是否变为空：" << lt2.empty() << endl;
}

9. unique

例子

	list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(2);lt1.push_back(2);lt1.unique();cout << "lt1的大小：" << lt1.size() << endl;for (auto e : lt1){cout << e << " ";}cout << endl;

10. remove

	list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(2);lt1.push_back(2);lt1.remove(1);//相当于find+erasecout << "lt1的大小：" << lt1.size() << endl;for (auto e : lt1){cout << e << " ";}cout << endl;

remove不像erase，它的参数是值而不是迭代器，且remove如果要移除的值不存在，不会报错。

11. splice

	list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2;lt2.push_back(5);lt2.push_back(6);lt2.push_back(7);lt2.push_back(8);lt1.splice(lt1.begin(), lt2);//将lt2的所有节点全部转移到lt1之前lt1.splice(lt1.begin(), lt2,--lt2.end());//将lt2的最后一个元素转移到lt1之前lt1.splice(lt1.begin(), lt2, ++lt2.begin(), lt2.end());//将迭代器区间的节点转移到lt1之前lt1.splice(lt1.begin(), lt1, ++lt1.begin(), lt1.end());//将lt1第一个节点后面的节点转移到lt1之前for (auto e : lt1){cout << e << " ";}cout << endl;

---

3. 简单实现list

#include<iostream>
using namespace std;namespace zn
{//节点template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _val;ListNode(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};//迭代器（双向迭代器）//迭代器底层都是指针，但有些指针需要封装，例如节点的指针，不然不能满足++/--等操作template<class T, class Ref, class Ptr>//T == T, Ref == T&/const T&, Ptr == T*/const T*struct __list_iterator{typedef ListNode<T>* iterator;typedef __list_iterator<T, Ref, Ptr> This;iterator _node;//构造__list_iterator(iterator node):_node(node){}//*重载Ref operator*(){return _node->_val;}//->重载//如果T恰好是结构体类型，而迭代器又被看成指针，那么->就可以派上用场Ptr operator->(){return &(_node->_val);}//++重载This& operator++(){_node = _node->_next;return *this;}This operator++(int){This tmp(_node);_node = _node->_next;return tmp;}//--重载This& operator--(){_node = _node->_prev;return *this;}This operator--(int){This tmp(_node);_node = _node->_prev;return tmp;}//==重载和!=重载bool operator==(__list_iterator lit)const{return _node == lit._node;}bool operator!=(__list_iterator lit)const{return !(_node == lit._node);}};//反向迭代器//对正向迭代器的封装，从而得到我们想要的操作template<class T,class Ref,class Ptr>class ReverseIterator{typedef __list_iterator<T, Ref, Ptr> iterator;typedef	ReverseIterator<T, Ref, Ptr> reverse_iterator;iterator _it;ReverseIterator(iterator it):_it(it){}public:Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}reverse_iterator& operator++(){--_it;return *this;}reverse_iterator operator++(int){reverse_iterator tmp = *this;--_it;return tmp;}reverse_iterator& operator--(){++_it;return *this;}reverse_iterator operator--(int){reverse_iterator tmp = *this;++_it;return tmp;}bool operator!=(const reverse_iterator& rit){return _it != rit._it;}bool operator==(const reverse_iterator& rit){return _it == rit._it;}};//listtemplate<class T>class list{typedef ListNode<T> Node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<T, T&, T*> reverse_iterator;typedef ReverseIterator<T, const T&, const T*> const_reverse_iterator;public://构造list(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}//拷贝构造list(const list<T>& lt)//list(const list& lt){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;for (auto& e : lt){push_back(e);}_size = lt._size;}//交换void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//=重载list<T> operator=(list<T> lt){swap(lt);return *this;}//析构~list(){Node* cur = _head->_prev;while (cur != _head){Node* tmp = cur->_next;delete cur;cur = tmp;}delete _head;_head = nullptr;}//迭代器iterator begin(){return _head->_next;}const_iterator begin()const{return _head->_next;}iterator end(){return _head;}const_iterator end()const{return _head;}reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}//插入（默认在pos前插入）iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;++_size;//隐式类型转换//返回指针类型，然后用类类型接收，会调用构造return newnode;}//删除iterator earse(iterator pos){//头节点不能删除，否则析构时会报错assert(pos != end());Node* cur = pos->_node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}//尾插和尾删void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}//头插和头删void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}//大小size_t size(){return _size;}//清理void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private://指向头节点Node* _head;size_t _size;};void test_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;}
}

---

4. vector和list比较

	vector	list
底层	顺序表，可扩容	双向循环链表，带头节点
效率	具有连续的空间，空间利用率高；访问元素效率高，支持随机访问；插入和删除元素效率低，需要挪动元素，时间复杂度为O(N)	底层开辟节点，空间利用率低；访问元素效率低，不支持随机访问； 插入和删除元素效率高，时间复杂度为O(1)
迭代器	是原生态指针；是随机迭代器，支持+/-等操作；无论是插入还是删除，都会导致迭代器失效（插入需要扩容，扩容后原来的迭代器失效）	是对原生态指针的封装；是双向迭代器，不支持+/-等操作 ；删除会导致迭代器失效
应用	适用于插入和删除操作少，访问多的情况	适用于插入和删除操作多，访问少的情况

---