C++：模仿实现list

目次

节点
迭代器
团体框架
构造函数
empty_init
拷贝构造
赋值重载
析构函数
clear
insert
erase
push_back和push_front
pop_back和push_front
size
empty
Print_Container

---

节点

对于链表节点，我们须要一个数据、一个前驱指针、一个后继指针来维护，而且将其封装成一个类。

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

复制代码

使用struct的缘故原由是因为，struct默认的域作用限定符是public，方便后续使用，不消走友元的那一套。
迭代器

我们知道迭代器提供访问容器的方法，之前实现vector和string时，迭代器用的就是数据类型的指针，但是list不可以直接用。因为vector和string的数据在内存的存放都是连续的，如果想找下一个数据的指针（迭代器），直接（迭代器）指针++就可以了；但是list的数据存放在内存不是连续的，如果直接把指针当成迭代器，迭代器++是找不到下一个数据的迭代器。
以是综上所述，我们应该用类对链表数据类型的指针封装成迭代器，在类里重载利用符让其达到我们想要的效果。
当然，我们实现的迭代器应该有两个版本，普通版本和const版本。

1. //普通迭代器
2. template<class T>
3. struct list_iterator
4. {
5.         typedef list_node<T> Node;
6.         typedef list_iterator<T> Self;
7.         Node* _node;
9.         list_iterator(Node* node)
10.                 :_node(node)
11.         {}
13.         T& operator*()
14.         {
15.                 return _node->_data;
16.         }
18.         T* operator->()
19.         {
20.                 return &_node->_data;
21.         }
23.         //前置++
24.         Self& operator++()
25.         {
26.                 _node = _node->_next;
27.                 return *this;
28.         }
30.         //后置++
31.         Self operator++(int)
32.         {
33.                 Self tmp(*this);
34.                 _node = _node->_next;
35.                 return tmp;
36.         }
38.         //前置--
39.         Self& operator--()
40.         {
41.                 _node = _node->_prev;
42.                 return *this;
43.         }
45.         //后置--
46.         Self operator--(int)
47.         {
48.                 Self tmp(*this);
49.                 _node = _node->_prev;
50.                 return tmp;
51.         }
53.         bool operator!=(const Self& it) const
54.         {
55.                 return _node != it._node;
56.         }
58.         bool operator==(const Self& it) const
59.         {
60.                 return _node == it._node;
61.         }
62. };

复制代码

1. ​//const迭代器
2. template<class T>
3. struct list_const_iterator
4. {
5.         typedef list_node<T> Node;
6.         typedef list_const_iterator<T> Self;
7.         Node* _node;
9.         list_const_iterator(Node* node)
10.                 :_node(node)
11.         {}
13.         const T& operator*()
14.         {
15.                 return _node->_data;
16.         }
18.         const T* operator->()
19.         {
20.                 return &_node->_data;
21.         }
23.         Self& operator++()
24.         {
25.                 _node = _node->_next;
26.                 return *this;
27.         }
29.         Self operator++(int)
30.         {
31.                 Self tmp(*this);
32.                 _node = _node->_next;
33.                 return tmp;
34.         }
36.         Self& operator--()
37.         {
38.                 _node = _node->_prev;
39.                 return *this;
40.         }
42.         bool operator!=(const Self& it) const
43.         {
44.                 return _node != it._node;
45.         }
47.         bool operator==(const Self& it) const
48.         {
49.                 return _node == it._node;
50.         }
51. };
53. ​

复制代码

我们发现这两份代码，除了重载*和->有所不同，其余代码都是一样的，以是我们可以增加两个模板参数，将这两份代码合二为一。

1. template<class T, class Ref, class Ptr>
2. struct list_iterator
3. {
4.         typedef list_node<T> Node;
5.         typedef list_iterator<T, Ref, Ptr> Self;
6.         Node* _node;
8.         list_iterator(Node* node)
9.                 :_node(node)
10.         {}
12.         Ref operator*()
13.         {
14.                 return _node->_data;
15.         }
17.         Ptr operator->()
18.         {
19.                 return &_node->_data;
20.         }
22.         Self& operator++() //前置++
23.         {
24.                 _node = _node->_next;
25.                 return *this;
26.         }
28.         Self operator++(int) //
29.         {
30.                 Self tmp(*this);
31.                 _node = _node->_next;
32.                 return tmp;
33.         }
35.         Self& operator--()
36.         {
37.                 _node = _node->_prev;
38.                 return *this;
39.         }
41.         Self operator--(int)
42.         {
43.                 Self tmp(*this);
44.                 _node = _node->_prev;
45.                 return tmp;
46.         }
48.         bool operator!=(const Self& it) const
49.         {
50.                 return _node != it._node;
51.         }
53.         bool operator==(const Self& it) const
54.         {
55.                 return _node == it._node;
56.         }
57. };

复制代码

 增加Ref和Ptr模板参数，让T*和T&作为参数传入，这就可以办理将两份代码合二为一。
团体框架

1. ​
2. ​
3. template<class T>
4. class list
5. {
6.         typedef list_node<T> Node;
7. public:
8.         /*typedef list_iterator<T> iterator;
9.         typedef list_const_iterator<T> const_iterator;*/
11.         //将T&和T*作为参数传入
12.     typedef list_iterator<T, T&, T*> iterator;
13.         typedef list_iterator<T, const T&, const T*> const_iterator;
15.     iterator begin()
16.     {
17.             /*iterator it(_head->_next);
18.             return it;*/
20.             //return iterator(_head->_next);
22.             //返回哨兵节点的下一个节点（第一个有效节点）
23.             //隐式类型转换
24.             return _head->_next;
25.     }
27.     iterator end()
28.     {
29.             //最后一个有效节点的下一位置，也就是哨兵节点
30.             return _head;
31.     }
33.     const_iterator begin() const
34.     {
35.             return _head->_next;
36.     }
38.     const_iterator end() const
39.     {
40.             return _head;
41.     }
43.     //实现各种函数......
45. private:
46.         Node* _head;
47.         size_t _size;
48. };
50. ​
52. ​

复制代码

构造函数

empty_init

多种构造函数的代码都有重合，以是把重合部分独立成一个函数。

1. ​
2. void empty_init()
3. {
4.         //创造哨兵节点
5.     _head = new Node();
6.         _head->_next = _head;
7.         _head->_prev = _head;
8.         _size = 0;
9. }
11. ​

复制代码

普通构造
普通构造就是创造哨兵节点，调用empty_init即可。

1. //普通构造
2. list()
3. {
4.         empty_init();
5. }

复制代码

列表构造
C++11的用法，用法例子如下：

1. list<int> lt1 = { 1,2,3,4,5,6 };

复制代码

 先创造一个哨兵节点，然后将列表的元素尾插即可。

1. //列表构造
2. list(initializer_list<T> il)
3. {
4.         empty_init();
5.         for (auto& e : il)
6.         {
7.                 push_back(e);
8.         }
9. }

复制代码

关于列表initializer_list<T>的知识，可以看以下连接。
   介绍列表
  拷贝构造

创建哨兵节点，将链表元素尾插到待构造的链表就完成拷贝构造了。

1. //拷贝构造
2. list(const list<T>& lt)
3. {
4.         empty_init();
6.         for (auto& e : lt)
7.         {
8.                 push_back(e);
9.         }
10. }

复制代码

赋值重载

与暂时对象lt互换即可，跟string、vector的实现雷同。

1. void swap(list<T>& lt)
2. {
3.         std::swap(_head, lt._head);
4.         std::swap(_size, lt._size);
5. }
7. list<T>& operator=(list<T> lt)
8. {
9.         swap(lt);
10.         return *this;
11. }

复制代码

析构函数

clear

清理除了哨兵节点以外的所有节点。

1. void clear()
2. {
3.         auto it = begin();
4.         while (it != end())
5.         {
6.                 it = erase(it);
7.         }
8. }

复制代码

先将链表clear掉，然后清理哨兵节点。  

1. ~list()
2. {
3.         clear();
4.         delete _head;
5.         _head = nullptr;
6. }

复制代码

insert

在pos（迭代器）位置前插入元素x，插入后_size++，返回新插入元素的迭代器。

1. iterator insert(iterator pos, const T& x)
2. {
3.         Node* cur = pos._node; //pos是iterator类的对象，访问里面的成员变量用pos._node，不能用pos->_node
4.         Node* prev = cur->_prev;
6.         Node* newnode = new Node(x);
8.         newnode->_next = cur;
9.         cur->_prev = newnode;
10.         newnode->_prev = prev;
11.         prev->_next = newnode;
13.         ++_size;
15.         //隐式类型转换
16.         return newnode;
17. }

复制代码

erase

删除pos位置的元素，删除后_size--，返回删除元素的下一元素的迭代器。

1. iterator erase(iterator pos)
2. {
3.         assert(pos != end());          //不能删掉哨兵位的节点
5.         Node* prev = pos._node->_prev;
6.         Node* next = pos._node->_next;
8.         prev->_next = next;
9.         next->_prev = prev;
11.         delete pos._node;
12.         --_size;
14.         return next;
15. }

复制代码

push_back和push_front

利用insert函数就可以实现尾插和头插。

1. void push_back(const T& x)
2. {
3.         /*Node* newnode = new Node(x);
4.         Node* tail = _head->_prev;
6.         tail->_next = newnode;
7.         newnode->_prev = tail;
9.         newnode->_next = _head;
10.         _head->_prev = newnode;
12.         ++_size;*/
13.         insert(end(), x);
14. }
16. void push_front(const T& x)
17. {
18.         insert(begin(), x);
19. }

复制代码

pop_back和push_front

利用erase函数实现尾删和头删。

1. void pop_back()
2. {
3.         erase(--end());
4. }
6. void pop_front()
7. {
8.         erase(begin());
9. }

复制代码

size

返回链表有效元素的个数.。

1. size_t size() const
2. {
3.         return _size;
4. }

复制代码

empty

判定链表是否为空。

1. bool empty() const
2. {
3.         return _size == 0;
4. }

复制代码

Print_Container

打印容器的函数。

1. template<class Container>
2. void Print_Container(const Container& con)
3. {
4.         //const对象要用const迭代器，这里没实现的话会报错
5.         /*auto it = con.begin();
6.         while (it != con.end())
7.         {
8.                 cout << *it << " ";
9.                 ++it;
10.         }*/
12.         for (auto e : con)
13.         {
14.                 cout << e << " ";
15.         }
16.         cout << endl;
17. }

复制代码

---

拜拜，下期再见