C++STL之list的模拟实现

目录

一.list准备

二. iterator迭代器

1._list_iterator

2.begin()、end()

3.const_begin()、const_end()

4.!=&&==

5.++ && --

6.operator*

7.operator->

三.Modify(修改)

1.insert()

2.erase()

3.push_back() && push_front()

4.pop_back&&pop_front

5.clear

四.constructor构造函数

迭代构造

拷贝构造

五.destructor析构函数

---

STL中list的使用也是和之前讲的类似，常用的接口就那些，可以参考list官方文档http://www.cplusplus.com/reference/list/list/?kw=list

本文章主要讲list的模拟实现.

list相当于是一个链表，对list操作相当于对链表操作

下面是对list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

一.list准备

上面提到了list是双向链表，而且是由每一个结点组成，所以我们先定义结点，包括三个成员：

_data数据，_prev指向前一个结点的指针，_next指向下一个结点的指针.

当然数据类型不能确定，使用模版来解决

	template<class T>class list_node{T _data;list_node<T>* _next;list_node<T>* _prev;};

结点创建完毕，就该创建链表了，链表只有一个类成员，既头结点，将上面结点名字重新定义

typedef list_node<T> Node;	
private:Node* _head;

一切准备就绪，开始正式工作

构造函数中初始化时，（list的构造函数）首先new一个头结点_head，然后因为是双向循环链表，而且一开始没有数据，所以让head的prev指向head，head的next指向head.

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

当然，还有结点的构造函数，方便我们后续进行new新的结点.

		list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}

这些构造函数只是暂时需要用到的，并不完整，文章下文会补充完善的.

二. iterator迭代器

关于迭代器，上一章我说了vector的模拟实现它的内部是由原生指针实现的，它之所以可以用原生指针，主要是因为vector的空间是连续的.

而list的空间是不连续的，所以不能直接使用原生指针.

但我们可以实现一个迭代器，然后内部实现对应的各种运算符操作.例如“++”，“--”等.

然后可以直接把指针转成迭代器使用即可.

下面开始实现迭代器.

1._list_iterator

这个类就是迭代器，它看起来像一个"指针"一样，进行各种比较或各种操作，它指向的是原链表中的一个结点，所以每次必须将原链表中的一个结点传入来构造迭代器.

这样的话，它的成员类型就是结点的类型list_node.

template<class T>//(暂时)
struct _list_iterator{typedef list_node<T> Node;_list_iterator(Node* node):_node(node){}}

2.begin()、end()

这两个函数应该很常见了，返回首元素，和尾元素.

但是问题是双向链表的首尾元素分别在哪呢？

双向链表一开始存在一个头结点，这个头结点不存储任何数据，它的next才是首元素，它的prev是最后一个元素.

begin()的位置是第一个元素，end()的位置是头结点的位置，如下图

 

所以begin()要返回头结点的next，end()直接返回头结点即可.

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

3.const_begin()、const_end()

之前写vector的时候，对于const类型我们直接加上const即可.但是这里就不可以了

之前我们写了begin(),返回类型是iterator，但是这个是const_iterator begin()

它俩之间不能构成重载，因为函数重载规则中没有返回值不同可以构成函数重载这一说.

这样就有了两个同名的函数，但是不能构成重载，这是编译不过去的.那我们该怎么解决呢？

可以在函数后加一个const来区分，但是当执行到_head->next时，由于加了const，_head已经不可以被解引用，引发编译错误.

这样也不可以，那该怎么办呢》

根据STL源码，它的迭代器有三个模板参数，分别为T，Ref，Ptr

普通迭代器三个参数为：T，T&，T*

const迭代器也有三个参数分别为T，const T&，const T*

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

此时代码如下：

	template<class T,class Ref, class Ptr>typedef _list_iterator<T, T&, T*> iterator;typedef _list_const_iterator<T, const T&, const T*> const_iterator;const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{return iterator(_head);}

4.!=&&==

这个很简单，直接返回两个迭代器相等或不相等即可.

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

5.++ && --

++

++有前置++也有后置++，实现方法具体可以看我之前讲的类和对象，仔细讲解了这些思路.

前置++，既先让node指向node的next即可，然后返回*this.

		iterator& operator++(){_node = _node->_next;return *this; }

后置++

为了区分前置++，需要在参数里面加一个int

思路是先保存当前结点，然后再让node指向node的next，最后返回tmp

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

-- 

前置--

和上面的思路一样，只是把next改成prev

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

后置--

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

6.operator*

*就是解引用，就是返回这个结点对应的值，所以直接返回data即可.

Ref此时为T&类型，可以读也可以写.

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

7.operator->

->这个操作符一般用在结构体指针中，并且左操作数必须为指针类型，所以我们返回的类型也应该为指针类型，既Ptr(T*)

只不过是与*的返回类型不同

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

三.Modify(修改)

这都是双链表的一些修改，在我之前写的里面有详细的讲解.这里便不再仔细讲述了.

1.insert()

		iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;//创建新结点并连接Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}

2.erase()

		iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}

3.push_back() && push_front()

这里直接复用了之前的insert代码

push_back()

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

push_front()

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

4.pop_back&&pop_front

pop_back()

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

pop_front()

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

5.clear

思路就是从头遍历链表，直到遇到end()，每遍历一个元素，就erase一个

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

四.constructor构造函数

无参构造函数第一部分已经说了，接下来说迭代构造和拷贝构造.

由于list的初始化构造中一部分需要经常利用，我们将其封装并放入私有成员里.

	private:void CreateHead(){_head = new Node;_head->_next = _head;_head->_prev = _head;}Node* _head;

迭代构造

这个类似于vector的迭代器构造，可以参考上一章

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

拷贝构造

    list(const list<T>& l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(l.cbegin(), l.cend());this->swap(temp);}

这里的swap我们需要自己实现一下，交换两个链表的头结点即可.

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

 

五.destructor析构函数

这个我们可以复用之前的clear，然后最后手动释放掉头结点.

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

list的模拟实现就到此为止了.

有不懂或错误的地方欢迎提问或指正哦