list模仿实现

目录

前言
具体实现
节点
迭代器
list迭代器的基本内容
成员变量和typedef
构造函数
对 ++ 和 -- 运算符的重写
对 运算符* 和 运算符->的重写
对运算符== 和 运算符！=的重写
迭代器完整代码
List的具体实现
基本成员和typedef
构造函数
front 和 back
insert和erase
push_back和push_front
pop_back和push_back
empty和size
begin和end
clear和swap
析构函数
总结

---

前言

list底层是一个带头双向循环链表。list的重点是对其节点的封装(即迭代器的封装)。盼望可以通过对list的模仿实现使各位更明白封装的意义。
具体实现

节点

节点内容很常规，一个_val存储数据，一个prev指针指向节点的前一个数据，一个next指针指向节点的后一个数据。(画图较丑，大致就是这样的图)

节点代码

1.         template<class T>
2.         struct ListNode
3.         {
4.                 T _val = T();
5.                 ListNode<T>* prev = nullptr;
6.                 ListNode<T>* next = nullptr;
8.                 ListNode(const T& x)
9.                         : _val(x)
10.                         , prev(nullptr)
11.                         , next(nullptr)
12.                 {}
13.         };

复制代码

迭代器

list迭代器的基本内容

list的迭代器实质上是对 节点 即 Node 的封装，使得迭代器能实现 ++ 和 -- 等一系列迭代器所需的基本运算操作(由于list的存储空间不连续，所以Node无法直接举行迭代器所需的基本运算，因此对其举行封装)。 值得一提的是list的迭代器不是随机迭代器，不支持 + 和 - ，其主要原因是由于 + 和 - 的操作太过斲丧性能了。
成员变量和typedef

由于是对 节点Node的封装，因此成员变量只有 _node。

1.                 typedef ListIterator<T, Ref, Ptr> Self;
2.                 typedef ListNode<T> Node;
3.         public:
4.                 Node* _node = nullptr;

复制代码

构造函数

1.                 ListIterator() = default;
2.                 ListIterator(Node* x)
3.                 {
4.                         _node = x;
5.                 }

复制代码

对 ++ 和 -- 运算符的重写

Self operator++(int) 是对后置++的重写， Self& operator++() 是对前置++的重写。

1. Self& operator++()
2. {
3.         _node = _node->next;
4.         return *this;
5. }
6. Self operator++(int)
7. {
8.         Self ret(_node);
9.         _node = _node->next;
10.         return ret;
11. }
12. Self& operator--()
13. {
14.         _node = _node->prev;
15.         return *this;
16. }
17. Self operator--(int)
18. {
19.         Self ret(_node);
20.         _node = _node->prev;
21.         return ret;
22. }

复制代码

对 运算符* 和 运算符->的重写

1. Ref operator*()
2. {
3.         return _node->_val;
4. }
5. Ptr operator->()
6. {
7.         return &*this->_node;
8. }

复制代码

对运算符== 和 运算符！=的重写

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

复制代码

迭代器完整代码

1.         template<class T , class Ref , class Ptr>        struct ListIterator        {                typedef ListIterator<T, Ref, Ptr> Self;
2.                 typedef ListNode<T> Node;
3.         public:
4.                 Node* _node = nullptr;        public:                ListIterator() = default;
5.                 ListIterator(Node* x)
6.                 {
7.                         _node = x;
8.                 }                Self& operator++()                {                        _node = _node->next;                        return *this;                }                Self operator++(int)                {                        Self ret(_node);                        _node = _node->next;                        return ret;                }                Self& operator--()                {                        _node = _node->prev;                        return *this;                }                Self operator--(int)                {                        Self ret(_node);                        _node = _node->prev;                        return ret;                }                Ref operator*()                {                        return _node->_val;                }                Ptr operator->()                {                        return &*this->_node;                }                bool operator==(const Self& x)
9.                 {
10.                         return _node == x._node;
11.                 }
12.                 bool operator!=(const Self& x)
13.                 {
14.                         return _node != x._node;
15.                 }        };

复制代码

List的具体实现

基本成员和typedef

1.                 typedef ListNode<T> Node;
2.         public:
3.                 typedef ListIterator<T, T&, T*> iterator;
4.                 typedef ListIterator<T, const T&, const T*> const_iterator;
5.         private:
6.                 Node* _head = nullptr;

复制代码

构造函数

1. list()
2. {
3.         _head = new Node(T());
4.         _head->next = _head->prev = _head;
5. }
7. list(int n , const T& x = T())
8. {
9.         _head = new Node(T());
10.         _head->next = _head->prev = _head;
11.         while (n--) push_back(x);
12. }
14. template<class InputIterator>
15. list(InputIterator l, InputIterator r)
16. {
17.         _head = new Node(T());
18.         _head->next = _head->prev = _head;
19.         while (l != r)
20.         {
21.                 push_back(*l);
22.                 l++;
23.         }
24. }
26. list(initializer_list<T> il)
27. {
28.         _head = new Node(T());
29.         _head->next = _head->prev = _head;
30.         for (const auto& x : il)
31.         {
32.                 push_back(x);
33.         }
34. }

复制代码

front 和 back

1. T& front()
2. {
3.         return _head->next->_val;
4. }
5. T& back()
6. {
7.         return _head->prev->_val;
8. }

复制代码

insert和erase

erase返回删除节点的后一个节点，避免迭代器失效题目。 insert此处也返回迭代器是为了工整，实际上list的insert不会导致迭代器失效

1. iterator insert(iterator pos, const T& x)
2. {
3.         Node* dest = new Node(x);
4.         dest->prev = pos._node->prev;
5.         dest->next = pos._node;
6.         pos._node->prev->next = dest;
7.         pos._node->prev = dest;
8.         return dest;
9. }
10. iterator erase(iterator pos)
11. {
12.         Node* dest = pos._node->next;
13.         dest->prev = pos._node->prev;
14.         pos._node->prev->next = dest;
15.         delete pos._node;
16.         return dest;
17. }

复制代码

push_back和push_front

除下面写法外，也可以思量对insert举行复用

1.                 void push_back(const T& x)
2.                 {
3.                         Node* dest = new Node(x);
4.                         dest->prev = _head->prev;
5.                         dest->next = _head;
6.                         _head->prev->next = dest;
7.                         _head->prev = dest;
8.                 }
9.                 void push_front(const T& x)
10.                 {
11.                         Node* dest = new Node(x);
12.                         dest->prev = _head;
13.                         dest->next = _head->next;
14.                         _head->next->prev = dest;
15.                         _head->next = dest;
16.                 }

复制代码

pop_back和push_back

除下面写法外，也可以思量对erase的复用

1.                 void pop_front()
2.                 {
3.                         if (!empty())
4.                         {
5.                                 Node* dest = _head->next;
6.                                 dest->next->prev = _head;
7.                                 _head->next = dest->next;
8.                                 delete dest;
9.                         }
10.                 }
11.                 void pop_back()
12.                 {
13.                         if (!empty())
14.                         {
15.                                 Node* dest = _head->prev;
16.                                 _head->prev = dest->prev;
17.                                 dest->prev->next = _head;
18.                                 delete dest;
19.                         }
20.                 }

复制代码

empty和size

1.                 bool empty()
2.                 {
3.                         return _head->next == _head->prev;
4.                 }
5.                 size_t size() const
6.                 {
7.                         size_t n = 0;
8.                         iterator b = _head->next;
9.                         iterator e = _head;
10.                         while (b != e)
11.                         {
12.                                 n++;
13.                                 ++b;
14.                         }
15.                         return n;
16.                 }

复制代码

begin和end

1.                 const_iterator begin() const
2.                 {
3.                         return const_iterator(_head->next);
4.                 }
5.                 const_iterator end() const
6.                 {
7.                         return const_iterator(_head);
8.                 }
9.                 iterator begin()
10.                 {
11.                         return _head->next;
12.                 }
13.                 iterator end()
14.                 {
15.                         return _head;
16.                 }

复制代码

clear和swap

1. void clear()
2. {
3.         iterator b = _head->next;
4.         iterator e = _head;
5.         while (b != e)
6.         {
7.                 b = erase(b);
8.         }
9. }
11. void swap(list<T>& l)
12. {
13.         Node* m = l._head;
14.         l._head = _head;
15.         _head = m;
16. }

复制代码

析构函数

2.                 ~list()
3.                 {
4.                         iterator b = _head->next, e = _head;
5.                         while (b != e)
6.                         {
7.                                 b = erase(b);
8.                         }
9.                         delete _head;
10.                 }

复制代码

总结

难点在于对迭代器的封装，同时不要忽略list类中erase迭代器通过返回值来防止因删除节点而导致的迭代器失效题目


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