【C++】list的模拟实现

目录

前言：list的简单介绍

一、Member variables

二、iterator

1、__list_iterator

2、begin()、end()

3、const_begin()、const_end()

4、operator!=、==

5、operator++

6、operator--

7、operator*

8、operator->

三、Modifiers

1、push_back

2、push_front

3、insert

4、pop_back

5、pop_front

6、erase

7、swap

8、clear

四、constructor

1、无参构造

2、迭代器区间构造

3、拷贝构造

五、destructor

六、operator=

总结

---

前言：list的简单介绍

list是C++STL中十分重要的容器，这个容器不可以使用[ ]来对链表进行操作

list的优点是按需索取，不会占用过多的空间，同时它的头部和尾部的插入删除时间复杂度是O(1)

因为它是带头双向循环链表，找头和尾的时间复杂度都是O(1)

同时还有会造成内存碎片的问题，因为它的节点是通过new出来的，频繁的new和delete必然会导致内存碎片。

list的遍历只能通过迭代器，因此它的迭代器是我们要重点实现的部分

 

---

一、Member variables

链表的成员变量很明显就是，链表的节点，而链表的节点是一个聚合类型，所以很明显链表节点是一个类，一个带头双向循环链表的成员一定有它当前节点的值，指向下一个节点的指针，和指向上一个节点的指针。同时还要有它的构造函数，构造函数就比较简单了，类似于数据结构带头双向循环链表的BuyNode函数，开一个空间，将当前节点的next和prev指针都指向空，然后在插入时链接到链表中就可以了，经过前面的叙述，我们可以得知这个类应该使用struct来定义是最好的，因为我们要访问节点的成员变量。

//带头双向循环链表
    //链表节点
    template<class T>
    struct list_node
    {
        list_node(const T& value = T())
            :_value(value)
            ,_next(nullptr)
            ,_prev(nullptr)
        {}
 
        T _value;
        list_node* _next;
        list_node* _prev;
    };

二、iterator

链表的迭代器与我们的vector和string有很大的不同，因为vector和string的空间是连续的，而list的空间是不连续的，它是一个一个的节点组成的

迭代器的定义是使用起来像指针，vector和string空间连续，所以直接是原生指针

而list空间不连续.。

C++相比于C语言的优势在于函数重载和封装，所以我们可以将指针封装成一个迭代器，分别实现++ -- * 等操作符重载就可以实现迭代器

1、__list_iterator

这个类就是迭代器，既然是迭代器，它会看起来像是一个指针，而这个"指针"是指向链表结点的，所以要想完成上面的操作，必然会需要我们向__list_iterator传一个节点

所以__list_iterator的成员函数就是节点list_node

template<class T>
    struct __list_iterator
    {
        typedef list_node Node;
        typedef __list_iterator iterator;
 
        __list_iterator(Node* node)
            :_node(node)
        {}
 
     
 
        Node* _node;
    };

这就是__list_iterator的简单框架

2、begin()、end()

要实现这两个成员函数，首先要想清楚begin()和end()到底指向哪个位置？

在STL的规范中begin是指向第一个元素的，end是指向尾元素的下一个位置的

因为我们的list是带头的，而头是不存储有效数据的，所以begin不能指向头，所以begin指向的应该是_head->next，而尾的下一个元素就是_head，因为是双向循环链表

        iterator begin()
        {
            return iterator(_head->_next);
        }
 
        iterator end()
        {
            return iterator(_head);
        }

这里特别说明一点，begin和end是list这个类的成员函数，并不是__list_iterator类里面的成员函数

下面的const_begin和const_end同理

因为都是迭代器的功能所以放在了这里，这里的排列顺序是根据实现顺序来排列的

3、const_begin()、const_end()

到了const版本的时候这里就出现了问题，如果还是按照我们的vector和string的方式写const迭代器就会出现问题

因为const迭代器必然是为了const对象也能够调用，函数重载的规则可没有根据返回值不同来区分重载的函数，而如果我们在函数后面加上const

const_iterator begin()const
{
    return _head->next;
}

它也会出现编译错误，无法解引用const对象的成员变量，因为我们要返回的是head的next

这个操作一定会将list类的成员变量_head解引用来找到它的下一个节点，所以不能在函数后面加const，那么这到底要怎么写才能够使const对象也能够调用呢？

我们可以看一下STL的源码

template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef __list_iterator             iterator;
  typedef __list_iteratorconst T&, const T*> const_iterator;
  typedef __list_iterator           self;
 
  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
    //…………………………
};

我们发现它的迭代器一共有三个模板参数，分别是T, Ref, Ptr

const迭代器有三个参数T, const T&, const T*

STL源码是通过实例化出的对象类型不同来区分是普通对象还是const对象的

因为无论是const对象还是普通对象，调用begin()的操作基本类似，唯一不同的是返回值类型，const对象要返回的是const 类型，普通对象返回普通类型

因此我们使用模板参数显示的控制就可以了，模板参数分别是T(普通类型)，Ref(引用类型),Ptr(指针类型)

这三个参数还要在后面的操作符重载函数中有用，具体细节在下面

        const_iterator begin()const 
        {
            return const_iterator(_head->_next);
        }
 
        const_iterator end()const 
        {
            return const_iterator(_head);
        }

4、operator!=、==

在前面的内容铺垫下这两个操作符是很容易实现的，这就是判断两个迭代器想不想等，换句话来说就是判断这两个迭代器所指向的节点想不想同

        bool operator!=(const iterator& it)const 
        {
            return _node != it._node;
        }
 
        bool operator==(const iterator& it)const 
        {
            return _node == it._node;
        }

5、operator++

++分为前置++和后置++

所谓的++就是将迭代器移动到下一个节点，就是cur->next

        iterator& operator++()
        {
            _node = _node->_next;
            return *this;
        }
 
        iterator operator++(int)
        {
            //浅拷贝就够用了，返回的是tmp的拷贝
            iterator tmp(*this);
            _node = _node->_next;
            return tmp;
        }

细心的同学会发现我们的__list_iterator并没有实现=操作符重载，因为没有必要，浅拷贝就足够了

后置++返回的是我们没有++的值，我们直接传值返回临时对象就可以了，我们不可能会对++之前的值进行操作。

6、operator--

--与++同理，因为是双向链表，--就是将迭代器移动到cur->prev

        iterator& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
 
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

7、operator*

在实现这个成员函数时，我们应该仔细想一想，迭代器解引用得到的是list节点的值，而不是整个节点，所以只要返回节点值就可以了，对应的返回值类型应该是Ref

       Ref operator*()
        {
            return _node->_value;
        }

8、operator->

这个操作符也是，要想一想它的应用场景，它一般应用在结构体指针中，并且它的左操作数必须是指针类型，那么我们自然就很清楚，我们要返回的是指针类型Ptr

与*操作符重载的不同就在于返回的类型不同而已

       Ptr operator->()
        {
            return &(operator*());
        }

三、Modifiers

这几个函数都是十分的简单，在链表的博客中都已经写明了如何实现，在这里就不再赘述

1、push_back

        void push_back(const T& x)
        {
            Node* newNode = new Node(x);
            Node* tail = _head->_prev;
            
            tail->_next = newNode;
            newNode->_prev = tail;
            newNode->_next = _head;
            _head->_prev = newNode;
        }

2、push_front

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

3、insert

        iterator insert(iterator pos, const T& x)
        {
            Node* newNode = new Node(x);
 
            Node* cur = pos._node;
            Node* prev = cur->_prev;
 
            prev->_next = newNode;
            newNode->_prev = prev;
            newNode->_next = cur;
            cur->_prev = newNode;
 
            return iterator(newNode);
        }

4、pop_back

        void pop_back()
        {
            erase(--end());
        }

5、pop_front

       void pop_front()
        {
            erase(begin());
        }

6、erase

        //返回的是删除元素的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos != end());
 
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
 
            delete cur;
 
            prev->_next = next;
            next->_prev = prev;
 
            return iterator(next);
        }

7、swap

       void swap(list& lt)
        {
            std::swap(_head, lt._head);
        }

8、clear

主要说一下clear与析构函数的区别：clear是清空list，但是list中还保留这头节点

而析构函数是将整个list全部清理

        void clear()
        {
            iterator it = begin();
            while(it != end())
            {
                it = erase(it);
            }
        }

四、constructor

list的构造函数与vector的特别像

1、无参构造

list的无参构造与带头双向循环链表的init函数类似

不过STL中的无参构造调用了empty_init()这个函数，我们为了仿照库中的实现，也定义了这个函数

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

无参构造，我们直接让无参构造调用empty_init就可以

        list()
        {
            empty_init();
        }

2、迭代器区间构造

这个构造与vctor相同，完全的一模一样就不再赘述

        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            empty_init();
 
            while(first != last)
            {
                push_back(*first);
                first++;
            }
        }

3、拷贝构造

拷贝构造我们使用现代写法，调用迭代器区间的构造函数，然后将临时对象的头节点与我们的头节点交换就完成了操作

        list(const list& lt)
        {
            empty_init();
 
            list tmp(lt.begin(), lt.end());
            swap(tmp);
        }

这里调用了empty_init是为了先要有头节点，只有有了头节点push_back才不会崩溃

五、destructor

析构函数也与vector类似，不过我们可以先调用clear，然后手动释放头节点

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

六、operator=

=操作符重载我们也使用现代写法，与拷贝构造类似

        list& operator=(list lt)
        {
            swap(lt);
            return *this;
        }

---

总结

以上就是今天要讲的内容，本文仅仅简单的模拟实现了list，list的空间配置器和反向迭代器还没有实现