资讯专栏INFORMATION COLUMN

【C++】list详解

wanghui / 3390人阅读

摘要:结果我们发现,好像没多大问题,但是我们尝试修改迭代器里面的内容时,却发现能修改成功。注意为两个迭代器之间的距离。报错这里的报错说的是不在我们的迭代器当中,这个是对我们迭代器类型的一个检查。当中为迭代器添加了如下声明来解决这个问题。


前言

list相较于vector来说会显得复杂,它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度。


一、list的节点

</>复制代码

  1. template <class T>struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data;};

这个是在stl3.0版本下的list的节点的定义,节点里面有一个前指针,一个后指针,有一个数据data。这里只能知道他是一个双向链表,我们可以再稍微看一下list关于它的构造函数

</>复制代码

  1. class list --> list() { empty_initialize(); void empty_initialize() { node = get_node(); node->next = node; node->prev = node; }

再看一下它的list(),可以看出他调用的empty_initialize(),是创建了一个头结点,并且是一个循环的结构。

综上:list的总体结构是一个带头循环双向链表



二、list的迭代器

迭代器通常是怎么使用的,看一下下面这段代码。

</>复制代码

  1. int main(){
  2. list<int> l;
  3. l.push_back(1);
  4. l.push_back(2);
  5. l.push_back(3);
  6. l.push_back(4);
  7. l.push_back(5);
  8. l.push_back(6);
  9. list<int>::iterator it = l.begin();
  10. while (it != l.end())
  11. {
  12. cout << *it << " ";
  13. it++;
  14. }
  15. cout << endl;
  16. return 0;}
  • 我们从list< int >当中定义一个iterator对象,然后让他去访问我们的节点
  • 并且他所支持的操作有++,解引用,当然还有 --等等

stl3.0当中的迭代器实现:

</>复制代码

  1. template<class T, class Ref, class Ptr>struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } reference operator*() const { return (*node).data; }#ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); }#endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; }

大家感兴趣可以先看看上面的,我们先用一个简述版的来带大家简要实现一下

</>复制代码

  1. template<class T>
  2. class __list_node
  3. {
  4. public:
  5. __list_node(const T& val = T())//用一个全缺省比较好
  6. :_next(nullptr)
  7. ,_pre(nullptr)
  8. ,node(val)
  9. {}
  10. public:
  11. __list_node<T>* _next;
  12. __list_node<T>* _pre;
  13. T node;
  14. };
  15. template<class T>
  16. class __list_itertaor//这里是迭代器
  17. {
  18. public:
  19. typedef __list_node<T> Node;
  20. __list_itertaor(Node* node)
  21. {
  22. _node = node;
  23. }
  24. bool operator!=(const __list_itertaor<T>& it)
  25. {
  26. return _node != it._node;
  27. }
  28. __list_itertaor<T>& operator++()
  29. {
  30. _node = _node->_next;
  31. return *this;
  32. }
  33. T& operator*()
  34. {
  35. return _node->node;
  36. }
  37. private:
  38. Node* _node;
  39. };

这里的实现是不完整的,但是很适合说明问题。通过我们去重载opertaor++,和重载opertaor*,可以让我们像指针一样去访问一个节点,让我们可以跟vector和string一样用同样的接口就能实现对数据的访问,这是非常厉害的一个技术。

注意点:

  • 我们通过对节点的操作,重载了operator++等接口实现了对一个节点的访问,访问的时候实际上也就是创建迭代器对象,对我们的数据进行访问,所以我们封装的时候是将节点的指针进行封装。
  • list相比vector,正因为他们的底层结构不相同,list的迭代器在插入操作和接合操作(splice)都不会造成迭代器失效,只有删除的时候,只有那个被删除元素的迭代器失效,而不影响后面的,而vector就统统失效了。

2.1、模板参数为什么是三个

2.2 const 迭代器

有这样一种情况,我们需要const对象去遍历,假如我们有个函数叫做print_list(const list< int >& lt);
传参: 其中传参中const是因为不会对对象进行修改,加引用是因为不用深拷贝,提高效率。
功能: 这个函数就是去打印链表里面的内容的。但是按照我们上面的实现,会出现什么问题呢。

这很正常,在const迭代器就去生成const迭代器对象,在vector,string这些迭代器就是原生指针的时候我们只需要typedef const T* const_iterator,那如果我们在我们生成的list也做类似的操作,来看看结果。

结果我们发现,好像没多大问题,但是我们尝试修改const迭代器里面的内容时,却发现能修改成功。const迭代器怎么能修改里面的数据呢?这就有问题了!!!说明我们的有一个巨大的隐患在里面。

2.3 修改方法

最简单的方法当然就是再写多一个迭代器,把__list_iterator换成__list_const_iterator 之类的,但是我们认真观察的话,实际上这两个类很多东西是重复的,只有在operator*,operator->时所需要的返回值,我们需要找到一种方法去让const对象的返回值也是const对象,答案就是添加多两个个模板参数。
以下以添加一个模板参数为例,实现一个Ref operator*();

</>复制代码

  1. template<class T>
  2. class __list_node
  3. {
  4. public:
  5. __list_node(const T& val = T())//用一个全缺省比较好
  6. :_next(nullptr)
  7. ,_pre(nullptr)
  8. ,node(val)
  9. {}
  10. public:
  11. __list_node<T>* _next;
  12. __list_node<T>* _pre;
  13. T node;
  14. };
  15. template<class T,class Ref>
  16. class __list_itertaor
  17. {
  18. public:
  19. typedef __list_node<T> Node;
  20. __list_itertaor(Node* node)
  21. {
  22. _node = node;
  23. }
  24. bool operator!=(const __list_itertaor<T,Ref>& it)
  25. {
  26. return _node != it._node;
  27. }
  28. __list_itertaor<T,Ref>& operator++()
  29. {
  30. _node = _node->_next;
  31. return *this;
  32. }
  33. Ref operator*()//返回Ref,返回值就有区别啦
  34. {
  35. return _node->node;
  36. }
  37. private:
  38. Node* _node;
  39. };
  40. template<class T>
  41. class list
  42. {
  43. typedef __list_node<T> Node;
  44. public:
  45. typedef __list_itertaor<T,T&> iterator;
  46. typedef __list_itertaor<T, const T&> const_iterator;//修改
  47. iterator begin()
  48. {
  49. return iterator(_node->_next);
  50. }
  51. iterator end()
  52. {
  53. return iterator(_node);
  54. }
  55. const_iterator begin()const
  56. {
  57. return const_iterator(_node->_next);
  58. }
  59. const_iterator end()const
  60. {
  61. return const_iterator(_node);
  62. }
  63. list()
  64. {
  65. _node = new Node;
  66. _node->_next = _node;
  67. _node->_pre = _node;
  68. }
  69. void push_back(const T& val)
  70. {
  71. Node* newnode = new Node(val);
  72. Node* tail = _node->_pre;
  73. tail->_next = newnode;
  74. newnode->_pre = tail;
  75. newnode->_next = _node;
  76. _node->_pre = newnode;
  77. }
  78. private:
  79. Node* _node;
  80. };

一图了解:也就是我们的测试端test函数中定义list< int >::const_iterator cit= l.begin();的时候迭代器对象就会识别到定义的const迭代器,它的第二个模板参数放的就是const T&,这样子我们operator*()返回的时候只需要返回第二个模板参数就可以了

同理,我们要用到的接口operator->当中也会有const对象和普通对象调用的情况。我们这里把实现的代码放出来,有需要的自取。

–》码云链接《–



二、美中不足

list上面说的仿佛都是优点

任意位置的O(1)时间的插入删除,迭代器失效的问题变少了。但他又有哪些不足呢

  • 不支持随机访问
  • 排序的效率慢,库中的sort用的是归并排序–>快排需要三数取中,对于链表来说实现出来效率也低,所以当链表的元素需要进行排序的时候,我们通常也都会拷贝到vector当中,再用vector当中的排序。
  • 同理链表的逆置效率也不高!


三、迭代器的分类

迭代器从功能角度来看的话分为:const迭代器/普通迭代器 + 正反向。

从容器底层结构角度分为:单向,双向,随机。

  • 单向: 单链表迭代器(forward_list)/哈希表迭代器;这些只支持单向++;
  • 双向: 双链表迭代器/map迭代器;这些支持的++/- -操作;
  • 随机迭代器: string/vector/deque;这些是支持++/- -/+/-操作的,类似原生指针一般。

我们来看一下部分函数的,比如sort当中的模板参数写成RandomAccessIterator,就是想要明示使用者他这里需要的是一个随机的迭代器,在它的底层会调用到迭代器的+操作,所以这个时候如果你传的是一个双向或者单向的迭代器就不行了!!

</>复制代码

  1. //sort的函数声明template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);custom (2)
  2. template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

比如说reverse函数声明,它的模板参数是BidirectionalIterator,也就是需要一个支持双向的迭代器,这个时候其实我们就可以传随机迭代器和双向迭代器,从上面的迭代器支持的操作可以看到,随机迭代器是支持双向迭代器的所有操作的
同理,如果是一个需要单向迭代器的地方,我们就可以传一个双向,随机,单向迭代器了!!

</>复制代码

  1. std::reversetemplate <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last);

从stl3.0当中的stl_iterator.h,我们可以看出当中的继承关系。这个我们之后再讲。

注意:difference_type为两个迭代器之间的距离。类型ptrdiff_t为无符号整形。



3.x std::find的一个报错

当我们实现了自己的数据结构,如list,我们如果用库里的std:find查找我们实现的数据结构当中的数据会报错。博主的测试版本为vs2013,在其他版本可能不做检查,不会报错。

</>复制代码

  1. void test_list()
  2. {
  3. list<int> l;
  4. l.push_back(5);
  5. list<int>::iterator it = std::find(l.begin(), l.end(), 5);
  6. }

报错:这里的报错说的是iterator_category不在我们的迭代器当中,这个是对我们迭代器类型的一个检查。



stl_list.h当中为迭代器添加了如下声明来解决这个问题。

解决方案: 我们可以用stl3.0版本下stl_list.h当中的迭代器的声明。也可以用release版本下,都是可以跑过的。

</>复制代码

  1. typedef bidirectional_iterator_tag iterator_category;
  2. typedef T value_type;
  3. typedef Ptr pointer;
  4. typedef Ref reference;
  5. typedef ptrdiff_t difference_type;



总结

list的讲解就到这里啦,看到这里不妨一键三连。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/124088.html

相关文章

  • 聊聊Java的泛型及实现

    摘要:静态变量是被泛型类的所有实例所共享的。所以引用能完成泛型类型的检查。对于这个类型系统,有如下的一些规则相同类型参数的泛型类的关系取决于泛型类自身的继承体系结构。事实上,泛型类扩展都不合法。 前言 和C++以模板来实现静多态不同,Java基于运行时支持选择了泛型,两者的实现原理大相庭径。C++可以支持基本类型作为模板参数,Java却只能接受类作为泛型参数;Java可以在泛型类的方法中取得...

    lewif 评论0 收藏0
  • C++IO流详解

    摘要:在使用时候必须要包含头文件并引入标准命名空间。在该头文件下,标准库三个类进行流的输入进行流的输出进行流的输入输出将结构体的内容转换成字符串字符串的内容输出到结构体当中注意实际是在其底层维护了一个类型的对象用来保存结果。 ...

    trilever 评论0 收藏0
  • [零基础学python]大话题小函数(1)

    摘要:开篇就要提到一个大的话题编程范型。例如,在面向对象编程中,程序员认为程序是一系列相互作用的对象,而在函数式编程中一个程序会被看作是一个无状态的函数计算的串行。 开篇就要提到一个大的话题:编程范型。什么是编程范型?引用维基百科中的解释: 编程范型或编程范式(英语:Programming paradigm),(范即模范之意,范式即模式、方法),是一类典型的编程风格,是指从事软件工程...

    xiguadada 评论0 收藏0
  • Python垃圾回收详解

    摘要:而采用的是引用计数机制为主,标记清理和分代收集两种机制为辅的策略。现在我们先去考虑一下,什么情况下引用计数,什么情况下,当引用次数为时,肯定就是需要进行回收的时刻。引用计数机制缺点维护引用计数需要消耗一定的资源循环应用时,无法回收。 上一篇文章:私有化规则与属性Property下一篇文章:Python进程专题总览篇 高级语言一般都有垃圾回收机制,其中c、c++使用的是用户自己管维护内...

    leo108 评论0 收藏0
  • 手把手写C++服务器(31):服务器性能提升关键——IO复用技术【两万字长文】

    摘要:前面几讲手撕了网关服务器回显服务器服务的代码,但是这几个一次只能监听一个文件描述符,因此性能非常原始低下。复用能使服务器同时监听多个文件描述符,是服务器性能提升的关键。表示要操作的文件描述符,指定操作类型,指定事件。  本系列文章导航: 手把手写C++服务器(0):专栏文章-汇总导航【更...

    big_cat 评论0 收藏0

发表评论

0条评论

wanghui

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<