C++list常用接口和模拟实现

C++中list容器底层实现是使用带头双向循环链表的结构，通过指针指向前一个和后一个节点。它也具有双向链表的优缺点，比如优点是对于在任意位置插入和删除不用移动数据，缺点是不能任意位置的随机访问，必须遍历到要访问的节点才可以；而且list还需要额外的空间来存储前一个和后一个节点的信息。
下面了解一下list的常用接口
1.构造函数

1. //构造空的list
2. list()
4. //拷贝构造
5. list (const list& x);
7. //迭代器构造，使用模板能适合不同的类型
8. template <class InputIterator>
9. list (InputIterator first, InputIterator last);
11. //构造n个值为val的list
12. list (size_type n, const value_type& val = value_type())

复制代码

2.迭代器

1. //返回开始位置的迭代器
2. iterator begin();
3. const_iterator begin() const;
5. //返回结束位置的迭代器
6. iterator end();
7. const_iterator end() const;

复制代码

需要留意的是这里的迭代器在底层并不是原生指针，详细实现在后文给出。
3.容量操纵

1. //判断是否为空
2. bool empty() const;
4. //返回有效节点的个数
5. size_type size() const;

复制代码

4.元素获取

1. //返回首元素的引用
2. reference front();
3. const_reference front() const;
5. //返回末尾元素的引用
6. reference back();
7. const_reference back() const;

复制代码

5.增删改查

1. //头插
2. void push_front (const value_type& val);
4. //尾插
5. void push_back (const value_type& val);
7. //头删
8. void pop_front();
10. //尾删
11. void pop_back();
13. //在任意位置插入
14. iterator insert (iterator position, const value_type& val);
16. //在任意位置删除
17. iterator erase (iterator position);
19. //交换两个链表中的元素
20. void swap (list& x);
22. //清空链表中的元素
23. void clear();

复制代码

在了解了链表的增删查改之后我们思索一个问题
list是否会像vector和string一样出现迭代器失效的缘故原由？由于这里是链式结构，它的内存在物理空间上并不一连，因此如果仅仅是插入一个元素并不会出现迭代器失效的问题，只有删除时会发生迭代器失效的问题，而且这里只有删除节点的迭代器会失效。
下面给出list的模拟实现
1.节点list_node设计
节点的结构就是双向链表的结构，这里也可以写成结构直接默认类成员公有的也可以。

1.         template<class T>
2.         class list_node
3.         {
4.         public:
5.                 list_node<T>* _next;
6.                 list_node<T>* _prev;
7.                 T _val;
9.                 list_node(const T& val = T())//默认匿名对象
10.                         :_next(nullptr)
11.                         ,_prev(nullptr)
12.                         ,_val(val)
13.                 {}
14.         };

复制代码

2.迭代器设计
关于const的迭代器设计与之前的string和vector都有所差别，对于节点的指针举行了又一层的封装。由于这里要支持->箭头和的重载。我们对于一个指针变量举行解引用通常是要访问其中存储的数据的内容（_val）；而->是要访问数据内容的成员。从这个特性就可以得到一个结论，在实现list迭代器时，重载解引用和箭头的返回类型差别，那么我们要怎样控制呢？
事实上在这里只需要控制模板参数就可以实现这种效果。详细代码如下

1.         template<class T,class Ref ,class Ptr>
2.         class _list_iterator
3.         {
4.         public:
5.         //这里事实上迭代器只是借用节点进行访问，而不是管理这些节点，链表才管理节点   
6.                 typedef list_node<T> Node;
7.                 typedef _list_iterator<T, Ref,Ptr> self;
9.                 Node* _node;
11.                 _list_iterator(Node* node)
12.                         :_node(node)
13.                 {}
15.                 Ref operator*()//这里控制解引用的返回类型
16.                 {
17.                         return _node->_val;
18.                 }
20.                 Ptr operator->()
21.                 {
22.                         return &_node->_val;
23.                 }
25.                 //前置++
26.                 self& operator++()
27.                 {
28.                         _node = _node->_next;
29.                         return *this;
30.                 }
32.                 //后置++
33.                 self operator++(int)
34.                 {
35.                         self temp(*this);
36.                         _node = _node->_next;
37.                         return temp;
38.                 }
40.                 //前置--
41.                 self& operator--()
42.                 {
43.                         _node = _node->_prev;
44.                         return *this;
45.                 }
47.                 //后置--
48.                 self operator--(int)
49.                 {
50.                         self temp(*this);
51.                         _node = _node->_prev;
52.                         return temp;
53.                 }
55.                 bool operator!=(const self& it) const
56.                 {
57.                         return _node != it._node;
58.                 }
60.                 bool operator==(const self& it) const
61.                 {
62.                         return _node == it._node;
63.                 }
64.         };

复制代码

这里的Ref控制解引用的返回类型，Ptr控制箭头的返回类型；而且在这个类中使用typedef的方法控制自增和自减的返回类型。
而且这样写还有一点好处是，对于普通的迭代器使用正常的模板参数即可，对于const迭代器使用const的模板参数即可。
3.常用接口的模拟实现

1.         template<class T>
2.         class list
3.         {
4.                 typedef list_node<T> Node;
5.         public:
6.                 typedef _list_iterator<T,T&,T*> iterator;//内嵌类
7.                 typedef _list_iterator<T,const T&,const T*> const_iterator;
9.                 //这里const迭代器的设计是错误的，因为const迭代器是希望指向内容不被修改
10.                 //这样的设计是迭代器本身不能修改
11.                 //typedef const _list_iterator<T> const_iterator;
13.                 iterator begin()
14.                 {
15.                         return _head->_next;//单参数的构造函数支持隐式类型转换
16.                 }
18.                 const_iterator begin() const
19.                 {
20.                         return _head->_next;
21.                 }
23.                 iterator end()
24.                 {
25.                         return _head;
26.                 }
28.                 const_iterator end() const
29.                 {
30.                         return _head;
31.                 }
33.                 void empty_init()
34.                 {
35.                         _head = new Node;
36.                         _head->_prev = _head;
37.                         _head->_next = _head;
38.                 }
40.                 list()
41.                 {
42.                         empty_init();
43.                 }
45.                 //lt2(lt1)
46.                 list(const list<T>& lt)
47.                 //list(const list& lt)//不推荐这样使用
48.                 {
49.                         empty_init();
51.                         //遍历lt1，直接把lt2尾插到lt1
52.                         //这里传引用效率高
53.                         for (const auto& e : lt)
54.                         {
55.                                 push_back(e);
56.                         }
57.                 }
59.                 void swap(list<T>& lt)
60.                 {
61.                         std::swap(_head, lt._head);
62.                 }
64.                 list<T>& operator=(list<T> lt)
65.                 //list& operator=(list lt)//这里与上面的拷贝构造同理
66.                 {
67.                         swap(lt);
68.                         return *this;
69.                 }
71.                 ~list()
72.                 {
73.                         clear();
75.                         delete _head;
76.                         _head = nullptr;
77.                 }
79.                 void clear()
80.                 {
81.                         iterator it = begin();
82.                         while (it != end())
83.                         {
84.                                 it = erase(it);
85.                         }
86.                 }
88.                 void push_back(const T& x)
89.                 {
90.                         insert(end(), x);
91.                 }
93.                 void pop_back()
94.                 {
95.                         erase(--end());//这里调用--，头节点的prev就是尾
96.                 }
98.                 void push_front(const T& x)
99.                 {
100.                         insert(begin(), x);
101.                 }
103.                 void pop_front()
104.                 {
105.                         erase(begin());
106.                 }
108.                 iterator insert(iterator pos, const T& x)
109.                 {
110.                         Node* cur = pos._node;
111.                         Node* prev = cur->_prev;
112.                         Node* newnode = new Node(x);
114.                         prev->_next = newnode;
115.                         newnode->_next = cur;
117.                         cur->_prev = newnode;
118.                         newnode->_prev = prev;
120.                         return newnode;
121.                 }
123.                 iterator erase(iterator pos)//这里会有迭代器失效，返回下一个位置的迭代器
124.                 {
125.                         assert(pos != end());
127.                         Node* cur = pos._node;
128.                         Node* prev = cur->_prev;
129.                         Node* next = cur->_next;
131.                         prev->_next = next;
132.                         next->_prev = prev;
133.                         delete cur;
135.                         return next;
136.                 }
138.                 size_t size()
139.                 {
140.                         size_t sz = 0;
141.                         iterator it = begin();
142.                         while (it != end())
143.                         {
144.                                 ++sz;
145.                                 ++it;
146.                         }
147.                         return sz;
148.                 }
149.                
150.         private:
151.                 Node* _head;
152.         };

复制代码

这里的常用接口实现都雷同与数据结构中的带头的双向链表。需要留意的就是爹迭代器失效的问题。
最后总结一下vector和list的各自优劣
（1）底层结构：vector是一连存储的，是一个动态的次序表；list是不一连存储，是一个带头的双向循环链表
（2）随机访问：vector支持[]随机访问；list不支持随机访问
（3）插入和删除效率：vector的插入和删除需要移动数据；list的插入和删除不需要移动数据。
（4）空间使用率：vector底层是一连的存储空间，不轻易造成内存碎片的问题，空间使用率高；list底层是不一连的存储空间，小的节点轻易出现内存碎片的问题，空间使用率低。
（5）迭代器：vector的迭代器是原生指针；list的迭代器对原生指针举行了再一层的封装。
（6）迭代器失效的问题：vector再插入和删除时都会导致迭代器失效，需要重新赋值；list只有再删除时才会导致迭代器失效。

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