STL中list实现

STL中list的实现

️简单介绍

list是一个容器，其原理是链表，但是链表有很多种，带头/不带头单链表、双向带头不带头链表、双向带头循环链表等等他们的结构不同，效率也不同，其中双向循环的结构使得其任意位置插入删除元素****时间复杂度都是O(1) 所以list的实现是使用的双向循环链表实现。

双向循环链表的每个结点都有prev和next两个指针，分别指向其前一个结点和其后一个结点，这种结构实现了双向循环。

️功能实现

• 这里将链表的结点封装成了一个类 和标准库的实现一样

//结点
	template<class T>//用模板 实现泛型编程
	struct __list_node
	{
    
		__list_node* prev;
		__list_node* next;
		T data;
		
		__list_node(const T& val = T())
			:prev(nullptr)
			,next(nullptr)
			,data(val)
		{
    

		}
	};

每个结点包含三个成员变量 两个指针，指向该结点上一个结点和下一个结点、还有一个用来存数据的data类
还有一个含有缺省值的默认构造函数

构造函数

一个list类有一个成员变量 头结点指针变量，该头结点的prev和next都是指向的自己，这种结构使得它可以生成天然的双向循环链表，后面插入数据都是链接在此头结点的后面。

类的主要构成：

template<class T>
struct __list_node
{
    
    __list_node* prev;
    __list_node* next;
    T data;
    //这里给了一个临时对象的缺省值 使得创建对象无论传不传参都可以有默认的构造函数可以用
    __list_node(cosnt T& val=T())
        :prev(nullptr)//初始化列表初始化
        ,next(nullptr)
        ,data(val)//自定义类型最好是用初始化列表初始化
    {
    
        
    }
}
template<class T>
class list
{
    
    typedef __list_node Node;//类型重定义 简化代码
    public:
    ....成员函数
    
    private:
    Node* _head;//成员变量 头结点指针
}

• 通过上面的介绍和图解，知道list类只有一个比较重要的成员变量，就是一个头结点指针，那么构造函数主要就是，为该头结点指针开辟指向的空间；再完成头结点的prev和next的链接关系即可。

普通构造函数：

list()
{
    
    _head=new Node();
    _head->prev=_head;//初始化让头尾指针都是指向自己
    _head->next=_head;
}

迭代器区间构造函数：

为了后面的拷贝构造更方便，我们还实现了一个可以用一段迭代器区间初始化的构造函数(这里涉及push_back()函数和迭代器知识，如有疑惑可先看下面的push_back()和迭代器的实现)

void emptyInit()
{
    
    _head=new Node();
    _head->prev=_head;
    _head->next=_head;
}

//设置模板 接收的迭代器类型可以是任何类型 
template<class InputIterator> 
list(InputIterator first,InputIterator second)
{
    
    //先完成简单的构造 初始化成员变量
   //_head=new Node();
   //_head->prev=_head;
   //_head->next=_head;
   //上述初始化代码可以封装为一个 初始化函数 emptyInit()
   emptyInit();
   while(first!=second)
   {
    
       push_back(*first);//push_back函数下面介绍
       ++first;//这里的first是迭代器 也是下面介绍 
   }

}

拷贝构造

• 拷贝构造首先需要调用普通构造（emptyInit()与普通构造函数相同，这里就是直接掉emptyInit()),然后再将被拷贝对象的数据拷贝到当前对象（用的是push_back()将数据一一尾插到当前对象)

传统写法

list(const list<T>& lt)
{
    
    emptyInit();
    for(auto& e:lt)
    {
    
        push_back(e);//将数据一一尾插到当前对象中
    }
}

现代写法

现代写法就用到了上面的迭代器区间构造函数

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

list(const list<T>& lt)
{
    
    emptyInit();
    list,T> temp(lt.begin(),lt.end());
    swap(temp);//成员函数，封装了std::swap(T& a,T& b)
}

赋值重载

赋值重载的大部分步骤跟拷贝构造类型，但是有一点不同的是拷贝构造构造的是新的对象，而赋值重载不是，那么赋值前就需要对该对象的数据进行清理

• 这里的清理用的是封装起来的clear函数，clear函数又是封装erase得到的（erase下面会介绍，也可以先到下面看erase实现再来看这个地方）

传统写法

void clear()
{
    
	iterator it = begin();
	while (it != end())
	{
    
	//erase(it);//这里要接收返回值否则就会崩 因为有迭代器失效 erase返回的是删除结点的下一个结点位置
		it=erase(it);
	}
}

list<T>& operator=(list<T>& lt)
{
    
    clear();
    list<T>::iterator it=lt.begin();
    while(it!=lt.end())
    {
    
        push_back(*it);
        ++it;
    }
    return *this;
}

现代写法

复用写好的拷贝构造拷贝一份我们想要的对象，然后利用交换函数交换两者的头指针即可。

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

析构

• 析构函数是利用的clear函数去释放每个结点（clear函数里用的又是erase函数，erase是用的尾删，直到删的只剩头结点点为止），然后将头结点也释放，将头结点指针置空。

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

尾插、尾删

尾插

• 双向带头循环链表的尾插很简单，创建好了新结点再将其和原链表最后一个结点和头结点关联起来即可。
  

//尾插
void push_back(const T& x)
{
    
	Node* tail = _head->prev;
	Node* newnode = new Node(x);

	// _head tail newnode
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = _head;
	_head->prev = newnode;
}

尾删

尾删就更简单了

• 先拿到链表的倒数第二个结点的地址，然后将其和头结点关联起来，使得链表的尾结点和头结点失去关联即可。

需要注意的是尾删要记得释放尾结点的空间！

void pop_back()
{
    
	Node* tail = _head->prev;
	Node* newtail = tail->prev;
	newtail->next = _head;
	_head->prev = newtail;
    delete tail;//释放删除结点空间
    tail=nullptr;
}

头插、头删

• 头插头删的原理基本与上面的尾插尾删一样，这里就不介绍了。

头插

void push_front(const T& val)
{
    
	Node* next = _head->next;
	Node* newnode = new Node(val);
	newnode->next = next;
	next->prev = newnode;
	_head->next = newnode;
	newnode->prev = _head;
}

头删

void pop_front()
{
    
	Node* first = _head->next;
	Node* second = first->next;
	_head->next = second;
	second->prev = _head;
	delete first;
	first = nullptr;
}

任意位置的插入与删除

插入

iterator& insert(iterator pos, const T& val)
{
    
	Node* prev = pos._node->prev;
	Node* newnode = new Node(val);//创建新结点

	//链接
	newnode->next = pos._node;
	pos._node->prev = newnode;
	prev->next = newnode;
	newnode->prev = prev;
	return pos;
}

删除

iterator 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;//销毁结点
	return iterator(next);
}

️正向迭代器

迭代器这里也是封装出来的，将迭代器写成一个类，其成员变量就是一个指针，该指针就是迭代器的核心，迭代器的操作都是围绕这里这个指针操作的。

版本一：

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 &(operator*());
    }
    
    Self& operator++()//++ 重载
    {
    
        _node=_node->next;
        return *this;
    }
    
    Self operator++(int)//后置加加
    {
    
        Self temp(*this);//拷贝构造
        _node=_node->next;
        return temp;
        
    }
    
     Self& operator--()
    {
    
        _node=_node->prev;
        return *this;
    }
    
    Self operator--(int)
    {
    
        Self temp(*this);//拷贝构造
        _node=_node->prev;
        return temp;
    }
     bool operator==(Self& it)
	{
    
		return _node == it._node;
	}

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

• 在list类中引入迭代器 ，设置begin() 、end()迭代器相关函数，就可以使用迭代器了

template<class T>
class list
{
    
    typedef __list_node Node;//类型重定义 简化代码
    typedef __list_iterator iterator;//在list类中重定义迭代器 
    public:
   iterator begin()
   {
    
       return iterator(_head->next);//第一个结点就是迭代器起始位置
   }
    
    iterator end()
    {
    
        return iterator(_head);//头结点可以作为迭代器 其是最后一个结点的下一个结点 
        //迭代器都是左闭右开的
    }
    
    private:
    Node* _head;//成员变量 头结点指针
}

上面就完成了一个基本的正向迭代器 但是这只是一个非const版本的迭代器 那么如果还要实现一个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就可以了 
    Ref operator*()//* 重载
    {
    
        return _node->data;
    }
    //这里的返回值类型就返回模板中的Ptr即可
    Ptr operator->()//-> 重载
    {
    
        return &(operator*());
    }
    
    Self& operator++()//++ 重载
    {
    
        _node=_node->next;
        return *this;
    }
    
    Self operator++(int)//后置加加
    {
    
        Self temp(*this);//拷贝构造
        _node=_node->next;
        return temp;
        
    }
    
     Self& operator--()
    {
    
        _node=_node->prev;
        return *this;
    }
    
    Self operator--(int)
    {
    
        Self temp(*this);//拷贝构造
        _node=_node->prev;
        return temp;
    }
     bool operator==(Self& it)
	{
    
		return _node == it._node;
	}

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

//list类中 对上面迭代器的引入
template<class T>
class list
{
    
    typedef __list_node Node;//类型重定义 简化代码
    
    typedef __list_iterator<T,T&,T*> iterator;//实例化模板
    typedef __list_iterator<T,const T&,const T*> const_iterator;
    
    public:
   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);
    }
    
    private:
    Node* _head;//成员变量 头结点指针
}

//两个用来测试上面迭代器是否有效的函数
void testiterator2(const list<int>& lt)
{
    
   list<int>::const_iterator cit=lt.begin();
    while(cit!=lt.end())
    {
    
        cout<<*cit<<endl;
        ++cit;
    }
}

void testiterator1()
{
    
    list<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    lt1.push_back(5);
    lt1.push_back(6);
    list<int>::iterator it=lt1.begin();
    while(it!=lt1.end())
    {
    
        cout<<*it<<endl;
        ++it;
    }
    testiterator2(lt1);
}

调用过程图示：