【STL_list 模拟】——打造属于自己的高效链表容器

一、list节点

​ list是一个双向循环带头的链表，所以链表节点结构如下：

	template<class T>struct ListNode{T val;ListNode* next;ListNode* prve;ListNode(int x){val = x;next = prve = this;}};

二、list迭代器

2.1、list迭代器与vector迭代器区别

​ list迭代器与vector迭代器不一样，不能使用简单的原生指针了；

vector中迭代器可以使用原生指针，因为vector的存储空间是连续的，可以通过指针+/-/++/–找到下一个（上一个）位置；而list(链表)我们知道存储空间是不连续的，不能通过指针++/—找到下一个（上一个）节点；那我们就不能使用原生指针。

2.2、list迭代器实现

​ 既然原生指针不能满足我们的需求，那我们就要用其他的方法来实现迭代器，这时候类的封装的意义就体现出来了；我们只需要对原生指针进行封装，然后使用运算符重载来修改迭代器++/–这些行为，这样就可以满足我们的需求了。

具体代码如下：

	template<class T, class Ref, class Str>class list_iterator{typedef ListNode Node;typedef list_iterator iterator;public:list_iterator(Node* node){_node = node;}//前置++iterator operator++(){Node tmp(_node);_node = _node->_next;return tmp;}//后置++iterator operator++(int){_node = _node->_next;return *this;}//前置--iterator operator--(){Node tmp(_node);_node = _node->_prve;return tmp;}iterator operator++(int){_node = _node->_prve;return *this;}bool operator==(const iterator& it){return _node == it._node;}bool operator!=(const iterator& it){return _node != it._node;}Ref operator*(){return _node->val;}Ptr operator->(){return &(_node->_val);}private:Node* _node;};

三、list实现

3.1、构造函数

先看一下list构造函数的接口

构造函数	接口说明
list()	默认构造函数，构造一个空的list
list (size_type n, const value_type& val =value_type())	用n个val值构造list
list (InputIterator first, InputIterator last)	还有一段迭代器区间初始化
list (const list& x)	拷贝构造函数

​ 这里我们实现的list是带头双向循环链表，具体结构与之前的双向链表相同。

在构造之前，我们需要先构造一个头结点，这里就写一个函数 empty_init 来构造这个头结点。

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

默认构造函数

list()
{empty_init();_size = 0;
}

用n个val值构造

list(size_t n, const T& val)
{/*_head = new Node();_head->_next = _head;_head->_prve = _head;*/empty_init();for (size_t i = 0; i < n; i++){Node* newnode = new Node(val);newnode->_next = _head->_next;newnode->_prve = _head->_next;_head->_next->_prve = newnode;_head->_next = newnode;}_size = n;
}

迭代器区间构造

​ 使用迭代器区间构造，这里复用一下后面的push_back直接尾插来构造。

template<class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();_size = 0;while (first != last){push_back(*first);_size++;}
}
void push_back(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;newnode->_prve = _head->_prve;_head->_prve->_next = newnode;_head->_prve = newnode;
}

拷贝构造函数

​ 拷贝构造，这里直接复用上面迭代器构造即可。

		list(const list& l){empty_init();list(l.begin(), l.end());_size = l.size();}

3.2、迭代器

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

​ 这里迭代器返回值，可以直接返回节点指针（因为单参数的构造函数支持隐式类型转换）。

3.3、Capacity

​ 主要就是empty和size（判断空和数据个数）

		//Capacitybool empty(){return _head == _head->_next;}size_t size(){/*size_t ret = 0;Node* ptail = _head->_next;while (ptail != head){ret++;ptail = ptail->_next;}return ret;*/return _size;}

​ 这里遍历链表来计算数据个数，代价太大了，我们直接写一个成员变量，在初始化，插入和删除时修改，会方便很多。

3.4、增删查改

​ 这里增删查改就实现其中的一部分，其他的不太常用。

3.4.1、push_back、push_front、pop_back、pop_front

​ 头插尾插，头删尾删，对于list而言，只需要修改指针的指向；

void push_back(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;newnode->_prve = _head->_prve;_head->_prve->_next = newnode;_head->_prve = newnode;_size++;
}
void push_front(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head->_next;newnode->_prve = _head;_head->_next->_prve = newnode;_head->_next = newnode;_size++;
}//删
void pop_back()
{if (!empty()){Node* del = _head->_prve;_head->_prve->_prve->_next = _head;_head->_prve = _head->_prve->_prve;delete del;_size--;}
}
void pop_front()
{if (!empty()){Node* del = _head->_next;_head->_next->_next->_prve = _head;_head->_next = _head->_next->_next;delete del;_size--;}
}

3.4.2、insert

​ insert在指定位置插入数据，看它的参数列表，大概就知道，要在迭代器position 迭代器位置（之前）插入数据（1个或者n个），或者插入一段迭代器区间的数据。

//insert
void insert(iterator pos, const T& val)
{Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;++_size;
}
void insert(iterator pos, size_t n, const T& val)
{for(size_t i = 0; i < n; i++){Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;}_size+=n;
}
void insert(iterator pos, int n, const T& val)
{for(size_t i = 0; i < n; i++){Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;}
}

这里需要注意：

​ 看到这里可能会疑惑，为什么实现了两个插入n个数据 的insert函数；

​ 因为，当数据类型是int时，下面模版实例化出的函数（iterator , int , int）比这里实现的(iterator , size_t , int)更加匹配；编译器就会去调用更加匹配的函数，就会出错。这里就是为了防止这种出错。

​ 插入迭代器的数据，与使用迭代器区间构造初始化相似，list只需改变指针指向即可。

		template<class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last){while (first != last){Node* newnode = new Node(*first);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;++first;}}

3.4.3、erase

​ erase删除一个节点，我们要修改前后节点的指针指向。

iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* next = del->_next;Node* prve = del->_prve;next->_prve = prve;prve->_next = next;delete del;return next;
}

​ 在我们删除节点之后，之前的迭代器就会失效，为了解决迭代器失效问题，我们就使用返回值，返回新的迭代器。

3.4.4、swap

​ 这里实现的list只有一个成员函数（头结点的指针），直接交换即可。

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

3.4.5、clear

​ clear函数，清理数据，（保留头结点）。

		//清除数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数，清理数据，（保留头结点）。

		//清除数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

3.5、析构函数

​ 析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

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

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws