0
0

C++STL之list

目录

1.list****的使用

构造函数

**接口说明 **

**list (size_type n, const value_type& val = **

**value_type()) **

*构造的list中包含n个值为val*的 **

元素

*list() **
构造空的list*
**list (const list& x) **
拷贝构造函数
list (InputIterator first, InputIterator last

用**[first, last)****区间中的元素构造 **

**list **

**2.list iterator的使用 **

可以将迭代器理解成一个指针，该指针指向list中的某个节点

函数声****明

接口说明

begin +

**end **

返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

**rbegin **

  • **rend **

*返回第一个元素的*reverse_iterator,即end**位置，返回最后一个元素下一个位 **

*置的*reverse_iterator,即begin*位置*

**【注意】 **

  1. begin与end**为正向迭代器，对迭代器执行++****操作，迭代器向后移动 **

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

**3.list的常用接口 **

**函数声明 **
接口说明
empty

检测list是否为空，是返回true，否则返回****false

*size **
返回list中有效节点的个数
*front **
返回*list的第一个节点中值的引用
*back **
返回*list的最后一个节点中值的引用
*push_front **
在*list首元素前插入值为val*的元素
pop_front

删除list中第一个元素

*push_back **
在list尾部插入值为val的元素
*pop_back **
删除*list中最后一个元素
*insert **
在*list position 位置中插入值为val的元素
*erase **
删除*list position*位置的元素
**swap **

交换两个list中的元素

*clear **
清空list***中的有效元素 **

4.list****的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，**迭代器失效即迭代器所指向的节点的无 **

效，即该节点被删除了。因为list****的底层结构为带头结点的双向循环链表，因此*在list*中进行插入 **

*时是不会导致list*的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 **

代器，其他迭代器不会受到影响。

  1. void TestListIterator1()
  2. {
  3. int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  4. list<int> l(array, array+sizeof(array)/sizeof(array[0]));
  5. auto it = l.begin();
  6. while (it != l.end())
  7. {
  8. // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
  9. 其赋值
  10. l.erase(it);
  11. ++it;
  12. }
  13. }
  14. // 改正
  15. void TestListIterator()
  16. {
  17. int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  18. list<int> l(array, array+sizeof(array)/sizeof(array[0]));
  19. auto it = l.begin();
  20. while (it != l.end())
  21. {
  22. l.erase(it++); // it = l.erase(it);
  23. }
  24. }
5.list的模拟实现
  1. #pragma once
  2. #include<iostream>
  4. namespace bit
  5. {
  6.     template<class T>
  7.     struct list_node
  8.     {
  9.         T _data;
  10.         list_node<T>* _next;
  11.         list_node<T>* _prev;
  13.         list_node(const T& data = T())
  14.             :_data(data)
  15.             , _next(nullptr)
  16.             , _prev(nullptr)
  17.         {}
  18.     };
  20.     // const_iterator
  21.     template<class T>
  22.     struct list_iterator
  23.     {
  24.         typedef list_node<T> Node;
  25.         typedef list_iterator<T> Self;
  26.         Node* _node;
  28.         list_iterator(Node* node)
  29.             :_node(node)
  30.         {}
  32.         T& operator*()
  33.         {
  34.             return _node->_data;
  35.         }
  37.         Self& operator++()
  38.         {
  39.             _node = _node->_next;
  40.             return *this;
  41.         }
  43.         Self& operator--()
  44.         {
  45.             _node = _node->_prev;
  46.             return *this;
  47.         }
  49.         bool operator!=(const Self& s) const
  50.         {
  51.             return _node != s._node;
  52.         }
  54.         bool operator==(const Self& s) const
  55.         {
  56.             return _node == s._node;
  57.         }
  58.     };
  60.     template<class T>
  61.     class list
  62.     {
  63.         typedef list_node<T> Node;
  64.     public:
  65.         typedef list_iterator<T> iterator;
  67.         iterator begin()
  68.         {
  69.             /*    iterator it(_head->_next);
  70.                 return it;*/
  71.                 //return iterator(_head->_next);
  72.             return _head->_next;
  73.         }
  75.         iterator end()
  76.         {
  77.             return _head;
  78.         }
  80.         list()
  81.         {
  82.             _head = new Node;
  83.             _head->_next = _head;
  84.             _head->_prev = _head;
  85.             _size = 0;
  86.         }
  88.         void push_back(const T& x)
  89.         {
  90.             /*Node* newnode = new Node(x);
  91.             Node* tail = _head->_prev;
  93.             tail->_next = newnode;
  94.             newnode->_prev = tail;
  95.             newnode->_next = _head;
  96.             _head->_prev = newnode;
  98.             ++_size;*/
  100.             insert(end(), x);
  101.         }
  103.         void push_front(const T& x)
  104.         {
  105.             insert(begin(), x);
  106.         }
  108.         void insert(iterator pos, const T& x)
  109.         {
  110.             Node* cur = pos._node;
  111.             Node* prev = cur->_prev;
  113.             Node* newnode = new Node(x);
  115.             // prev newnode cur
  116.             newnode->_next = cur;
  117.             cur->_prev = newnode;
  118.             newnode->_prev = prev;
  119.             prev->_next = newnode;
  121.             ++_size;
  122.         }
  124.         void pop_back()
  125.         {
  126.             erase(--end());
  127.         }
  129.         void pop_front()
  130.         {
  131.             erase(begin());
  132.         }
  134.         void erase(iterator pos)
  135.         {
  136.             assert(pos != end());
  138.             Node* prev = pos._node->_prev;
  139.             Node* next = pos._node->_next;
  141.             prev->_next = next;
  142.             next->_prev = prev;
  143.             delete pos._node;
  145.             --_size;
  146.         }
  148.         size_t size() const
  149.         {
  150.             return _size;
  151.         }
  153.         bool empty() const
  154.         {
  155.             return _size == 0;
  156.         }
  157.     private:
  158.         Node* _head;
  159.         size_t _size;
  160.     };
  161.     void test_list1()
  162.     {
  163.         list<int> lt;
  164.         lt.push_back(1);
  165.         lt.push_back(2);
  166.         lt.push_back(3);
  167.         lt.push_back(4);
  169.         list<int>::iterator it = lt.begin();
  170.         while (it != lt.end())
  171.         {
  172.             std::cout << *it << " ";
  173.             ++it;
  174.         }
  175.         std::cout << std::endl;
  176.     }
  177. }
6.list的反向迭代器

**通过前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++， **

**因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对 **

正向迭代器的接口进行包装即可。

  1. template<class Iterator>
  2. class ReverseListIterator
  3. {
  4. // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
  5. 成员变量
  6. // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
  7. // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
  8. public:
  9. typedef typename Iterator::Ref Ref;
  10. typedef typename Iterator::Ptr Ptr;
  11. typedef ReverseListIterator<Iterator> Self;
  12. public:
  13. //
  14. // 构造
  15. ReverseListIterator(Iterator it): _it(it){}
  16. //
  17. // 具有指针类似行为
  18. Ref operator*(){
  19. Iterator temp(_it);
  20. --temp;
  21. return *temp;
  22. }
  23. Ptr operator->(){ return &(operator*());}
  24. //
  25. // 迭代器支持移动
  26. Self& operator++(){
  27. --_it;
  28. return *this;
  29. }
  30. Self operator++(int){
  31. Self temp(*this);
  32. --_it;
  33. return temp;
  34. }
  35. Self& operator--(){
  36. ++_it;
  37. return *this;
  38. }
  39. Self operator--(int)
  40. {
  41. Self temp(*this);
  42. ++_it;
  43. return temp;
  44. }
  45. // 迭代器支持比较
  46. bool operator!=(const Self& l)const{ return _it != l._it;}
  47. bool operator==(const Self& l)const{ return _it != l._it;}
  48. Iterator _it;
  49. };
7.list与vector****的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及

应用场景不同，不同如下。

*vector **
list
底层结构*

**动态顺序表，一段连续空间 **

带头结点的双向循环链表

随机访****问

支持随机访问，访问某个元素效率****O(1)

*不支持随机访问，访问某个元 素效率O(N）*

插入和删****除

*任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更*低

任意位置插入和删除效率高，不需要搬移元素，时间复杂度为****O(1)

空间利用率

**底层为连续空间，不容易造成内存碎片，空间利用 **率高，缓存利用率高

底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低

迭代器

原生态指针

对原生态指针**(节点指针)****进行 **

封装

迭代器失效

在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失****效

插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不****受影响

*使***用 **

场****景

*需要高效存储，支持随机访问，不关心插入删除效***率 **

大量插入和删除操作，不关心****随机访问

标签： c++ 数据结构 链表
本文转载自: https://blog.csdn.net/zzzzz_ccc/article/details/143171879
版权归原作者 zzzzz_ccc 所有， 如有侵权，请联系我们删除。
登录后发布评论

“C++STL之list”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航
1.list****的使用