list的使用以及模拟实现

本章目标

1.list的使用
2.list的模拟实现

1.list的使用

在stl中list是一个链表,并且是一个双向带头循环链表,这种结构的链表是最优结构.
因为它的实现上也是一块线性空间,它的使用上是与string和vector类似的.但相对的因为底层物理结构上它并不像vector是线性连续的,它并没有重载像[]这样的运算符,也没有重载流插入流提取这样的操作.
在这里的使用我们只介绍它的最为特别的接口

1.1sort

在这里list专门提供了一个sort接口用来排序,因为list的迭代器原因它并不能使用算法库中的sort,并且两个sort的底层并不相同.

在算法库中要求的sort是一个随机迭代器.而对于list来说,因为它底层的实现原因,它的底层是一个双向迭代器.

在c++中一共有三种迭代器.
随机迭代器,双向迭代器,单向迭代器

对于这三种迭代器它们支持的操作是从右到左依此兼容的.

例如要求双向迭代器的reverse接口是可以传随机迭代器的

对于这两个sort来说,算法库中的sort的底层是快排,而在list容器中的sort底层是用的是归并排序.
因为双向迭代器是不支持相减操作的,而在快排中有一个找基准值的过程,我们会用左右端点相减来去取基准值防止排序的时间复杂度达到n方的程度.
并且这个list中的sort的效率并不如算法库中的sort效率高

1.2remove和remove_if

而者整体的逻辑都是删除特定值,但是remove是移除给你传过去val相等的值,remove_If是删除满足特定条件的值

1.3splice和merge

我们先说第一个接口,这个接口的作用是两个list相互拼接起来.


我们可以拼接整个链表也可拼接某个迭代器位置的,也可以拼接某个迭代器区间.
但是我们用来拼接的那个链表被拼接的地方将会消失

我们再来说第二个接口,它的作用是用来合并两个有序list到一个list中,
在这里我们提供一段代码供大家测试

#include <iostream>
#include <list>

// compare only integral part:
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }

int main ()
{
  std::list<double> first, second;

  first.push_back (3.1);
  first.push_back (2.2);
  first.push_back (2.9);

  second.push_back (3.7);
  second.push_back (7.1);
  second.push_back (1.4);

  first.sort();
  second.sort();

  first.merge(second);

  // (second is now empty)

  second.push_back (2.1);

  first.merge(second,mycomparison);

  std::cout << "first contains:";
  for (std::list<double>::iterator it=first.begin(); it!=first.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;

1.4unique

这个接口的作用是用来去除当前list中相同的元素,但是去除相同的元素是有要求的,它是要求我们的list是有序的.

2.list的模拟实现

因为list的底层并不是一块连续的物理空间,在不同的stl版本中实现并不相同,c++标准并没有规定他是怎么实现的,我们只需要将其进行封装,给予接口供其使用即可.
我们在这里实现list的结构是参考gcc的SGI版本的stl.



在SGI版本的stl中,将链表结点,迭代器,链表封装为三个类.
并且链表结点和迭代器的实现,并没有class而是用的struct,将所有成员都开放为公有.
因为我们在使用list的时候,并不会去通过链表结点和迭代器去进行内部的访问,而且因为c++标准并没有明确规定.各个平台环境下实现也各有不同.如果使用就会出现移植性问题.者也算是一种隐形的封装.

2.0list容器的构成

跟据SGI版本的源码,我们也实现三个类,list,list_node,list_iterator

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)
	{
	}
};

template <class T >
struct list_iterator
{
	typedef List_Node<T> Node;
	typedef list_iterator<T> self;
	Node* node;
	list_iterator( Node* val)
		:node(val)
	{
	}
}:

template <class T>
class list
{
	typedef List_Node<T> Node;
		
public:
	list()
{
	head = new Node;
	head->next = head;
	head->prev = head;
}
private:
	Node* head;
	size_t _size;

};

1.在这里面我们将所有需要用到模板的地方都进行了typedef,者样做第一个是为了封装,我们在这里面使用list只给客户提供接口,并不希望,它们,通过通过结点和迭代器进行访问.第二是为了我们实现的方便.
2.对于迭代器,我们主要实现它解引用.我们要通过这个迭代器去访问它的数据.
所以它的底层也因该是一个结点类型的指针,
3.对于结点的构造函数.我们在给val缺省值的时候,给了一个匿名对象,这样如果我们要给的值是一个自定义类型,它就会调用它的构造,如果是内置类型也是调用一个默认构造.

2.1插入删除

因为list底层的结构是一个双向带头循环的链表.它的逻辑上的结构是和我之前发的博客是一致的.
我们在这里涉及底层逻辑,不过多阐述.只提与之有出入的地方.

void push_back(const T& x)
{
	/*Node* tail = head->prev;
	Node* newnode = new Node(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = head;
	head->prev = newnode;*/
	insert(end(), x);
}

在这里我们可以主动实现(注释中的代码)也可以复用后面要实现的insert函数.

2.1.1insert

void insert(iterator pos, const T& val)
{
	//prev newnode  cur 
	Node* prev = pos.node->prev;
	Node* cur = pos.node;
	Node* newnode = new Node(val);
	prev->next = newnode;
	cur->prev = newnode;
	newnode->prev = prev;
	newnode->next = cur;
	++_size;
}

逻辑上和之前的双向链表是一样的但是与之前不同的是,在这里我们传的是一个迭代器.

2.1.2erase

iterator erase(iterator pos)
{
	//prev pos next
	Node* prev = pos.node->prev;
	Node* next = pos.node->next;
	Node* cur = pos.node;
	prev->next = next;
	next->prev = prev;
	delete cur;
	--_size;
	//return next;
	return iterator(next);
}

对于erase来说,要注意迭代器失效的问题.要返回被删位置的迭代器.
在这里我们也给一个用next结点指针初始化的匿名对象.

void push_front(const T& x)
{
	insert(begin(), x);
}
void pop_front()
{
	erase(begin());
}
void pop_back()
{
	erase(--end());
}

对于它们的尾插头插的复用,我们需要实现list中begin(),end(),迭代器++,–等接口.

iterator begin()
{
	return iterator(head->next);
}
iterator end()
{
	return iterator(head);
}

因为begin和end是一对左闭右开的区间.我们又是一个双向链表.
它存储数据的第一个位置begin是头节点的下一个结点.
它的end是最后存储数据的下一个结点.也就是哨兵位.

Ref 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)
{
	return node != it.node;
}
bool operator==(const self& it)
{
	return node == it.node;
}

我的迭代器主要是为了遍历修改.而list是需要迭代器是实现这些运算符重载去完成上面的功能的.对于这些运算符重载是和我们之前学过的日期类的整体逻辑是相似的.在这里不做过多赘述.

2.2const迭代器

对于const迭代器来说,我们至于要要让迭代器指向的对象值不被修改即可.我们至于要修改*的运算符重载.,让它返回的对象是一个const对象即可.但是再重新写一个类的开销太大了.我们可以多给一个模板参数.

template <class T ,class Ref,class Ptr>
struct list_iterator
{
	typedef List_Node<T> Node;
	typedef list_iterator<T,Ref,Ptr> self;

用ref代替*运算符重载的返回值

Ref operator*()
{
	return node->data;
}

我们至于要再list里面传两个不同的模板类的参数即可.
本质上还是写了两个类.只不过有了模板,我们实际上是让编译器干了这个活.

	typedef list_iterator<T, T&,T*> iterator;

	typedef list_iterator<T,const T&,const T*>  const_iterator;

	const_iterator begin() const
	{
		return const_iterator(head->next);
	}
	const_iterator end() const
	{
		return const_iterator(head);
	}

再list这个类中,我们再给两个begin,和end的函数重载.
不过它们的返回值就要给const_iterator这个类的匿名对象.

3.其他构造函数,拷贝,赋值运算符重载,析构

它也支持initializer_list的构造.迭代器区间构造.但是它们都面临一个问题,它们要初始化头结点.我们只需要将默认构造那一部分进行封装.

void empty()
{

	head = new Node;
	head->next = head;
	head->prev = head;
	_size = 0;
}

因为list需要进行深拷贝.我们可以先实现list的swap,然后实现拷贝,赋值运算符重载.都可以用现代写法.

void swap(const list<T>& it)
{
	std::swap(head, it.head);
	std::swap(size, it.size);
}
list(const list<T>& it)
{
	empty();
	for (auto& ch : it)
	{
		push_back(ch);
	}
}
list<T>& operator=(list<T> val)
	{
		swap(val);
		return *this;
	}

对于它的析构函数,我们先要实现它的clear函数.clear,函数是清除头结点以外的结点.析构实在clear的基础上再对头节点进行释放.

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

~list()
{
	clear();
	delete head;
	head = nullptr;
	cout << "~list" << endl;
}

4.对于自定义类型的->运算符重载

struct C
{
	int a ;
	int b;
	C(int a = 2,int b = 1)
		:a(a)
		,b(b)
	{
	}
};

假设我们有这么一个类.我们对这个类

	list<C> c;
	c.push_back({ 1,2 });
	c.push_back({ 4,3 });
	c.push_back({ 5,2 });
	auto it = c.begin();
	while (it != c.end())
	{
		//cout << it->a << it->b << " ";
		cout << it.operator->()->a << it.operator->()->b << " ";
		it++;
	}
	cout << endl;

我们要访问struct的成员变量的时候,如果这个类没有实现它的流插入流提取运算符重载.我们需要主动取访问它的内部的变量去间接访问.我们可以提前再迭代器实现->去直接访问它的内部的成员变量.

Ptr operator->()
{
	return &node->data;
}

template <class T ,class Ref,class Ptr>
struct list_iterator
{
	typedef List_Node<T> Node;
	typedef list_iterator<T,Ref,Ptr> self;

再这里也存在const对象的问题.我们仍然需要传一个模板参数.
具体参考代码
https://gitee.com/woodcola/c-learning-code/tree/master/list/list