STL——list的先容和模拟实现

目次

前言
list的先容
list的模拟实现
节点：
list类
迭代器的实现
前置++/--
后置++/--
重载*
重载->
重载==/!=
begin()与end()
list的插入/删除
构造/析构函数
重载=
list模拟实现代码如下
小结

---

前言

本篇博客我们将要开始先容list这个容器，list是带头双向循环链表，STL标准模板库中实现了list如许方便我们去使用，那么本篇博客我们将脱下list的秘密外衣，先容它的使用以及模拟实现。
list的先容

list的底层是带头双向循环链表，可以在恣意位置完成插入删除的功能，相识其迭代器我们将更加深入相识C++封装的特性。与vector相比，list的最大缺陷是不支持随机访问，但由于其底层封装了迭代器，因此list是可以通过迭代器访问的。同时，由于list的结构是链状的，以是它在肯定程度上可以节流空间
下面我们来看一下list为我们提供的接口：
起首来看list的构造函数：

list与其他容器一样都提供了一个迭代器构造，initializer构造以及拷贝构造 
接下来是迭代器：

 容量操纵：

修改操纵：

list的模拟实现

这是这篇博客的重点，通过模拟实现list我们将更加深入相识list的底层结构，以及怎样使用
节点：

起首我们提供一个节点的类，这个类内里包含了prev指针，next指针以及我们要存储的数据data，如下所示：

1. template<class T>
2. struct ListNode
3. {
4.         ListNode<T>* _next;
5.         ListNode<T>* _prev;
6.         T _data;
7.         ListNode(const T& data = T()) :_next(nullptr), _prev(nullptr), _data(data);
8.         {}
9. };

复制代码

分析上述代码，我们看到，我们将这个类声明为struct而不是class，这是为什么呢？因为在后续的操纵过程中我们将频繁访问 节点当中的数据，假如声明成class，那么假如我们要访问内部的数据就要声明成友元大概内部类，如许会对阅读代码的人造成困扰，同时也不方便我们去操纵，以是在现实操纵过程中，假如瞥见了须要频繁操纵的数据，那么我们尽大概的让它声明成struct
同时，我们在这个节点类中提供了一个构造函数，如许可以使我们的程序更加安全可靠。
list类

有了节点后我们将用这个节点去创建一个list，因此我们此时须要一个list类，内里封装我们要实现list的各种操纵，其代码如下所示：

1. template<class T>
2. class list
3. {
4.         typedef ListNode<T> Node;
5. public:
7. private:
8.         Node* _head;
9. };

复制代码

起首我们搭建出list的框架，内里封装了一个头节点，其后续要实现的各种功能我们将在public中实现。同时，我们将ListNode<T>重新命名为了Node，如许是为了可读性考虑
迭代器的实现

我们知道，迭代器为容器提供了一种统一的访问形式，从而屏蔽了底层细节，方便人们使用和学习。前面我们实现了vector，它的迭代器是一个指针，那么对于list而言我们能用指针实现吗？答案是否定的，因为它的结构不是连续的，以是我们不能这么做，那么为了保证我们有一种统一的访问方式我们必须提供一个类去封装iterator，这个类内里得重载前置++，前置--，后置++，后置--，迭代器，解引用等功能，其结构如下所示：

1.         template<class T>
2.         struct ListIterator
3.         {
4.                 typedef ListNode<T> Node;
5.                 typedef ListIterator<T> Self;
6.                 Node* _node;
8.                 ListIterator(Node*node):_node(node)
9.                 {}
12.         };

复制代码

分析上述代码，我们可以看到，在这个迭代器类中我们保存了一个节点，以便访问节点中的数据，从而实现对节点的操纵，由于后续要频繁访问数据，以是我们同样将ListIterator声明为公有。
前置++/--

1. Self& operator++()
2. {
3.         _node = _node->_next;
4.         return *this;
5. }
6. Self& operator--()
7. {
8.         _node = _node->_prev;
9.         return *this;
10. }

复制代码

后置++/--

1. Self operator++(int)
2. {
3.         Self tmp(_node);
4.         _node = _node->_next;
5.         return tmp;
6. }
7. Self operator--(int)
8. {
9.         Self tmp(_node);
10.         _node = _node->_prev;
11.         return tmp;
12. }

复制代码

重载*

1. T& operator*()
2. {
3.         return _node->_data;
4. }

复制代码

重载->

1. T* operator->()
2. {
3.         return &_node->_data;
4. }

复制代码

重载==/!=

1. bool operator==(const Self&it)
2. {
3.         return _node == it._node;
4. }
5. bool operator!=(const Self& it)
6. {
7.         return _node != it._node;
8. }

复制代码

 由此，我们就完成了一个iterator，但是如许的代码显然移至性是很低的，为什么呢？因为在现实操纵过程中，我们常常会遇见const修饰的对象，那么对于其而言我们应该使用const迭代器去完成，那这该怎么办呢？有两种办理方法，一种是重新实现一个const类型的迭代器；另一种通过调用不同的模板参数去完成，显然第一种方法固然很简单，但是有很多重复的代码，以是我们在现实操纵中更多的是用第二种办理方法。
仔细观察上述代码，我们发现只有函数可以用const修饰，一个是T&，一个是T*，那么我们可以再加两个模板参数，一个负责T&，一个负责T*，那么我们就得到了下面的代码：

1. template<class T,class Ref,class Ptr>
2. struct ListIterator
3. {
4.         typedef ListNode<T> Node;
5.         typedef ListIterator<T,T&,T*> Self;
6.         Node* _node;
8.         ListIterator(Node*node):_node(node)
9.         {}
11.         Self& operator++()
12.         {
13.                 _node = _node->_next;
14.                 return *this;
15.         }
16.         Self& operator--()
17.         {
18.                 _node = _node->_prev;
19.                 return *this;
20.         }
22.         Self operator++(int)
23.         {
24.                 Self tmp(_node);
25.                 _node = _node->_next;
26.                 return tmp;
27.         }
28.         Self operator--(int)
29.         {
30.                 Self tmp(_node);
31.                 _node = _node->_prev;
32.                 return tmp;
33.         }
35.         Ref operator*()
36.         {
37.                 return _node->_data;
38.         }
40.         Ptr operator->()
41.         {
42.                 return &_node->_data;
43.         }
45.         bool operator==(const Self&it)
46.         {
47.                 return _node == it._node;
48.         }
49.         bool operator!=(const Self& it)
50.         {
51.                 return _node != it._node;
52.         }
53. };

复制代码

begin()与end()

当我们将list的迭代器类实现出来后我们就可以用迭代器访问这个类，因此我们应该在list这个类中提供一个接口，这个接口就是begin与end，其代码如下所视：

1. typedef ListIterator<T, T&, T*> iterator;
2. iterator begin()
3. {
4.         return iterator(_head->_next);
5. }
6. iterator end()
7. {
8.         return iterator(_head);
9. }
10. typedef ListIterator<T, const T&,const T*> const_iterator;
11. const_iterator begin()const
12. {
13.         return const_iterator(_head->_next);
14. }
15. const_iterator end()const
16. {
17.         return const_iterator(_head);
18. }

复制代码

list的插入/删除

list最常见的插入删除就是在头部和尾部的插入删除，此中插入的步调是：
1.创建新节点
2.获取目的位置的节点及其前驱节点
3.让新节点的头指向目的位置节点的头节点，让新节点的尾节点指向目的位置节点
4.让前驱节点的尾指向新节点，目的位置节点的头指向新节点
值得留意的是：list的插入/删除伴随着迭代器失效的问题，即：插入新节点后无法访问插入位置的数据
那么办理方法是什么呢？很简单，就是返回插入位置的数据，因此list的插入和删除都要传迭代器接收目的位置的数据，代码如下：

1. iterator insert(iterator pos, const T& x)
2. {
3.         Node* newnode = new Node(x);
4.         Node* cur = pos._node;
5.         Node* prev = cur->_prev;
7.         newnode->_next = cur;
8.         newnode->_prev = prev;
9.         prev->_next = newnode;
10.         cur->_prev = newnode;
11.         return iterator(newnode);
12. }
13. iterator erase(iterator pos)
14. {
15.         Node* cur = pos._node;
16.         Node* prev = cur->_prev;
17.         Node* next = cur->_next;
19.         prev->_next = next;
20.         next->_prev = prev;
21.         delete cur;
22.         return iterator(next);
23. }

复制代码

有了插入删除的接口，那么我们就可以很轻松实现list的头部插入删除，尾部插入删除，其代码如下：

1. void pop_back()
2. {
3.         erase(--end());
4. }
5. void pop_front()
6. {
7.         erase(begin());
8. }
10. void push_back(const T& x)
11. {
12.         insert(begin(), x);
13. }
14. void push_front(const T& x)
15. {
16.         insert(end, x);
17. }

复制代码

构造/析构函数

list的C++标准库中提供了很多的构造方式，我们在这里只着重先容此中的无参构造，initializer_list构造以及拷贝构造，在实现构造函数之前，我们应该先写一个初始化函数，这个初始化函数是将头节点的next和prev都指向本身从而实现初始化，我们在写构造函数时，重要用这个初始化函数来构造，其代码如下：

1. void empty_init()
2. {
3.         _head = new Node();
4.         _head->_next = _head;
5.         _head->_prev = _head;
6. }
7. list()
8. {
9.         empty_init();
10. }
11. list(const list<T>& il)
12. {
13.         empty_init();
14.         for (const auto& e : il)
15.         {
16.                 push_back(e);
17.         }
18. }
19. list(initializer_list<T> il)
20. {
21.         empty_init();
22.         for (const auto& e : il)
23.         {
24.                 push_back(il);
25.         }
26. }

复制代码

析构函数与构造函数雷同，提供了一个clear接口，通过调用clear接口逐个删除list的节点，最后再将头节点释放，如许就实现了一个简单的析构函数，其代码如下所示：

1. void clear()
2. {
3.         auto it = begin();
4.         while (it != end())
5.         {
6.                 it = erase(it);
7.         }
8. }
9. ~list()
10. {
11.         clear();
12.         delete _head;
13.         _head = nullptr;
14. }

复制代码

重载=

list的重载=是通过传值传参然后调用swap来实现的，其代码如下所示：

1. list<T>& operator=(const list<T> lt)
2. {
3.         swap(_head, lt._head);
4.         return *this;
5. }

复制代码

分析上述代码，我们可以看到，不同于传统的重载operator=我们这里采用了传值传参，然后交换头节点，如许做的好处显而易见，传值传参调用拷贝构造产生一个临时对象，临时对象具有常量属性因此要加const修饰，在出作用域之后就析构烧毁。
list模拟实现代码如下

1. template<class T> struct ListNode{        ListNode<T>* _next;        ListNode<T>* _prev;        T _data;        ListNode(const T& data = T()) :_next(nullptr), _prev(nullptr), _data(data)        {}};template<class T,class Ref,class Ptr>
2. struct ListIterator
3. {
4.         typedef ListNode<T> Node;
5.         typedef ListIterator<T,T&,T*> Self;
6.         Node* _node;
8.         ListIterator(Node*node):_node(node)
9.         {}
11.         Self& operator++()
12.         {
13.                 _node = _node->_next;
14.                 return *this;
15.         }
16.         Self& operator--()
17.         {
18.                 _node = _node->_prev;
19.                 return *this;
20.         }
22.         Self operator++(int)
23.         {
24.                 Self tmp(_node);
25.                 _node = _node->_next;
26.                 return tmp;
27.         }
28.         Self operator--(int)
29.         {
30.                 Self tmp(_node);
31.                 _node = _node->_prev;
32.                 return tmp;
33.         }
35.         Ref operator*()
36.         {
37.                 return _node->_data;
38.         }
40.         Ptr operator->()
41.         {
42.                 return &_node->_data;
43.         }
45.         bool operator==(const Self&it)
46.         {
47.                 return _node == it._node;
48.         }
49.         bool operator!=(const Self& it)
50.         {
51.                 return _node != it._node;
52.         }
53. };template<class T>class list{        typedef ListNode<T> Node;public:        typedef ListIterator<T, T&, T*> iterator;        iterator begin()        {                return iterator(_head->_next);        }        iterator end()        {                return iterator(_head);        }        typedef ListIterator<T, const T&,const T*> const_iterator;        const_iterator begin()const        {                return const_iterator(_head->_next);        }        const_iterator end()const        {                return const_iterator(_head);        }        void empty_init()        {                _head = new Node();                _head->_next = _head;                _head->_prev = _head;        }        list()        {                empty_init();        }        list(const list<T>& il)        {                empty_init();                for (const auto& e : il)                {                        push_back(e);                }        }        list(initializer_list<T> il)        {                empty_init();                for (const auto& e : il)                {                        push_back(il);                }        }        list<T>& operator=(const list<T> lt)        {                swap(_head, lt._head);                return *this;        }        void clear()        {                auto it = begin();                while (it != end())                {                        it = erase(it);                }        }        ~list()        {                clear();                delete _head;                _head = nullptr;        }        iterator insert(iterator pos, const T& x)        {                Node* newnode = new Node(x);                Node* cur = pos._node;                Node* prev = cur->_prev;                newnode->_next = cur;                newnode->_prev = prev;                prev->_next = newnode;                cur->_prev = newnode;                return iterator(newnode);        }        iterator erase(iterator pos)        {                Node* cur = pos._node;                Node* prev = cur->_prev;                Node* next = cur->_next;                prev->_next = next;                next->_prev = prev;                delete cur;                return iterator(next);        }        void pop_back()        {                erase(--end());        }        void pop_front()        {                erase(begin());        }        void push_back(const T& x)        {                insert(begin(), x);        }        void push_front(const T& x)        {                insert(end, x);        }private:        Node* _head;};

复制代码

小结

本篇博客先容了list的使用和模拟实现，通过对list的模拟实现，我们先容了迭代器失效的问题以及迭代器的封装。
感谢您在百忙之中可以或许看完本篇文章，假如本篇文章对您有所帮助的话，希望您能留下点赞评论加关注，您的支持就是我创作的最大动力。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。