C++:list- 惊觉

list的介绍及使用

list的介绍

列表可以在任意位置进行插入和删除的操作，且支持双向迭代器
双向列表可以将每个不同位置的元素存储在不同的地址空间，顺序由每个元素地址的前后进行排序

list文档：

https://cplusplus.com/reference/list/list/?kw=list

list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口

list的构造

构造函数（(constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造 list

list 迭代器的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

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

list capacity

函数声明	接口说明
emtpy	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

list的底层结构

list的架构

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

	template <class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

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

		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		bool operator!=(const __list_iterator<T>& it)
		{
			return _node != it._node;
		}
	};

	template <class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator;

		iterator begin()
		{
			return iterator(_head->_next);
		}

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

		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;

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

	private:
		Node *_head;
	};
}

为什么list的Node（节点）为啥要使用struct呢？

因为list的数据是纯POD结构，没有需要特别保护的状态，struct和class的区别就是访问权限（struct默认public，class是private），只有list的迭代器和类会访问list，就不需要对外隐藏

为啥迭代器要单独写成struct呢？

成员节点必须对外可用：

在迭代器中就一个成员函数_node（节点指针），然后靠“operator*”和“operator++”这些来让用户操作。如果写成class并把_node藏进private，那迭代器自己的运算符重载反而访问不了_node，还得写 getter，纯属自找麻烦

本身就是公开工具：

迭代器是给用户用的，begin()使用的就是它，用户能自由的++、*、比较。且没有需要保护的状态，所有的东西本身就要公开，所以用struct最省事

那为啥操作符重载也要写在struct呢？

因为运算符重载写在哪取决于操作符的操作对象是谁，我们现在重载了“*”、“++”、“!=”，这三个都是迭代器使用的，因为迭代器是使用struct，所以要写在struct里面

迭代器

template <class T>
struct __list_iterator
{
	typedef list_node<T> Node;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}

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

	__list_iterator<T>& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	__list_iterator<T> operator++(int)
	{
		__list_iterator<T> tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	__list_iterator<T>& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

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

	bool operator!=(const __list_iterator<T>& it)const
	{
		return _node != it._node;
	}

	bool operator==(const __list_iterator<T>& it)const
	{
		return _node == it._node;
	}
};

const版本迭代器

template <class T>
struct __list_const_iterator
{
	typedef list_node<T> Node;
	Node* _node;

	__list_const_iterator(Node* node)
		:_node(node)
	{}

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

	__list_const_iterator<T>& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	__list_const_iterator<T> operator++(int)
	{
		__list_const_iterator<T> tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	__list_const_iterator<T>& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

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

	bool operator!=(const __list_const_iterator<T>& it)const
	{
		return _node != it._node;
	}

	bool operator==(const __list_const_iterator<T>& it)const
	{
		return _node == it._node;
	}
};

为啥要单独为了const的迭代器呢？

因为iterator的*it返回的是int&，这样用户可以对容器中的数据进行修改，可是我并不想要容器中的数据被修改，因此我们要造一个const版本的迭代器，可是我们发现迭代器里除了operator*的类型是不一样的，其他的代码都是一样的，那么该怎么办呢？

我们可以在模板参数加上Ref，Ref是负责管operator*的，当我们把Ref写上后我们只需要在class list写上

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

改良过后的迭代器

template <class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref> Self;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}

	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)const
	{
		return _node != it._node;
	}

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

虽然已经拿到了it的值，可是并不知道*it的类型是哪个类型，可是要怎么知道*it的类型呢？这里我们必须把元素类型暴露出来

这里我们先拿一个函数进行测试

//测试代码
struct Pos
{
	int _row;
	int _col;

	Pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
};


void test_list2()
{
	List::list<Pos> lt2;
	lt2.push_back({ 1,1 });
	lt2.push_back({ 2,2 });
	lt2.push_back({ 3,3 });
	lt2.push_back({ 4,4 });

	//list<Pos>::iterator it = lt2.begin();
	auto it = lt2.begin();
	while (it != lt2.end())
	{
		cout << *it._row << ":" << *it._col << endl;
		++it;
	}
	cout << endl;
}

这里*it._row和*it._col会报错，因为“.”的优先级比“*”高所以编译器会理解成*（it._row）,可是迭代器并没有_row和_col，所以编译器出现了报错，那要怎么解决呢？

我们可以将_row和_col写成这样

cout << (*it)._row << ":" << (*it)._col << endl;

还有一种写法，可以这样写

cout << it->_row << ":" << it->_col << endl;

为啥要这样写呢？

虽然(*it).row可以使用，但是每次使用的时候都需要一个括号，太麻烦，所以C++允许我们重载“operator->”，让迭代器可以使用“*it->_row”

代码：

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

更规范的写法是在模板参数加上Ptr来写

template <class T,class Ref,class Ptr>

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

链表各个参数的底层逻辑

push_back（尾插）

void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* tail = _head->_prev;

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

insert（指定pos位置插入）

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

	prev->_next = newnode;
	newnode->_next = cur;
	cur->_prev = newnode;
	newnode->_prev = prev;

	++_size;

	return iterator(newnode);

}

erase（指定pos位置删除）

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;


	prev->_next = next;
	next->_prev = prev;
	delete cur;

	--_size;

	return iterator(next);

}

先回看push_back，除了上面的哪个写法我们还有一种写法，我们可以直接调用我们写的insert

push_back(尾插)

void push_back(const T& x)
{
	insert(end(), x);
}

push_front也可以调用insert

Push_front(头插)

void push_front(const T& x)
{
	insert(begin(), x);
}

pop_back和pop_front可以调用erase

pop_back

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

pop_front

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

我们来运行下：

//测试代码
void test_list3()
{
	List::list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	print(lt1);

	lt1.push_front(10);
	lt1.push_front(20);
	print(lt1);

	lt1.pop_back();
	lt1.pop_back();
	print(lt1);

	lt1.pop_front();
	lt1.pop_front();
	print(lt1);
}

运行结果：

析构函数

在写析构函数之前我们还需要一个函数，叫“clear”

clear（清除）

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

继续写析构函数

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

拷贝构造函数

在写拷贝构造函数的时候我们需要把某些功能封装成令一个函数“emtpy_init”

emtpy_init

void emtpy_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

接下来继续来写拷贝构造函数

list(const list<T>& lt)
{
	emtpy_init();

	for (const auto& e : lt)
	{
		push_back(e);
	}
}

为啥还是要写拷贝构造呢？

虽然迭代器不需要手写拷贝构造，因为他的内部就一个指针成员，编译器默认生成的逐字拷贝就足够了
可是链表容器不一样如果我写上“List::list<int> lt2 = lt1;”我需要lt2建立一个独立新的节点，而不是和lt1共用一个节点，否则析构时同一块内存会被delete两次，程序直接崩溃

我们来运行一次

这里还需要写上“operator=”，这里有两种写法

传统写法：

list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for(const auto& e : lt)
		{
			push_back(e);
		}
	}

	return *this;
}

现代写法：

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

当我们写上拷贝构造后就可以解决这个问题了

这里还有一个问题，我们虽然可以拷贝其他的list，可是还不能用花括号进行初始化，在C++11里面有一个类型叫做“initializer_list<valuetype>”，加上它就可以进行花括号初始化

list(initializer_list<T> il)
{
	empty_init();
	for (const auto& e : il)
	{
		push_back(e);
	}
}

测试代码：

void test_list4()
{
	List::list<int> lt1;

	List::list<int> lt3 = { 10,20,30,40,50 };
	lt1 = lt3;
	print(lt1);
}

运行结果：

size（返回数据长度）

这里有两种写法：

写法1：

size_t size()const
{
	size_t n = 0;
	for (auto& e : *this)
	{
		++n;
	}
}

写法2：

我们在链表的成员遍历写上“size_t _size = 0;”

size_t size()const
{
	return _size;
}

我们如果在“insert”和“erase”加上“++size”和“--size”后，会降低获取长度的时间复杂度

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_90184733/article/details/163927837

C++:list