【C++】手把手教你写出自己的list类

【C++】手把手教你写出自己的list类

讲完vector的相关知识，今天我们来看一下list。

目录

• list的介绍
• list的模拟实现
• • list的构造
  • • 构造函数的使用
    • 构造函数的模拟实现
  • 迭代器
  • • 迭代器的使用
    • 迭代器的模拟实现
  • 拷贝构造
  • • 拷贝构造的使用
    • 拷贝构造的模拟实现
  • 赋值
  • insert
  • earse
  • pop_back 与 pop_front
  • clear
  • 析构函数

list的介绍

c++中的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的库函数使用，边对list(c++98版本)进行模拟实现。

ps:这边建议没有看过前两篇string和vector模拟实现的同学，可以先看一下，以便形成一个更整体的理解。
【C++】手把手教你写出你自己的String类
【C++】手把手教你写出自己的vector类

list的构造 构造函数的使用

list 的构造函数有四种

构造函数接口说明list()00list(size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素list(const list& x)拷贝构造函数list(InputIterator first,InputIterator last)用其他迭代器区间中的元素构造list

使用实例:

#include
using namespace std;

int main()
{
	listl1; //构造空的l1
	listl2 (4,100); //构造l2,含有4个100
	listl3 (l2.begin(),l2.end()); //使用l2的迭代器 的区间构造
	listl4 (l3);  //用l3拷贝构造l4
	// 以数组为迭代器区间构造l5
	int array[] = {16,2,77,29};
	std::list l5 (array, array + sizeof(array) / sizeof(int) );
}

构造函数的模拟实现

在实现构造函数之前，我们先要搞清楚，list里的链表结构是带头结点的双向链表。

这里我们先实现一下无参构造函数。

这里我们要明白，我们初始化了什么？对于一个带头结点的双向链表，无参初始化就是建立一个头结点（不存储数据），并且把指针指向自身。

所以，实现构造函数并不困难。

1. 将节点的结构 封装到结构体中

   template
   struct __list_node
   {
     //构造函数
     __list_node(const T& val = T())
       :_next(nullptr)
       :_prev(nullptr)
       :_val(val)
     {}
       
     __list_node* _next;
     __list_node* _prev;
     T _val;
   };
   

2. 实现无参构造函数

template
class list
{
  typedef __list_node Node;
  
public:

  list()
  {
     _head=new Node();
     _head->next=_head;
     _head->prev=_prev;
  }
private:
  Node* _head;  
   
} 
}

迭代器 迭代器的使用

list迭代器的使用与string,verctor没有太大区别。但在结构上有很大的不同。

函数声明接口说明begin+end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器rebegin+rend返回第一个元素的reverse_iterator,即end位置,返回最后最后一个元素下一个位置的reverse_+iterator,即begin位置

void print_list(const list& l)
{
   list::const_iterator it =l.begin();
   for(it;it!=l.end();++it)
   {
     cout<<*it< 
 
迭代器的模拟实现 
在我们讲解list的迭代器之前，我们先来对迭代器分一下类：
 迭代器有两种实现方式，具体应根据容器底层数据结构实现：
 
 
原生态指针 ，比如vector
 
 
将原生态指针进行封装，因迭代器使用形式要与指针完全相同，因此在自定义的类中必须实现以下方法：
 
  1. 指针可以解引用，即迭代器的类中必须重载operator*()
  2. 指针可以通过->访问其指空间成员，迭代器类中必须重载operator->()
  3. 指针可以通过++向后移动，即在迭代器中重载opoerator++() 与operator++(int)
      (ps：对于是否需要 -- ,需要根据具体的结构来抉择，双向链表可以前后移动，
       所以需要重载--,但是forward_list（单链表结构）就不需要重载)
 4.  迭代器需要进行是否相等的比较，既需要重载operator==() 与operator!=()
 
 
简而言之，无论是哪种迭代器，目的都是要伪装成指针
 
 
那么，list属于哪种迭代器呢?
 很显然，属于第二种，为什么？
 因为这是list的结构决定的：
 
对于vector ,由于是连续存储，我们不需要重载++,可以直接通过指针的加减来实现访问元素，但是list 不是连续存储，我们要通过节点事先存储的next指针来访问下一个元素，而不能直接++。
对于vector,指针的解引用对应的是相应的值，而对于list ,每个位置存储的是一个结构体，不能直接通过解引用来得到对应数值，而应该 (*_head)._val
 
 
 
vector 和 list 的迭代器 在32位系统之下 所占空间为多少？
 实际上一样的，都是4个字节，因为存储的都是地址
 
 
所以，我们需要对原生态指针进行封装，并对部分运算符进行重载：
 
template
struct __list_iterator
{
  typedef __list_iterator  self;
  typedef __list_node Node;
  
  Node* _node;
  
  //构造函数
  __list_iterator(Node*node)
      :_node(node)
  {}

  Ref operator*()
  {
     return _node->_data;
  }    
  Ptr operator->()
  {
    return &_node->_data;
  }
  self& operator++()
  {
    _node=_node->_next;
    return *this;
  }
  self operator++(int)
 {
	self tmp(*this);
	_node = _node->_next;
	return tmp;
 }

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

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

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

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

 
至此，我们完成了迭代器，我们迭代器的库方法在list类中实现一下：
 
这里要注意 end()取的位置为什么是_head. 这是因为list是一个循环链表，而end()取地位置是最后一个位置的下一个，也就是头节点_head的位置
 
template
class list
{
  typedef __list_nodeNode;
public:
  typedef __list_iterator iterator;
  typedef __list_iterator const_iterator;
  
         iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}
        
        list()
		{
			// 带头双向循环
			//_head = new Node(T());
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

 
private:
  Node*_head; 
}
 
看到这里，我相信许多同学抱有疑问：
 为什么迭代器的模板参数有三个？
 
template
 
这是原码中一个比较巧妙地设计：
 
第一个参数 控制传入的数据类型
第二参数 分辨 iterator 和 const_iterator
第三个参数 用于 "->"的重载
 
这里我们着重讲一下 模板参数 Ref 和 Ptr:
 
Ref
 对于大多数容器，迭代器都有两种，一种是支持 读写 的，一种是只支持 读 的，分别为iterator 和 const_iterator。
 对于使用原生指针 实现的迭代器（比如string,list），区分二者很简单，只需要在调用的时候添加 const即可：
 
 typedef T*  iterator;
 typedef const T* const_iterator;
 
但是对于 封装指针实现的迭代器(比如 list),我们需要对所有的成员函数都添加const,也就是说，我们要写两份迭代器，这样会使代码冗余，可读性降低。
 
所以，我们可以在模板参数上”做手脚“，增加一个参数(这里可以暂时忽略第三个参数)，这样我们可以在只写一个迭代器的前提下区分二者了。
 
typedef __list_iterator iterator;
typedef __list_iterator const_iterator;
 
按照原码，这里我们给迭代器传的参数是 T& ,也就是 引用类型。
 
Ptr
 
第三个参数 Ptr 是为了重载 ->而建立的。
 
我们在传参的时候 Ptr 是 T*类型，也就是 T的地址。
 
  Ptr operator->()
  {
    return &_node->_data;
  }
 
使用实例：
 
对于下面的例子，我们使用迭代器访问节点的时候，三个模板参数分别为****
 
struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;

		TreeNode(int val=-1)
			:_left(nullptr)
			,_right(nullptr)
			,_val(val)
		{}
	};

void test_list2()
{
		listlt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));

		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it)._val << endl;
			cout << it->_val << endl;
			
			++it;
		}
		cout << endl;

	}
 
这里有一个小的细节，当我们使用->访问节点的时候，实际上正确的写法是 it->->_val:
 第一个-> 取得 it指向得节点得地址，第二个 ->取得节点的_val，但是编译器为了增加可读性，在编译的时候做了特殊处理，省去了一个->。
 
 
拷贝构造 
拷贝构造的使用 
拷贝构造是很常用的一种构造方式，指用已有的list来构造新的list.
 
    listl2 (4,100); //构造l2,含有4个100
	listl4 (l2);  //用l2拷贝构造l4
 
拷贝构造的模拟实现 
拷贝构造的写法我们在之前已经讲了很多次了，其中最值得我们注意的是我们应该避免浅拷贝的使用，原因不再解释。
 
拷贝构造一般有三种写法：
 
传统写法1
 
这个写法是最容易想到的，先建立头节点并初始化，然后向头节点后链接元素。
 
list(const list& lt)
{
  //创建头结点 ，并初始化
  _head=new Node;
  _head->_next=_head;
  _head->_prev=_head;
  //赋值
  for(const auto& e: lt)
  {
    push_back(e);
  }
}
 
现代写法
 
现代写法依旧是熟悉的“坐享其成”，我们使用迭代器构造函数 构造一个tmp, 然后将tmp和this的头节点交换，这样的交换使待拷贝对象获得了tmp的内容，也就达到了拷贝构造的目的。
 
这样的思想虽然暂时在list上没有在效率上体现优势，但在其他的结构中，这种“坐享其成”思想有很大的作用
 
template
  list(InputIterator first,InputIterator last)
  {
	  _head=new Node;
	  _head->_next=_head;
	  _head->_prev=_head;
	  
	  while(first!=last)
	  {
	    push_back(*first)
	    ++first;
	  }
 }
 	  
list(const list& lt)
{
	 _head=new Node();
	 _head->_next=_head;
	 _head->_prev=_head;
	 
	 listtmp(lt.begin(),lt.end());
	 std::tmp(_head,tmp._head);
}
 
 
赋值 
list之间的赋值也是常用的。我们只需要将 "="重载即可。
 
传统写法
 关于赋值的一些细节在string的模拟实现已经讲了，这里不再赘述，我只再讲一下思路：
 
先将被赋值的对象内容全部清空（保留头结点），然后讲新的节点插入即可。
 
list& operator = (const list& lt)
{
  if(this !=<)
  {
    clear();
    for(const auto& e: lt)
    {
      push_back(e);
    }
  }
  return *this;
}
 
现代写法
 
现代写法依旧是“坐享其成”的方式，通过交换头节点的方式，得到形参lt（lt是经过深拷贝得到的临时对象）的内容
 
list& operator = (const list lt)
{
  swap(_head,lt.head);
  return *this;
}
 
 
insert 
iterator insert(iterator pos,const T& x)
{
  assert(pos!=end());
  Node*cur=pos._node;
  Node*prev=cur->_prev;
  
  Node*newnode = new Node();
  newnode->_prev=prev;
  newnode->_next=cur;
  cur->_prev=newnode;
  
  //返回newnode位置的迭代器
  return iterator(newnode);
  
}
 
 
earse 
erase除了了删除数据，它还具有返回值，它会返回删除元素的下一个位置的迭代器。
 
iterator earse(iterator pos)
{
  assert(pos!= end());
  Node*cur=pos._node;
  Node*cur->prev=_prev;
  Node*cur->next=_next;
  
  delete cur;
  prev->_next=next;
  next->_prev=prev;
  
  return iterator(next);
}
```、
---


## push_back 与push_front
尾插函数与头插函数，可以直接借用insert来实现。

```cpp
void push_back(const T& x)
		{
			insert(end(), x);
		}
 
void push_front(const T& x)
		{
			insert(begin(), x);
		}
 
 
pop_back 与 pop_front 
同理，头删和尾删也可以直接通过earse来实现
 
void pop_front()
		{
			erase(begin());
		}
 
void pop_back()
		{
			erase(--end());
		}
 
 
clear 
clear函数 会将 list容器中除了头结点外的所有节点都删除。
 
在实现clear的时候，我们可以利用earse这种返回删除元素下个位置的特点，来逐个删除元素
 
void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
 
 
析构函数 
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
 
 
至此，我们完成了list容器中大部分基础功能，有兴趣的同学可以进一步完善。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5698469.html