有趣的地方

有趣的地方

list使用与模拟实现

目录

list使用

reverse

sort

 unique

splice

list模拟实现

类与成员函数声明

节点类型的定义

非const迭代器的实现

list成员函数

构造函数

尾插

头插

头删

尾删

任意位置插入

 任意位置删除

清空数据

析构函数

拷贝构造函数

赋值重载函数

const迭代器的设计

终极版迭代器的实现

迭代器扩充小知识


list使用

list的诸多使用与前面博客讲解的string仍然类似,我们此处只讲解比较特殊的接口函数

list的底层是带头双向循环链表,在我的数据结构专栏博客 带头双向循环链表_CSDN博客 已经讲解过了,重点是体会带头双向循环链表与顺序表的不同,尤其是某个位置插入与删除数据的效率!

reverse

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto e : lt)
	{
		cout << e << " "; //1 2 3 4 
	}
	cout << endl;

	lt.reverse(); //逆置链表

	for (auto e : lt)
	{
		cout << e << " "; //4 3 2 1 
	}
	cout << endl;
}

sort

void test_list2()
{
	list<int> lt;
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(1);

	for (auto e : lt)
	{
		cout << e << " "; //2 3 4 1 
	}
	cout << endl;

	//默认是升序 < less
	//lt.sort(); 

	//降序: > greater
	greater<int> gt;
	lt.sort(gt);

	lt.sort(greater<int>()); //匿名对象

	for (auto e : lt)
	{
		cout << e << " "; //4 3 2 1
	}
	cout << endl;
}

注意: list的排序无法使用算法库中的sort,主要原因是list不支持随机访问的迭代器

迭代器类型按性质或者底层实现分为三种:

1.单向:只支持++, 单链表/哈希表
2.双向:++与--都支持,双向链表/红黑树(map和set)
3.随机:++/--/+/- vector/string/deque

注意: 2是兼容1的,3是兼容2的(本质是继承关系)

 unique

void test_list3()
{
	list<int> lt;
	lt.push_back(4);
	lt.push_back(1);
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(5);
	lt.push_back(5);
	lt.push_back(3);

	for (auto e : lt)
	{
		cout << e << " "; //4 1 1 2 5 5 3
	}
	cout << endl;

	lt.sort();
	lt.unique(); //把相邻的重复去掉, 配合sort可以达到去重的功能

	for (auto e : lt)
	{
		cout << e << " "; //1 2 3 4 5
	}
	cout << endl;
}

splice

void test_list5()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);

	list<int>::iterator it = lt1.begin();
	++it;
	lt1.splice(it, lt2); //将lt2嫁接到lt1第2个位置之后, lt2就为空了!
	for (auto e : lt1)
	{
		cout << e << " "; //1 10 20 30 40 2 3 4
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " "; //空
	}
	cout << endl;
}
void test_list5()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);

	lt1.splice(lt1.begin(), lt2, lt2.begin()); //将lt2的第一个节点接到lt1开始
	
	for (auto e : lt1)
	{
		cout << e << " "; //10 1 2 3 4 
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " "; //20 30 40
	}
	cout << endl;
}
void test_list5()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);

	lt1.splice(lt1.begin(), lt2, lt2.begin(), lt2.end()); //将lt2的全部接到lt1开始

	for (auto e : lt1)
	{
		cout << e << " "; //10 20 30 40 1 2 3 4
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " "; //空
	}
	cout << endl;
}

list模拟实现

关于带头双向链表的结构与实现可以直接看我之前的博客: 带头双向循环链表-CSDN博客

类与成员函数声明

namespace dck
{
	//每个节点的类型
	template <class T>
	struct list_node
	{
		T _data; //数据域
		list_node<T>* _next; //前驱指针
		list_node<T>* _prev; //后继指针
		list_node(const T& x = T()); //构造函数
	};

	//非const迭代器
	template <class T>
	struct __list_iterator //前加_表示内部的实现
	{
		typedef list_node<T> Node;
		Node* _node;

		//构造函数
		__list_iterator(Node* node);

		//迭代器++(前置++)
		typedef __list_iterator<T> self;
		self& operator++();
		//迭代器--(前置--)
		self& operator--();
		//迭代器++(后置++)
		self operator++(int);
		//迭代器--(后置--)
		self operator--(int);

		//迭代器解引用
		T& operator*();
		T* operator->();

		//两个迭代器进行比较
		bool operator!=(const self& s);
		bool operator ==(const self& s);
	};

	//list的类型
	template <class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		void empty_init(); //空初始化
		list(); //构造函数
		void push_back(const T& x); //尾插
		void push_front(const T& x); //头插
		void pop_front(); //头删
		void pop_back(); //尾删
		iterator insert(iterator pos, const T& x); //任意位置插入
		iterator erase(iterator pos); //任意位置删除
		iterator begin(); //起始位置迭代器
		iterator end(); //结束位置迭代器
		void clear(); //清空数据
		~list(); //析构函数
		list(const list<T>& lt); //拷贝构造函数
		list<T>& operator=(const list<T>& lt); //赋值重载函数传统写法
		void swap(list<T>& lt); //交换两个list, 赋值重载函数现代写法要调用swap函数
		list<T>& operator=(list<T> lt); //赋值重载函数现代写法

	private:
		Node* _head;
        size_t size; //记录链表中节点的个数,降低时间复杂度
	};
}

节点类型的定义

//每个节点的类型
template <class T>
struct list_node
{
	T _data;
	list_node<T>* _next;
	list_node<T>* _prev;

	list_node(const T& x = T()) 
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

非const迭代器的实现

之前讲解的string与vector的迭代器都是原生指针,而list的迭代器不是原生指针,主要原因是因为list的底层是双向链表,如果用原生指针++,是无法到下一个节点的;直接解引用拿到的也不是具体的数据,而是整个节点对象;而迭代器的访问与遍历方式都是类似的,都是++, 解引用,判断!=, 所以我们只需要把list的迭代器设计成类,在类中对原生指针做封装

//迭代器的实现 --- 封装屏蔽了底层差异和细节,提供了统一的访问遍历修改方式!
template <class T>
struct __list_iterator //前加_表示内部的实现
{
	typedef list_node<T> Node;
	Node* _node;

	//构造函数
	__list_iterator(Node* node)
		:_node(node)
	{}

	//迭代器++(前置++)
	typedef __list_iterator<T> self;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//迭代器--(前置--)
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//迭代器++(后置++)
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	//迭代器--(后置--)
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	//迭代器解引用
	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	//两个迭代器进行比较
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

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

注意: 当list中存放的是自定义类型的对象时,使用->解引用时,写法如下:

class AA
{
public:
	AA(int aa1 = 1, int aa2 = 1)
		:_a1(aa1)
		,_a2(aa2)
	{}
		
	int _a1;
	int _a2;
};

void test_list()
{
	list<AA> lt1;
	lt1.push_back(AA(1, 2));
	lt1.push_back(AA(3, 4));
	lt1.push_back(AA(5, 6));
	list<AA>::iterator it = lt1.begin();
	while (it != lt1.end())
	{
		//显式应该这么写,因为operator->()拿到的是原生指针,还要再次->解引用拿到数据
		cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;
		//本来应该 it->->_a1, 但是可读性不好,因此编译器特殊处理, 省略了一个->
		cout << it->_a1 << " " << it->_a2 << endl;
		++it;
	}
	cout << endl;
}

list成员函数

构造函数
//空初始化, 后续代码可能会用到,因此单独写出来
void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

//构造函数
list()
{
	empty_init();
}
尾插
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;
	//_size++;

    //调用insert函数
	insert(end(), x); 
}
头插
//头插
void push_front(const T& x)
{
	insert(begin(), x);
}
头删
//头删
void pop_front()
{
	erase(begin());
}
尾删
//尾删
void pop_back()
{
	erase(--end());
}
任意位置插入
//insert
//在pos位置之前插入
//list的迭代器不存在失效的问题,因为不涉及扩容
//参考库的实现,还是给insert带上返回值
iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node; //当前节点指针
	Node* prev = cur->_prev; //前一个节点指针
	Node* newnode = new Node(x); //开辟新节点

	//链接
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	++_size;
	return iterator(newnode); //返回新插入节点位置的迭代器
}
 任意位置删除
//erase之后,迭代器pos失效,因为当前节点已经被释放了!
//因此我们给erase带上返回值
iterator erase(iterator pos)
{
	Node* cur = pos._node; //当前节点指针
	Node* prev = cur->_prev; //前一个节点指针
	Node* next = cur->_next; //后一个节点指针

	delete cur; //释放当前节点

	//链接前一个节点和后一个节点
	prev->_next = next; 
	next->_prev = prev;

	--_size;
	return iterator(next); //返回释放节点的下一个位置
}

迭代器接口

iterator begin()
{
	//return iterator(_head->_next);
	return _head->_next;  //单参数的构造函数支持隐式类型转化
}

iterator end()
{
	//return iterator(_head);
	return _head;  //单参数的构造函数支持隐式类型转化
}
清空数据
//清空数据(不清除带哨兵位的头节点)
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
析构函数
//析构函数
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
拷贝构造函数
//拷贝构造
list(list<T>& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);
	}
}
赋值重载函数

传统写法

//赋值重载传统写法
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear(); 
		for (auto e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}

现代写法

//赋值重载现代写法
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

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

const迭代器的设计

上述代码实现了非const迭代器,本质就是封装了一个类,提供了对应的接口,而const迭代器本质就是迭代器指向的内容不可修改,因此不可以直接写const iterator,  这个const修饰的是迭代器本身不能被修改,那迭代器如何++访问数据呢?? 因此非const迭代器应该是一个独立的类

//非const迭代器
template <class T>
struct __list_const_iterator //前加_表示内部的实现
{
	typedef list_node<T> Node;
	Node* _node;

	//构造函数
	__list_const_iterator(Node* node)
		:_node(node)
	{}

	//迭代器++(前置++)
	typedef __list_const_iterator<T> self;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//迭代器--(前置--)
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//迭代器++(后置++)
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	//迭代器--(后置--)
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	//迭代器解引用
	const T& operator*() const
	{
		return _node->_data;
	}

	const T* operator->() const
	{
		return &_node->_data;
	}

	//两个迭代器进行比较
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

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

list类中提供const迭代器的begin和end接口即可:

//list的类型
template <class T>
class list
{
	typedef list_node<T> Node;
public:
	//提供迭代器
	typedef __list_iterator<T> iterator;
	typedef __list_const_iterator<T> const_iterator;

	const_iterator begin() const
	{
		//return iterator(_head->_next);
		return _head->_next;  //单参数的构造函数支持隐式类型转化
	}

	const_iterator end() const
	{
		//return iterator(_head);
		return _head;  //单参数的构造函数支持隐式类型转化
	}
};

但是上面的写法太冗余了,非const迭代器和const迭代器都是封装了类,类中的实现大同小异,参考了STL库中的实现以后,其实只需要一个类+增加模板参数即可,  实现如下:

终极版迭代器的实现

//迭代器
template <class T, class Ref, class Ptr>
struct __list_iterator //前加_表示内部的实现
{
	typedef list_node<T> Node;
	Node* _node;

	typedef __list_iterator<T, Ref, Ptr> self;

	//构造函数
	__list_iterator(Node* node)
		:_node(node)
	{}

	//迭代器++(前置++)
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//迭代器--(前置--)
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//迭代器++(后置++)
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	//迭代器--(后置--)
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	//迭代器解引用
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	//两个迭代器进行比较
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

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

list类:

template <class T>
//list的类型
class list
{
	typedef list_node<T> Node;
public:
	//提供迭代器
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		return iterator(_head->_next);
		return _head->_next;  //单参数的构造函数支持隐式类型转化
	}

	iterator end()
	{
		return iterator(_head);
		return _head;  //单参数的构造函数支持隐式类型转化
	}

	const_iterator begin() const
	{
		//return iterator(_head->_next);
		return _head->_next;  //单参数的构造函数支持隐式类型转化
	}

	const_iterator end() const
	{
		//return iterator(_head);
		return _head;  //单参数的构造函数支持隐式类型转化
	}
};

迭代器扩充小知识

场景1:想实现一个打印函数,  无论list的节点是什么类型都能打印

template <class T>
void Print(const list<T>& lt)
{
	//list<T>为未实例化的类模板,编译器不能直接去他里面去找
	//编译器无法识别list<T>::const_iterator是内嵌类型还是静态成员变量
	//前面加一个typename就是告诉编译器,这里是一个类型,等list<T>实例化再去类里面去取
	typename list<T>::const_iterator it = lt.begin(); 
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

void test_list5()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	Print(lt1);

	//list不会存在浅拷贝的问题,因为不涉及扩容
	list<string> lt2;
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	Print(lt2);
}

场景2:想实现一个打印函数, 无论是哪个STL,都能使用同一个打印函数

//模板(泛型编程)本质: 本来应该由我们做的事情交给编译器去做了!
template <typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

void test_list5()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	print_container(lt1);

	//list不会存在浅拷贝的问题,因为不涉及扩容
	list<string> lt2;
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	lt2.push_back("1111111111111111");
	print_container(lt2);

	vector<string> v;
	v.push_back("2222222222222222");
	v.push_back("2222222222222222");
	v.push_back("2222222222222222");
	v.push_back("2222222222222222");
	v.push_back("2222222222222222");
	print_container(v);
}

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图