文章目录

• 1、list的基本介绍
• 2、list的常用接口
• • 2.1、list的构造
  • 2.2、list iterator的使用
  • 2.3、list capacity
  • 2.4、list element access
  • 2.5、list modifiers
  • 2.6、list迭代器的实现方式
  • 2.7、list 迭代器失效
• 3、list部分功能模拟实现
• • 3.1 结点
  • 3.2 正向迭代器
  • 3.3 反向迭代器
  • 3.4 list主体
• 4、vector和list对比

1、list的基本介绍

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

2、list的常用接口

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口：

2.1、list的构造

2.2、list iterator的使用

注意
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

2.3、list capacity

2.4、list element access

2.5、list modifiers

除上述之外，list还有其他一些操作，如果需要了解，请点击——》点击跳转

2.6、list迭代器的实现方式

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
   2.1指针可以解引用，迭代器的类中必须重载operator*()
   2.2指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
   2.3指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)，至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载
   4.2迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

2.7、list 迭代器失效

迭代器就是对指针进行封装的一个类。迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

//错误写法void TestListIterator1(){ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值 l.erase(it);  ++it; }}//正确写法void TestListIterator(){  int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };  list<int> l(array, array+sizeof(array)/sizeof(array[0]));  auto it = l.begin();  while (it != l.end())  {    l.erase(it++); // it = l.erase(it);  }}

3、list部分功能模拟实现

3.1 结点

template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data; //_prev和_next指针先置空，再实际进行链接的时候再做出来ListNode(const T& data = T())//如果没data没给值，则data会通过T类型去构造， //因为这里const进行了修饰，所以延长了data的生命周期，后面的构造函数也是类似的: _prev(nullptr) , _next(nullptr), _data(data){}};

3.2 正向迭代器

//      template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* x):_node(x){}//it1 = it2或者it2(it1)---》浅拷贝即可//析构函数//为什么上述拷贝和析构不需要我们自己实现//因为迭代器的意义就是为了访问和修改容器中的数据//结点属于链表，不属于迭代器，所以也不需要释放//都不需要自己实现，默认生成的即可//重载*(解引用)Ref operator*(){return _node->_data;}//重载->Ptr operator->(){return &_node->_data;}//重载前置++self& operator++(){_node = _node->_next;return *this;}//重载后置++//因为tmp是个局部变量，出来作用域会被析构，所以这里返回self，而不是引用self operator++(int)//占位参数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!=(const self& it) const{return _node != it._node;}//重载等于bool operator==(const self& it) const{return _node == it._node;}};

3.3 反向迭代器

//反向迭代器就是对正向迭代器的封装//template <class Iterator, class Ref, class Ptr>class reverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> self;public:reverse_iterator(Iterator it):_it(it){}//重载*(解引用)Ref operator*(){Iterator prev = _it;return *--prev;//注意这里是去调用正向迭代器的--,而不是当前类(反向迭代器)的--//再进*，返回迭代器中的data的引用}//重载->Ptr operator->(){return &operator*();//跟上面类似，不过返回的是data的指针}//重载前置++self& operator++(){--_it;return *this;}//重载前置--self& operator--(){++_it;return *this;}//bool operator==(const self& it) const，如果这里不加const，则下面也不加，如果加了const相当于权限的放大//    如果这里加了const，则下面可加可不加bool operator==(const self& rit) const{return _it == rit._it;}bool operator!=(const self& rit) const//这里加const的原因也和上面一样{return _it != rit._it; }private:Iterator _it;};

3.4 list主体

template<class T>class list{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;void InitHead()//后面调用该函数是为了解决nullptr的问题{_head = new Node();_head->_next = _head;_head->_prev = _head;}list(){InitHead();}传统写法lt2(lt1)//list(const list& lt)//{//  InitHead();//for (auto e : lt)//{//push_back(e);//}//}传统写法lt2 = lt1//list& operator=(const list& lt)//{//if (this != &lt)//比较两个list 指针，判断是否是自己给自己赋值//{//clear();//for (auto e : lt)//{//push_back(e);//}//}//return *this;//}list(size_t n, const T& val = T())//如果没val没给值，则val会通过T模板去构造，因为这里const进行了修饰，所以延长了val的生命周期{InitHead();for (size_t i = 0; i < n; i++){push_back(val);}}//list(5,5)是去调用list(size_t n, const T& val = T())还是list(InputIterator first, InputIterator last)//当然是去掉用后者，因为后者的类型更加匹配//调用了后者，因为first被推导出来是个int类型，但push_back(*first)中对int进行解引用，所以会报错//所以就需要我们实现一个list的重载 //当我们进行重载后，list(5,5)就会调用重载版本，因为虽然list(int n, const T& val = T())和list(InputIterator first, InputIterator last)//类型都是最匹配的，但list(InputIterator first, InputIterator last)会进行类型推导，所以编译器选择不需要类型推导的list(int n, const T& val = T())list(int n, const T& val = T()){InitHead();for (int i = 0; i < n; i++){push_back(val);}}//现代写法template<class InputIterator>list(InputIterator first, InputIterator last)//给定一个迭代器区间进行构造{InitHead();while (first != last){push_back(*first);++first;}}//现代写法//lt2(lt1)list(const list<T>& lt){InitHead();list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}//现代写法//lt2 = lt1list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}reverse_iterator rbegin(){return reverse_iterator(end());//调用end(),返回_end的迭代器，再用这个迭代器去构造reverse_iterator}reverse_iterator rend(){return reverse_iterator(begin());}//返回第一个结点的迭代器iterator begin(){//因为有_head,所以就返回下一个结点的iteratorreturn iterator(_head->_next);}iterator end(){//因为所有迭代器的end是有效数据的下一个位置，所以返回_headreturn iterator(_head);}//const对象调用const_iterator begin() const{return const_iterator(_head->_next);}//const对象调用const_iterator end() const{return const_iterator(_head);}//对头和尾进行操作，都可以对inserthe 和 erase 进行复用void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x);//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//上面的代码等价于下面这句insert(end(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}//pos不失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//连接操作cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;return iterator(newnode);}//因为pos._node已经被释放，所以pos失效iterator erase(iterator pos){//_head结点要在最后再释放，因为_head不是有效结点(_head结点不存放有效数据)assert(pos != end());//连接操作Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;//因为删除之后iterator失效，所以返回删除数据的后一个数据的迭代器return iterator(next);}void clear(){iterator it = begin();//begin就是_head->nextwhile (it != end())//end就是_head{//iterator del = it++;//delete del._node;//erase(del);erase(it++);}_head->_next = _head->_prev = _head;//结点删除完了需要让_head中指针的指向自己}~list(){clear();//先把除头结点之外的其他结点释放掉delete _head;//再将头结点释放_head = nullptr;}private:Node* _head;};

4、vector和list对比