C++中list的使用及模拟实现

一，list的基本介绍

list是一个双向链表容器，允许在任意位置进行快速删除和插入操作。

1，list的底层是双向链表结构，双向链表中，每个元素存储在互不相关的节点中，在节点中保存着指向前一个节点和后一个节点的指针。

2，与forward_list相似，forward_list是单链表，只能向前迭代。而list是双向链表，可以前后迭代。

3，list与vector相比，它的插入和删除元素效率更高，不需要遍历一遍原链表。

二，list的一些基本使用

2.1，list的构造函数

list() //无参构造函数

list(size_t n,const value_type& val = value_type()) //n个va的构造

list(InputIterator first,InputIterator last) //迭代器区间构造

list(const list& x) //拷贝构造

示例:

void Test_List1()
{
   list<int> lt1; //无参构造，值为空

   list<int> lt2(4, 100); //4个100初始化

   list<int> lt3(lt2.begin(), lt2.end()); //迭代器区间构造

   list<int> lt4(lt2); //拷贝构造
}

注：C++11提供了initializer_list的新类型，主要用于初始化。

用法如下：

initializer_list<int> lt = { 1,2,3,4,5 };
list<int> lst(lt); //用lt中的元素初始化lst

但一般在写的时候，可以使用隐式类型转化

list<int> lt = { 1,2,3,4,5 }; //和上面代码一样

2.2，list的迭代器

list提供了双向迭代器，可用于遍历和操作容器中的数据。

begin()：返回指向第一个元素的迭代器。
end()：返回指向最后一个元素之后位置的迭代器。
rbegin()：返回指向最后一个元素的逆向迭代器。
rend()：返回指向第一个元素之前位置的逆向迭代器。

void Test_List2()
{list<int> myList = { 1, 2, 3, 4, 5 };// 正向迭代器遍历listcout << "正向遍历list: ";list<int>::iterator itr;for (itr = myList.begin(); itr != myList.end(); ++itr){cout << *itr << " ";}cout << endl;// 逆向迭代器遍历listcout << "逆向遍历list: ";list<int>::reverse_iterator ritr;for (ritr = myList.rbegin(); ritr != myList.rend(); ++ritr){cout << *ritr << " ";}cout << endl;}

运行结果：

2.3，list的插入

对于插入操作，list实现了如下几个常用的接口

push_back(x) //尾插

push_front(x) //头插

insert(iterator it ,x) //在迭代器位置之前插入x

示例：

void Test_List3()
{list<int> lt;//尾插lt.push_back(1);lt.push_back(2);cout << "push_back:";for (auto e : lt)cout << e << " ";cout << endl;//头插lt.push_front(4);lt.push_front(5);cout << "push_front:";for (auto e : lt)cout << e << " ";cout << endl;//迭代器lt.insert(lt.begin(), 9);cout << "insert:";for (auto e : lt)cout << e << " ";cout << endl;}

运行结果：

2.4，list的删除

对于删除，list提供的接口如下:

pop_back() //尾删

pop_front() //头删

erase(iterator it) //删除it位置

erase(iterator first,iterator last) //删除[first,last)区间

示例：

void Test_List4()
{list<int> it = { 1,2,3,4,5 };//尾删it.pop_back();cout << "pop_back:";for (auto e : it)cout << e << " ";cout << endl;//头删it.pop_front();cout << "pop_front:";for (auto e : it)cout << e << " ";cout << endl;//eraseit.erase(it.begin());it.erase(it.begin(), it.end());cout << "erase:";for (auto e : it)cout << e << " ";cout << endl;
}

三，list的模拟实现

3.1，链表节点的定义

//定义节点
template<class T>
struct list_node
{
   T _data; //存储的数据
   list_node<T>* prev;//指向前一个节点
   list_node<T>* next;//指向后一个节点
   //构造函数
   list_node(const T& data=T())
       :_data(data)
       ,prev(nullptr)
       ,next(nullptr)
   {}
};

3.2，链表主体

3.2.1，链表的大致轮廓（含注释）

template<class T>
class list
{
public:
   typedef list_node<T> Node;
   //构造函数
   list()
   {
       //当只有一个节点时，为了保证满足双向链表的规则
       //让新节点的next和prev指针指向自己
       _head = new Node;
       _head->_next = _head;
       _head->_prev = _head;
       _size = 0;
   }
private:
   Node* _head; //头节点
   size_t _size; //记录数据个数
};

3.2.2，常见接口的实现

插入操作

insert(iterator it,T x) ,迭代器前插入

void insert(iterator pos, const T& x)
{
   Node* cur = pos._node;
   Node* prev = cur->_prev;

   Node* newnode = new Node(x);
   //链接前一个指针和后一个指针
   // prev newnode cur
   newnode->_next = cur;
   cur->_prev = newnode;
   newnode->_prev = prev;
   prev->_next = newnode;

   ++_size;
}

push_back(x），尾插。直接开辟一个新节点来存储x的值，让新节点链接到链表的最后。

注意：需要改变头节点和原链表最后一个节点指针的指向。

void push_back(const T& x)
{
   Node* newnode = new Node(x);//开辟新节点存储x
   Node* tail = _head->_prev; //插入之前，原链表的尾节点

   tail->_next = newnode;
   newnode->_prev = tail;
   newnode->_next = _head;
   _head->_prev = newnode;

   ++_size; //插入后，数据个数++
}

push_front,头插。这里可以直接复用上面写过的insert逻辑。在迭代器begin() 位置之前插入x，也就是头插。当然尾插操作也可以复用

void push_front(const T& x)

{

insert(begin(), x);

}

删除操作

erase(iterator it),删除迭代器位置

删除之前，需要将前一个节点和后一个节点链接起来

void erase(iterator pos)
{
   assert(pos != end());

   Node* prev = pos._node->_prev;
   Node* next = pos._node->_next;
   //先将删除位置的前一个节点和后一个节点链接起来
   prev->_next = next;
   next->_prev = prev;
   delete pos._node; //释放当前节点

   --_size; //数据个数--
}

pop_back() ,尾删 ,复用erase逻辑。end(),是最后一个节点的下一个位置，所以要--

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

pop_front(),头删，复用erase逻辑

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

返回链表的数据个数

size_t size() const
{
return _size;
}

判断链表是否为空

bool empty() const
{
return _size == 0;
}

3.2.3，迭代器的实现

对于list的迭代器，我们用来遍历链表。那么，我们需要实现对++，--，！=，*，->等操作符的重载，同时还需要节点。所以我们需要对链表的节点进行一次封装，实现对++，--，！=，*,->等操作符的重载

代码如下（含注释）

//对节点进行封装
template<class T>
struct list_iterator
{typedef list_node<T> Node;      //节点重命名typedef list_iterator<T> Self; //迭代器重命名Node* _node;  //链表节点list_iterator(Node* node):_node(node){}//返回节点存储的数据T& operator*(){return _node->_data;}//返回当前节点数据的地址T* operator->(){return &_node->_data;}//++后返回下一个节点的地址Self& operator++(){_node = _node->_next;return *this;}//++后返回上一个节点的地址Self& operator--(){_node = _node->_prev;return *this;}//用存储的数据来判断节点相不相等bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

迭代器封装好后，我们就可以实现list的begin()和end();

template<class T>
class list
{
public:
   typedef list_node<T> Node;
   typedef list_iterator<T> iterator;
   iterator begin()
   {
       return _head->_next;
   }
   iterator end()
   {
       return _head;
   }

......//下面代码省略

};

现在可以看到我们对list迭代器的实现，只是实现了普通迭代器，还有const迭代器没有实现。

const迭代器的实现与普通迭代器的实现方式相似，只需将所返回值的类型改为const类型。

代码如下：

//对节点进行封装
template<class T>
struct list_const_iterator
{typedef list_node<T> Node;      //节点重命名typedef list_iterator<T> Self; //迭代器重命名Node* _node;  //链表节点list_iterator(Node* node):_node(node){}//返回节点存储的数据const T& operator*(){return _node->_data;}//返回当前节点数据的地址const T* operator->(){return &_node->_data;}//++后返回下一个节点的地址Self& operator++(){_node = _node->_next;return *this;}//++后返回上一个节点的地址Self& operator--(){_node = _node->_prev;return *this;}//用存储的数据来判断节点相不相等bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

这样就实现了const迭代器，然后我们在list类中实现cbegin(),cend()就可以了。

但是，这样写，代码冗余量太大了，而这两个迭代器的实现又十分相似，所以我们可以将这两个迭代器的代码结合。

这两个迭代器的区别是什么？就是返回值的类型不同，那么我们可以在迭代器的模板参数中增加两个参数,当这两个参数类型为普通类型时，就是普通迭代器；当这两个参数了欸行为const类型时，就是const迭代器。

代码如下：

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}//Ref可以为普通类型，也可以为const类型Ref operator*(){return _node->_data;}//Ptr可以为普通类型，也可以为const类型Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

3.3，代码总体

#include <iostream>
using  namespace std;namespace xg
{//定义节点template<class T>struct list_node{T _data;  //存储的数据list_node<T>* _prev;//指向前一个节点list_node<T>* _next;//指向后一个节点//构造函数list_node(const T& data=T()):_data(data),_prev(nullptr),_next(nullptr){}};template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}//Ref可以为普通类型，也可以为const类型Ref operator*(){return _node->_data;}//Ptr可以为普通类型，也可以为const类型Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class T>class list{public:typedef list_node<T> Node;//普通迭代器typedef list_iterator<T, T&, T*> iterator;//const 迭代器typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}//返回const类型const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}//构造函数list(){//当只有一个节点时，为了保证满足双向链表的规则//让新节点的next和prev指针指向自己_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//链接前一个指针和后一个指针// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;}void erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;//先将删除位置的前一个节点和后一个节点链接起来prev->_next = next;next->_prev = prev;delete pos._node;  //释放当前节点--_size;    //数据个数--}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size() const{return _size;}bool empty() const{return _size == 0;}void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){Node* newnode = new Node(x);//开辟新节点存储xNode* tail = _head->_prev;  //插入之前，原链表的尾节点tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;++_size;   //插入后，数据个数++}private:Node* _head;  //头节点size_t _size; //记录数据个数};}

3.4，简单测试

int main()
{
   xg::list<int> lt;
   //插入
   lt.push_back(1);
   lt.push_back(2);
   lt.push_front(3);
   lt.push_front(4);
   auto it = lt.begin();
   while (it != lt.end())
   {
       cout << *it << " ";
       ++it;
   }
   cout << endl;
   //删除
   lt.insert(lt.begin(), 5);
   lt.erase(lt.begin());
   lt.pop_back();
   lt.pop_front();
   it = lt.begin();
   while (it != lt.end())
   {
       cout << *it << " ";
       ++it;
   }
   cout << endl;
   //迭代器遍历
   it = lt.begin();
   while (it != lt.end())
   {
       cout << *it << " ";
       ++it;
   }
   cout << endl;
   return 0;
}