list模拟实现 伪代码

知识点

节点

template<class T>
struct list_node //这是一个通用节点模板,所以名字还用list_node,方便不同容器共享节点结构,在容器内可以改别名Node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _data;

	list_node(const T& x = T())  //如果调用构造函数时不传参,就自动调用T类型的默认构造函数生成一个默认值
		:_next(nullptr), _prev(nullptr), _data(x)
	{}
};

正向迭代器

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; }  //_node->_data是实际值,引用它即访问它,可做左值
	Ptr operator->() { return &_node->_data; } //返回node的data的地址,&取值

	Self& operator++()
	{
		_node = _node->_next;
		return *this; //this是Self*,*this是Self&
	}

	Self operator++(int) //后置版本it++
	{
		Self tmp(*this); //用当前对象构造新Self
		_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 //比较两个迭代器内部的节点指针是否指向同一个位置
	{
		/*if (it->data == *this->data)
		{
			return true;
		}
		else 
			return false;*/
		return _node != it._node;
	}

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

反向迭代器

template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

	Iterator _it; //反向迭代器内部的_it实际上是正向迭代器中 当前位置的下一个元素

	Reverse_iterator(Iterator it) :_it(it) {}

	Ref operator*() 
	{
		Iterator tmp = _it; //规定_it指向的是最后一个元素的后一个位置
		return *--tmp;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp = _it;
		--_it;
		return *tmp;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	Self operator--(int)
	{
		Self tmp = _it;
		++_it;
		return *tmp;
	}

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

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

包装的正向迭代器

  • 其中,_it 其实是一个正向迭代器

为什么?

真正“传入”的时机是你用它时!

比如这样:

bit::list<int>::iterator it = lst.end();
bit::Reverse_iterator<bit::list<int>::iterator, int&, int*> rit(it);

这一句就做了这些事:

模板参数名 实际传入值 含义
Iterator bit::list<int>::iterator 正向迭代器类型
Ref int& 解引用操作返回引用
Ptr int* -> 操作返回指针类型

bit::list<int>::iterator

第一层:class listtypedef list_iterator<T, T&, T*> iterator

第二层:struct list_iteratortypedef list_iterator<T, Ref, Ptr> Self;

所以:

  • 之后 *rit 实际调用的是 int& operator*(),而 *--tmp 最终是你自己的 list_iteratoroperator*() 返回的引用

正向反向遍历逻辑一致

位置 正向迭代器值 反向迭代器内部 _it 应该是
rbegin() 指向 30 _it = v.end()
rend() 超出左边界 _it = v.begin()

题目

1. 下面有关 vector 和 list 的区别,描述正确的是:

  • A. 两者在尾部插入的效率一样高 ❌ 错误

vector 在尾部插入通常是 摊还 O(1),但可能因 扩容而移动整个数组,所以不是绝对高效。

list 在尾部插入是 O(1),不会移动元素。

👉 所以虽然通常效率都高,但不能说“一样高”。

  • B. 两者在头部插入的效率一样高 ❌ 错误

vector 在头部插入是 O(n),因为要搬动所有元素。

list 在头部插入是 O(1),只改链指针。

👉 所以效率差距很大,不一样高。

  • C. 两者都提供了 push_back 和 push_front 方法 ❌ 错误

list:✅ 提供 push_back() 和 push_front()

vector:✅ 有 push_back(),❌ 没有 push_front()

👉 所以这个选项错误。

  • D. 两者都提供了迭代器,且迭代器都支持随机访问 ❌ 错误

vector 的迭代器是 随机访问迭代器 ✅

list 的迭代器是 双向迭代器 ❌,不支持随机访问(不能 +n、[])

2. 以下程序输出结果为( )

int main()
{
	int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };
	int n = sizeof(ar) / sizeof(int);
	list<int> mylist(ar, ar+n); 
	list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);
	reverse(mylist.begin(), pos);
	reverse(pos, mylist.end());
	list<int>::const_reverse_iterator crit = mylist.crbegin();
	while(crit != mylist.crend())
	{
		cout<<*crit<<" ";
		++crit;
	}
	cout<<endl;
}
  • reverse() 是左闭右开

完整代码

list.h

#pragma once

#include<assert.h>

//class list {
//public:
//
//private:
//
//}; //不能直接以这个结构开始,要命名空间以及使用模板类

namespace zoya {
	template<class T>
	struct list_node //这是一个通用节点模板,所以名字还用list_node,方便不同容器共享节点结构,在容器内可以改别名Node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		list_node(const T& x = T())  //如果调用构造函数时不传参,就自动调用T类型的默认构造函数生成一个默认值
			:_next(nullptr), _prev(nullptr), _data(x)
		{}
	};

	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; }  //_node->_data是实际值,引用它即访问它,可做左值
		Ptr operator->() { return &_node->_data; } //返回node的data的地址,&取值

		Self& operator++()
		{
			_node = _node->_next;
			return *this; //this是Self*,*this是Self&
		}

		Self operator++(int) //后置版本it++
		{
			Self tmp(*this); //用当前对象构造新Self
			_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 //比较两个迭代器内部的节点指针是否指向同一个位置
		{
			/*if (it->data == *this->data)
			{
				return true;
			}
			else 
				return false;*/
			return _node != it._node;
		}

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

	template<class Iterator,class Ref,class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

		Iterator _it; //反向迭代器内部的_it实际上是正向迭代器中 当前位置的下一个元素

		Reverse_iterator(Iterator it) :_it(it) {}

		Ref operator*() 
		{
			Iterator tmp = _it; //规定_it指向的是最后一个元素的后一个位置
			return *--tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp = _it;
			--_it;
			return *tmp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp = _it;
			++_it;
			return *tmp;
		}

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

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

	template<class T>
	class list
	{
		typedef list_node<T> Node;  //默认为private,辅助性内部别名,低关注度
	public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;


		list()
		{
			empty_init();
		}

		list(std::initializer_list<T> lt) //{1, 2, 3, 4} 这种语法,在 C++11 中被设计为会被自动转换为一个 std::initializer_list<int> 类型的对象。
		{
			empty_init();
			for (const auto& e : lt)
			{
				push_back(e);
			}

		}

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

		list<T>& operator=(list<T> lt) //如果用list<T>& lt,就不能进行swap(),因不能修改const引用。本质上不是交换,不用考虑本引用的list本身
		{
			swap(lt);
			return *this; //返回被赋值的本身
		}

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

		iterator begin() { return iterator(_head->_next); }
		iterator end() { return iterator(_head); } //循环双向链表,所以到head表示整个链表都遍历完了

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

		reverse_iterator rbegin() { return reverse_iterator(end()); }
		reverse_iterator rend() { return reverse_iterator(begin()); }

		const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
		const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

		size_t size() const { return _size; }

		bool empty() const { return _size == 0; }

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

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

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

		void 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;
		}

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

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

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

			delete cur;
			--_size;

			return iterator(next);
		}

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

	private:
		void empty_init()
		{
			//_head = NULL;
			_head = new Node;  //堆上分配的这块内存的指针
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		Node* _head;
		size_t _size;
	};
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
#include <ctime>
#include "list.h"
using namespace std;

void test_list1()
{
	list<int> lt1 = { 1,2,3,4 };

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;

	list<int> lt2 = { 10,2,30,5 };
	for (auto e : lt2)
		cout << e << " ";
	cout << endl;
}

void test_list2()
{
	list<int> lt1 = { 1,2,3,4 };
	lt1.assign(2, 1); //清空lt,放入2个1

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

struct A //带默认参数的构造函数
{
	A(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {} //直接初始化列表,直接调用有参构造,不用再调用默认构造
	int _a1;
	int _a2;
};

ostream& operator<<(ostream& os, const A& a) {
	os << "(" << a._a1 << ", " << a._a2 << ")";
	return os;
}

void test_list3()
{
	list<A> lt1;
	lt1.push_back(A(2, 2));

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;

	lt1.emplace_back(2, 2);

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

void test_list4()
{
	list<int> lt1 = { 10,2,30,5,2,4,2 };

	lt1.remove(100);
	lt1.remove(5);
	lt1.remove(2);

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

void test_list5()
{
	list<int> lt1 = { 10,2,30,5,2,4,2 };
	lt1.sort();

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;

	lt1.sort(greater<int>()); //从大到小排序

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

void test_list6()
{
	list<int> lt1 = { 10,2,30,5,2,5,5,2,4,2 };
	lt1.sort();
	lt1.unique(); //只移除相邻且相等的元素,保留第一个。因unique() 不会自动排序,所以通常要先调用 sort()

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

void test_list7()
{
	list<int> lt1 = { 1,2,3,4,5,6 };
	lt1.splice(lt1.end(), lt1, lt1.begin());

	for (auto e : lt1)
		cout << e << " ";
	cout << endl;
}

void test_op1()
{
	srand(time(0));
	const int N = 1000000;
	vector<int> v;
	list<int> lt1;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i; //rand()生成的随机数范围有限,有时会重复,加上i尽量保证每个元素至少不完全相同
		v.push_back(e);
		lt1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort(); //std::list的迭代器是双向迭代器,不支持随机访问,但std::sort要求随机访问迭代器,list无法直接用std::sort,所以用自身的成员函数sort()。
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1); //vector sort:341  
	printf("list sort:%d\n", end2 - begin2); //list sort : 564
}

void test_op2()
{
	srand(time(0));
	const int N = 1000;
	list<int> lt1, lt2;
	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	vector<int> v(lt2.begin(), lt2.end());
	sort(v.begin(), v.end());
	lt2.assign(v.begin(), v.end()); //把vector中的元素复制覆盖到list中
	int end1 = clock();

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

	printf("list copy to vector and sort and copy to list:%d\n", end1 - begin1); //1
	printf("list sort:%d\n", end2 - begin2); //0
}

void test_zoyalist1()
{
	zoya::list<int> lt1 = { 1,2,3,4 };

	for (auto it = lt1.begin(); it != lt1.end(); ++it)
	{
		*it += 1;
		cout << *it << " ";
	}
	cout << endl;
}

void Print(const zoya::list<int>& lt)
{
	zoya::list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

void test_zotalist2()
{
	zoya::list<A> lt1;
	lt1.push_back({ 1,1 });
	lt1.push_back({ 2,2 });
	lt1.push_back({ 3,3 });
	lt1.push_back({ 4,4 });

	for (auto it = lt1.begin(); it != lt1.end(); ++it)
		cout << it->_a1 << ":" << it->_a2 << endl;

	zoya::list<int> lt2 = { 1,2,3,4 };
	Print(lt2);
}

void test_zoyalist3()
{
	zoya::list<int> lt1 = {1, 2, 3, 4};
	for (auto it = lt1.rbegin(); it != lt1.rend(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	//test_list2();
	//test_list3();
	//test_list4();
	//test_list5();
	//test_list6();
	//test_list7();
	//test_op1();
	//test_op2();

	//test_zoyalist1();
	//test_zotalist2();
	test_zoyalist3();

	return 0;
}
全部评论

相关推荐

前端学习交流
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务