• 【STL】list

    文章目录

    1. list

    列表逻辑上是顺序容器，允许在容器的任何地方进行O(1)的插入和删除操作，并在两个方向上进行迭代。

    list的使用对于现在的我们来说，已经没有什么学习成本了，大家自己看文档就看得懂。

    1.1 list迭代器的思考

    因为链表不是物理上连续的存储空间，所以不能用it < it.end()来迭代。以前vector、string的迭代器就是原生指针，但是list不是了。

    大家想一想list的迭代器解引用是怎么取到数据，++it怎么到下一个节点的位置？这才是我们学习list的重点。

    image-20220712104028052

    1.2 list::sort

    list是支持排序的，但是有大量数据(以10000个数据为分界)要排序的话，不建议用list。

    list的sort不支持快排(std::sort)，因为快排的源码有两个迭代器相减的操作，list的迭代器是不支持的。

    list的迭代器并不能支持随机访问。

    void TestOP()
{
	srand(time(0));
	const int N = 10000000;
	vector v; 
	v.reserve(N);

	list lt1;
	list lt2;

	for (int i = 0; i < N; ++i)
	{
		//v.push_back(rand());
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}
		
	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	for (auto e : lt1)
	{
		v.push_back(e);
	}
    // 快排
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}
	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	printf("vector Sort:%d\n", end1 - begin1);
	printf("list Sort:%d\n", end2 - begin2);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    用list排序还不如把list的数据拷贝给vector，用std::sort排好后再拷回来效率高。

    list1进行如上操作，list2用list::sort排序。测试结果如下:

    image-20220712111411568

    1.3 迭代器分类

    迭代器分为三类:单向、双向、随机迭代器。InputIterator表示只写迭代器，三种类型迭代器它都支持。

    image-20220712110152332

    2. list模拟实现

    2.1 快速搭建list框架

    #pragma once
namespace Yuucho
{
	template
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;

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

	
	template
	class list
	{
		typedef list_node Node;
	public:
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

	private:
		Node* _head;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    2.2 list的迭代器设计

    假设我们认为list的迭代器就是节点的原生指针，那你解引用的话是不支持直接取数据的。节点的指针解引用还是节点，节点的指针++能到下一个节点吗？不能到，节点的物理空间并不连续。那怎么办？

    节点的指针不支持，但是可以间接支持。节点的指针取data就是数据，节点的指针等于next就有了下一个节点的地址。

    因此我们用自定义类型去封装，运算符重载就可以控制行为。OK，搞定。

    我们自己实现就没必要像源码那样复杂，可以简化一下。

    节点不属于迭代器，不需要迭代器释放，所以不需要写析构函数。

    拷贝构造和赋值重载，默认生成的浅拷贝就可以。

    template
struct __list_iterator
{
	typedef list_node Node;
	typedef __list_iterator self;
	Node* _node;
    
	// 通过节点的指针来构造迭代器
	__list_iterator(Node* node)
		:_node(node)
	{}

	// 析构函数  -- 节点不属于迭代器，不需要迭代器释放
	// 拷贝构造和赋值重载 -- 默认生成的浅拷贝就可以

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

    // 支持list存储自定义类型时用->访问数据
    // 做到像指针一样使用
	T* operator->()
	{ 
		//return &(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;
	}

};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    关于->重载的可读性优化：
    image-20220712130449909

    至此，我们就可以在list类中使用迭代器了：

    typedef __list_iterator iterator;

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

iterator end()
{
	return iterator(_head);// end就是哨兵位的头结点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    测试：

    image-20220712122632652

    源码中的迭代器是这样的：

    template
struct __list_iterator
{
    typedef __list_iterator						iterator;
    typedef __list_iterator			consut_iterator;
    typedef __list_iterator					self;
	// ......
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    源码为什么要提供三个模板参数呢？

    我们先来讨论一下consut_iterator和iterator有什么区别。

    假设我们写了一个打印链表的函数:为了减少拷贝我们传引用，防止引用实体被修改我们有加了const。

    void print_list(const list& lt)
{
	list::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    那么此时我们的代码就有问题了，因为const对象不能调用非const的成员函数begin。

    如果我们为const对象提供以下迭代器接口，那会出大问题。

    typedef __list_iterator iterator;

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

iterator end() const
{
	return iterator(_head);// end就是哨兵位的头结点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    const对象返回普通迭代器，那么我的普通迭代器就可读可写了。

    迭代器模仿的是指针的行为，为了让const对象的迭代器在调用解引用*和箭头->时不修改原数据，我们应该这样写。

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

    // 支持list存储自定义类型时用->访问数据
    // 做到像指针一样使用
const T* operator->()
{ 
	//return &(operator*());
	return &_node->_data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    但是如果你直接在迭代器类里面这样改，又会有一个问题。普通对象用什么？

    那为了解决这个问题，很多人的做法是再写一个__list_const_iterator类，支持不能修改迭代器指向节点的数据。这样可以是可以，但是没有很好地做到复用。

    那高手是怎么实现的呢？不就是两个参数吗？

    我们增加两个模板参数来灵活控制这里的参数。

    template
struct __list_iterator
{
	typedef list_node Node;
	typedef __list_iterator self;
	Node* _node;
    
	// 通过节点的指针来构造迭代器
	__list_iterator(Node* node)
		:_node(node)
	{}

	// 析构函数  -- 节点不属于迭代器，不需要迭代器释放
	// 拷贝构造和赋值重载 -- 默认生成的浅拷贝就可以

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

    // 支持list存储自定义类型时用->访问数据
    // 做到像指针一样使用
	Ptr operator->()
	{ 
		//return &(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;
	}

};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    我们就可以在list类中这样使用：

    typedef __list_iterator						iterator;
typedef __list_iterator			const_iterator;

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

const_iterator end()
{
	return const_iterator(_head);// end就是哨兵位的头结点
}

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    至此，我们就很好地提供了list的普通对象和const对象的迭代器。

    2.3 list迭代器使用流程梳理

    紫色代表普通对象，蓝色代表const对象。

    普通对象调用的是普通的begin，普通的begin返回的是普通迭代器，普通迭代器是参数没加const的迭代器类typedef来的，T&和T*传给迭代器类模板，分别应用到了Ref和Ptr的位置。

    const对象调用的是const的begin，const的begin返回的是const迭代器，const迭代器是参数加const的迭代器类typedef来的，const T&和const T*传给迭代器类模板，分别应用到了Ref和Ptr的位置。

    image-20220713102851098

    const_iterator的第一个模板参数不传const T的原因是：

    因为lt调用begin构造迭代器传的是list_node*类型，如果第一个模板参数写成const T，那Node就变成了list_node*类型。此时这两个就是不同的类型了，编译器无法用不同类型的参数来构造迭代器。

    node是list_node*类型，_node是list_node*类型，无法构造。

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

    • 1
    • 2
    • 3

    2.4 push_back

    这里和数据结构链表实现思路是一致的，不多赘述。

    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;

    // 复用insert
	insert(end(), x);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.5 insert

    这里和数据结构链表实现思路是一致的，不多赘述。只是多了新插入节点的返回值。

    // 插入在pos位置之前
iterator insert(iterator pos, const T& x)
{
	Node* newNode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;

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

	return iterator(newNode);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.6 erase

    这里和数据结构链表实现思路是一致的，不多赘述。只是多了新释放节点的后一个节点的返回值。防止迭代器失效。

    iterator erase(iterator pos)
{
	assert(pos != end());

	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

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

	return iterator(next);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.7 push_front, pop_back,pop_front

    复用insert和erase。

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    2.8 析构和clear

    我们先清理掉数据再析构。

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.9 拷贝构造

    链表的深拷贝得一个一个节点拷贝。不是所有的浅拷贝都不好，比如说迭代器类的默认拷贝函数就能让迭代器和源节点的指针一起指向同一块空间(但节点并不属于迭代器)，这正是我们想要的。

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

template 
list(InputIterator first, InputIterator last)
{
	empty_init();

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

// 两个链表交换，交换的是头指针
void swap(list& lt)
{
	std::swap(_head, lt._head);
}

// lt2(lt1) -- 现代写法
list(const list& lt)
{
    // 不能拿随机值交换，不然析构会出问题
	empty_init();
	list tmp(lt.begin(), lt.end());
	swap(tmp);
}

// lt2 = lt1
list& operator=(list lt)
{
	swap(lt);
	return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    3. list迭代器失效问题

    list的insert迭代器不失效，不存在出现野指针或者意义变了的问题。因为它每一个节点相对独立，扩容也是一个一个扩。迭代器指向哪儿就是哪儿。但是为了保持设计统一和支持查找被插入的节点，所以还是用了返回值。

    但是erase的迭代器失效就很明显了。因为迭代器指向的节点被释放了，野指针问题显而易见。所以用被erase的节点的下一个节点作返回值来解决这个问题

  • 相关阅读:
    【内网安全】——windows信息收集
    项目管理：敏捷开发之十大误区
    今天是七夕，来看看程序员的土味情话。
    深度清理mac磁盘空间的方法，方方面面都清理干净
    Vue 组件的全局注册与组件的jsx实现方法
    JS删除对象的某个属性
    Java设计模式 | 基于订单批量支付场景，对策略模式和简单工厂模式进行简单实现
    基于LinuxC语言实现的TCP多线程/进程服务器
    蓝桥杯（路径 动态规划 C++）
    Packet Tracer - 研究 DUAL FSM
  • 原文地址：https://blog.csdn.net/iwkxi/article/details/126593502