list及其模拟实现

发布于：2025-03-17 ⋅ 阅读:(15) ⋅ 点赞:(0)

list其实就是一个带头双向链表

1 迭代器

按功能分
iterator
reverse_iterator
const_iterator
const_reverse_iterator
按性质分 支持结构 支持操作
单向 forward_list/unordered_map ++
双向 list/map/set ++/--
随机 vector/string/deque ++ / -- / + / -

按性质分，决定可以使用那些算法。支持单向的算法，也支持双向和随机，反之不然。

2 list的使用

2.1 list的构造

构造函数（(constructor)） 接口说明

list(size_type n,

const value_type& val = value_type())

 构造的list包含n个值为val的元素
list() 构造空的list
list(const list& x) 拷贝构造函数
list(InputIterator frist,InputIterator last) 用[frist,last)区间中的元素构造list 
void test_list1()
{
	list<int> l1;
	list<int> l2(4, 10);
	list<int> l3(l2);
	list<int> l4(++l2.begin(), --l2.end());
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l2)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l4)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	test_list1();
}

2.2 list的迭代器

函数声明 接口说明

begin

 返回第一个元素的迭代器（头节点的下一个）

end

 返回最后一个元素下一个的位置（头结点）

rbegin

 返回第一个元素的reverse_iterator，及end的位置

rend

 返回最后一个元素下一个位置的reverse_iterator，及begin的位置 
void PrintList(const list<int>& l)
{
	list<int>::const_iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;//迭代器支持++
	}
	cout << endl;
}

void test_list2()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(int));
	PrintList(lt);
	auto it = lt.rbegin();
	while (it != lt.rend())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

2.3 list的增删查改

函数说明 接口说明

empty

 检测list是否为空，是返回ture，否则返回false

size

 返回list中有效节点的个数
front 返回list的第一个节点中值的引用

back

 返回list的最后一个节点中值的引用

push_front

 在list首元素前插入值为val的元素

pop_front

 删除list中的第一个元素

emplace_front 

 和push_front类似

push_back

 在尾部插入值为val的元素

pop_back

 删除list中最后一个元素

emplace_back 

 和push_back类似（有些情况比push_back高效）
insert 在list position 位置中插入值为val的元素

erase

 删除list position 位置的元素（可以返回迭代器）

swap

 交换两个list中的元素

resize

 调整list的大小，包含n个元素

clear

 清空list中的有效元素 
void test_list3()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	PrintList(lt);

	lt.push_front(5);
	PrintList(lt);

	lt.pop_back();
	lt.pop_front();
	PrintList(lt);

	list<int> lt2;
	lt2.push_back(1);
	lt2.push_back(2);
	lt2.push_back(3);
	lt2.push_back(4);
	lt2.push_back(5);
	lt2.insert(lt2.begin(), 10);
	PrintList(lt2);

	lt2.erase(--lt2.end());
	PrintList(lt2);

}

struct A
{
	A(int a1 = 1,int a2 = 1)
		:_a1(a1)
		,_a2(a2)
	{
		cout << "A(int a1 = 1,int a2 = 1)" << endl;
	}

	A(const A& aa)
	{
		_a1 = aa._a1;
		_a2 = aa._a2;
		cout << "A(const A& aa)" << endl;
	}

	int _a1;
	int _a2;
};

void test_list4()
{
	list<A> lt;

	A aa(1, 1);
	lt.push_back(aa);
	lt.push_back(A(2, 2));//创建一个临时对象
	//lt.push_back(3, 3);

	lt.emplace_back(aa);
	lt.emplace_back(A(2, 2));
	lt.emplace_back(3, 3);//使用 3 和 3 作为参数调用 A 的构造函数,避免了拷贝构造
}

2.4 list Operations

函数说明 接口说明

splice

能够把一个std::list中的元素（可以是单个元素、一段连续元素或者全部元素）移动到另一个std::list的指定位置。

remove

 删除给定值的元素

unique

 删除重复值(前提是有序)

merge

 合并有序列表

sort

 对容器中的元素进行排序

reverse

 反转元素的顺序 
void test_list5()
{
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

	it = mylist1.begin();
	++it;                         // points to 2

	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
								  // mylist2 (empty)  mylist2为空
								  // "it" still points to 2 (the 5th element)

	PrintList(mylist1);

	list<int> lt;
	for (int i = 1; i <= 6; ++i)
		lt.push_back(i);

	//把x之后的值翻转
	int x;
	cin >> x;
	it = find(lt.begin(), lt.end(), x);
	if (it != lt.end())
	{
		auto next_it = next(it);//当x是第一个元素时，移动范围从第二个元素开始，防止整个链表被移动，确保哨兵节点指针正确。
		lt.splice(lt.begin(), lt, next_it, lt.end());
	}
	PrintList(lt);

	//删除x
	lt.remove(x);
	PrintList(lt);

}

void test_list6()
{
	list<int> first, second;
	first.push_back(2);
	first.push_back(4);
	first.push_back(6);
	second.push_back(1);
	second.push_back(3);
	second.push_back(5);

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

	first.merge(second);
	PrintList(first);

	list<int> lt;
	lt.push_back(5);
	lt.push_back(10);
	lt.push_back(5);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(12);

	lt.sort();
	lt.unique();
	PrintList(lt);
}

3 list的模拟实现

3.1 list的节点

template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& data = T())//构造函数
			:_data(data)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

3.2 list的迭代器

iterator：

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

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

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

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

		list_iterator operator++()
		{
			_node = _node->_next;
			return *this;
		}

		list_iterator operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		list_iterator operator++(int)//后置++：必须添加一个 无实际用途的 int 类型占位参数
		{
			list_iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		list_iterator operator--(int)//后置--
		{
			list_iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const list_iterator& lt) const
		{
			return _node != lt._node;
		}

		bool operator==(const list_iterator& lt) const
		{
			return _node == lt._node;
		}
	};

const_iterator：

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

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

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

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

		list_iterator operator++()
		{
			_node = _node->_next;
			return *this;
		}

		list_iterator operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		list_iterator operator++(int)//后置++：必须添加一个 无实际用途的 int 类型占位参数
		{
			list_iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		list_iterator operator--(int)//后置--
		{
			list_iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const list_iterator& lt) const
		{
			return _node != lt._node;
		}

		bool operator==(const list_iterator& lt) const
		{
			return _node == lt._node;
		}
	};

这两个迭代器只有重载operator*和operator->时有差异所以可以写成一下写法

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 operator*()
		{
			return _node->_data;
		}

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

		Self operator++()//前置++
		{
			_node = _node->_next;
			return *this;
		}

		Self operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator++(int)//后置++：必须添加一个 无实际用途的 int 类型占位参数
		{
			list_iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Self operator--(int)//后置--
		{
			list_iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const list_iterator& lt) const
		{
			return _node != lt._node;
		}

		bool operator==(const list_iterator& lt) const
		{
			return _node == lt._node;
		}
	};

const iterator 是迭代器本身不能改变

const_iterator 是指向的内容不能改变

    struct AA
	{
		int _a1 = 1;
		int _a2 = 1;
	};

    template<class Container>
	void PrintContainer(const Container& con)
	{
		typename Container::const_iterator it = con.begin();
		//auto it = con.begin();
		for (auto& e : con)
		{
			cout << e << " ";
		}
		cout << endl;
	}

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

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		list<AA> la;
		la.push_back(AA());
		la.push_back(AA());
		la.push_back(AA());
		la.push_back(AA());

		list<AA>::iterator ait = la.begin();
		while (ait != la.end())
		{
			cout << ait->_a1 << ":" << ait->_a2 << endl;
			//特殊处理，本来是两个->才合理，为了可读性省略了一个
			//cout << ait.operator->()->_a1 << ait.operator->()->_a2 << endl;
			++ait;
		}
		cout << endl;
	}

3.2 list

template<class T>
	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()
		{
			/*iterator it(_head->_next);
			return it;*/

			//return iterator(_head->_next);//

			return _head->_next;//单参数构造函数支持隐式类型转换
		}

		iterator end()
		{
			return _head;
		}

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

		const_iterator end() const
		{
			return _head;
		}

		list()
		{
			empty_init();
		}

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

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

		//l1(l2)
		list(const list<T>& lt)
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

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

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

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

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

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

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

			_size++;

			return newnode;
		}

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

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

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

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;

			_size--;

			return next;
		}

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

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

		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}
	private:
		Node* _head;
		size_t _size;
	};

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

		list<int>::iterator it = lt.begin();
		lt.insert(it, 10);
		*it += 100;
		PrintContainer(lt);

		it = lt.begin();
		while (it != lt.end())
		{
			if (*it % 2 == 0)
			{
				it = lt.erase(it);
			}
			else
			{
				it++;
			}
		}
		PrintContainer(lt);
	}

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

		list<int> lt2(lt);
		PrintContainer(lt);
		PrintContainer(lt2);

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

		lt = lt3;
		PrintContainer(lt);

		PrintContainer(lt3);
	}

	void func(const list<int>& lt)
	{
		PrintContainer(lt);
	}

	void test_list4()
	{
		//直接构造
		list<int> lt0({ 1,2,3,4,5,6 });
		
		//隐式类型转换
		list<int> lt1 = { 1,2,3,4,5,6,7,8 };
		const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };

		func(lt0);
		func({ 1,2,3,4,5,6 });
		PrintContainer(lt3);

	}

4 list和vector的比较

vector list
底层结构 动态顺序表，一段连续的空间 带头节点的双向链表
随机访问 支持随机访问，访问某个元素的效率O(1) 不支持随机访问，访问某个元素效率O(N)

插入和删除
任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N) ，插入时有可能需要增容。
增容：开辟新空间，拷贝元素，释放旧空间，导致效率更
低
任意位置插入和删除效率高，
不需要搬移元素，时间复杂度
为 O(1)
空间利用率 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器 原生态指针 对愿生态节点进行封装
迭代器失效 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，导致原来的迭代器失效，删除时，当迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景 需要高效存储，支持随机访问，不关心插入删除效率 大量插入删除操作，不关心随机访问

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布