C++ 简单模拟实现 STL 中的 list 与 queue

  • 开发
  • 31

目录

一，list

1， list 的节点与迭代器

2，list 的数据结构、一些简单的功能、构造函数

3，list 的对元素操作

4，C++ 11 的一些功能

5，完整代码：

二，queue

一，list

std::list 是 C++ 标准模板库 (STL) 中提供的一个容器模板，它被实现为环状双向链表。list 和 vector 是两个最常被使用的容器。相较于 vector 的连续线性空间，list 的非连续存储就显得复杂许多，它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，list 对空间的使用一点也不浪费。而且，对于任何位置的插入或移除元素，list 永远是常数时间。

关于 list 的各种接口的用法这里就不介绍了，此文主要是模拟实现。
 

1， list 的节点与迭代器

list 本身和 list 的节点是不同的结构，是需要分开设计的。list 中会包含 list 节点结构。节点结构：

template<class T>
struct list_node {
	list_node<T>* next, * pre;	// next 指向下一个节点，pre 指向前一个节点
	T data;
	list_node(const T& data_ = T())
		:next(nullptr),pre(nullptr),data(data_){}
};

如果不清楚迭代器是什么或者是不清楚要怎么设计一个容器专属的迭代器可以看看这个：C++ 迭代器与反向迭代器-CSDN博客

如果对 vector 的实现细节感兴趣可以看看这个：C++ 简单模拟实现 STL 中的 vector 与 stack-CSDN博客

list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。所以 list 迭代器必须有能力指向 list 的节点，并且能够进行正确的递增（++）、递减（--）、取值（*）、成员存取（->）等操作。这里要注意，取值时取的是节点的数据值，不是节点本身，成员取用时取用的是节点的成员。例如：

mySTL::list<int> lt = { 1,2,3,4,5 };
for (auto it = lt.begin();it != lt.end();++it) {
	cout << *it << " ";    // 输出的是 1 2 3 4 5;
}
mySTL::list<pair<int, int>> lt2 = { {1,2},{3,4},{5,6} };
for (auto it = lt2.begin();it != lt2.end();++it) {
	cout << it->first << "," << it->second << " # ";	// 输出的是 1,2 # 3,4 # 5,6 #
}

list 迭代器的设计：

template<class T,class Ref,class Ptr>
struct list_iterator {

	typedef list_node<T> Node;
	typedef list_iterator<T, Ref, Ptr> self;
	typedef list_iterator<T, T&, T*> iterator;

	// 迭代器内部的一个普通指针类型，指向对应的 list 节点
	Node* _node;

	// 迭代器相应类型的定义
	typedef T	value_type;
	typedef Ref reference;
	typedef Ptr pointer;

	// 迭代器的构造
	list_iterator(Node* node):_node(node){}					// 用节点构造当前迭代器
	list_iterator(const iterator& iter):_node(iter._node){}	// 用普通迭代器构造当前迭代器

	// 注意, 对迭代器解引用, 取出来的是节点里面的数据值
	reference operator*()const { return _node->data; }
	// &(operator*()), 这是一个标准的做法
	pointer operator->()const { return &(operator*()); }

	self& operator++() { 
		_node = _node->next; 
		return *this;
	}
	self operator++(int){
		Node* tmp = _node;
		_node = _node->next;
		return tmp;
	}
	self& operator--() { 
		_node = _node->pre; 
		return *this;
	}
	self operator--(int) {
		Node* tmp = _node;
		_node = _node->pre;
		return tmp;
	}

	bool operator==(const self& iter)const { return _node == iter._node; }
	bool operator!=(const self& iter)const { return not operator==(iter); }

};

2，list 的数据结构、一些简单的功能、构造函数

list 是一个带有头节点的环状双向链表，它只需要一个指针就可以完整的表示整个链表，为了方便操作，我们也可以来额外来维护一个 size 变量来表示节点的个数（不包括头节点）。

template<class T>
class list {
	// ...
private:
	typedef list_node<T> Node;
	typedef list<T> self;

private:
	Node* _head = nullptr;  //头节点
	size_t _size = 0;

	void initialize() {		//初始化头节点
		_head = new Node;
		_head->pre = _head->next = _head;
	}
	// ...
};

list 中有关迭代器的操作与一些简单的基础功能：

template<class T>
class list {
	// ...
public:
	//迭代器
	/*正向迭代器*/
	typedef list_iterator<T, T&, T*> iterator;
	typedef list_iterator<T, const T&, const T*> const_iterator;

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

	/*反向迭代器*/
	typedef Reverse_Iterator<iterator> reverse_iterator;
	typedef Reverse_Iterator<const_iterator> const_reverse_iterator;

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

public:
	// 简单的基础功能
	size_t size() { return _size; }
	bool empty() { return _size == 0; }
	void clear() {
		while (not empty()) pop_back();
	}

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

	// 对首尾元素的访问
	T& back() { return *(--end()); }
	const T& back()const { return *(--end()); }
	T& front() { return *begin(); }
	const T& front()const { return *begin(); }
	// ...
};

list 的构造函数：

template<class T>
class list {
	// ...
public:
	//构造
	list() { initialize(); }

	list(size_t n, const T& data = T()) {
		initialize();
		while (n--) { push_back(data); }
	}
	list(int n, const T& data = T()) {
		initialize();
		while (n--) { push_back(data); }
	}

    /*使用迭代器构造*/
	template<class input_iterator>						
	list(input_iterator begin, input_iterator end) {
		initialize();
		while (begin != end) {
			push_back(*(begin++));
		}
	}

	//拷贝
	list(const list& lt) {
		initialize();
		for (const auto& data : lt) {
			push_back(data);
		}
	}

	self& operator=(list lt) {
		swap(lt);
		return *this;
	}

	//析构
	~list() {
		clear();
		delete _head;
		_head = nullptr;
		_size = 0;
	}
	// ...
};

3，list 的对元素操作

std::list 里面提供的元素操作有很多，这里就只挑几种重要的函数来实现。我们把 insert 与 erase 操作实现之后就可以很轻松的实现 push_back()、push_front()（尾插，头插） 与 pop_back() 、pop_front() （尾删，头删）操作了。

template<class T>
class list {
	// ...
public:
	//增
	void push_front(const T& data) { insert(begin(), data); }	// 头插新节点
	void push_back(const T& data) { insert(end(), data); }		// 尾插新节点
	// 在 pos 位置的前面插入一个值为 data 的新节点, 返回新插入的节点的迭代器
	iterator insert(iterator pos, const T& data) {
		Node* node = pos._node;
		Node* newNode = new Node(data);

		newNode->next = node;
		newNode->pre = node->pre;

		node->pre->next = newNode;
		node->pre = newNode;
		++_size;
		return newNode;
	}

	//删
	void pop_front() { erase(begin()); }	// 头删
	void pop_back() { erase(--end()); }		// 尾删
	// 删掉迭代器 pos 所指向的节点, 返回删掉的节点的位置的新节点迭代器
	iterator erase(iterator pos) {
		assert(pos != end());
		Node* tmp = pos._node;
		tmp->pre->next = tmp->next;
		tmp->next->pre = tmp->pre;
		Node* res = tmp->next;
		delete tmp;
		--_size;
		return res;
	}
	// ...
};

4，C++ 11 的一些功能

这里主要实现的功能是 initializer_list 初始化 与 右值引用，如果对这两个东西不了解的话可以看看这两篇博客：

C++11 一些常用的功能-CSDN博客

C++ 左值引用与右值引用-CSDN博客

template<class T>
class list {
	// ...
public:
	//C++ 11 
	//initializer_list构造
	list(const std::initializer_list<T>& lt) {
		initialize();
		for (const T& data : lt) {
			push_back(data);
		}
	}

	//右值引用相关
	//移动构造与移动赋值
	list(list&& lt) :_head(lt._head), _size(lt._size) {
		initialize();
		lt._head = nullptr;
		lt._size = 0;
	}

	self& operator=(list&& lt) {
		delete* this;
		std::swap(_head, lt._head);
		std::swap(_size, lt._size);
	}

	//插入
	void push_front(T&& data) { insert(begin(), std::forward<T>(data)); }
	void push_back(T&& data) { insert(end(), std::forward<T>(data)); }
	iterator insert(iterator pos, T&& data) {
		Node* node = pos._node;
		Node* newNode = new Node(std::forward<T>(data));

		newNode->next = node;
		newNode->pre = node->pre;

		node->pre->next = newNode;
		node->pre = newNode;
		++_size;
		return newNode;
	}
	// ...
};

5，完整代码：

namespace mySTL {

	// list 节点类
	template<class T>
	struct list_node {
		list_node<T>* next, * pre;	// next 指向下一个节点，pre指向前一个节点
		T data;
		list_node(const T& data_ = T())
			:next(nullptr),pre(nullptr),data(data_){}
	};

	// list 迭代器类
	template<class T,class Ref,class Ptr>
	struct list_iterator {

		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;
		typedef list_iterator<T, T&, T*> iterator;

		// 迭代器内部的一个普通指针类型，指向对应的 list 节点
		Node* _node;

		// 迭代器相应类型的定义
		typedef T	value_type;
		typedef Ref reference;
		typedef Ptr pointer;

		// 迭代器的构造
		list_iterator(Node* node):_node(node){}					// 用节点构造当前迭代器
		list_iterator(const iterator& iter):_node(iter._node){}	// 用普通迭代器构造当前迭代器

		// 注意, 对迭代器解引用, 取出来的是节点里面的数据值
		reference operator*()const { return _node->data; }
		// &(operator*()), 这是一个标准的做法
		pointer operator->()const { return &(operator*()); }

		self& operator++() { 
			_node = _node->next; 
			return *this;
		}
		self operator++(int){
			Node* tmp = _node;
			_node = _node->next;
			return tmp;
		}
		self& operator--() { 
			_node = _node->pre; 
			return *this;
		}
		self operator--(int) {
			Node* tmp = _node;
			_node = _node->pre;
			return tmp;
		}

		bool operator==(const self& iter)const { return _node == iter._node; }
		bool operator!=(const self& iter)const { return not operator==(iter); }

	};
	
	// list 类
	template<class T>
	class list {
	private:
		typedef list_node<T> Node;
		typedef list<T> self;

	private:
		Node* _head = nullptr;  //头节点
		size_t _size = 0;

		void initialize() {		//初始化头节点
			_head = new Node;
			_head->pre = _head->next = _head;
		}

	public:
		//迭代器
		/*正向迭代器*/
		typedef list_iterator<T, T&, T*> iterator;					
		typedef list_iterator<T, const T&, const T*> const_iterator;

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

		/*反向迭代器*/
		typedef Reverse_Iterator<iterator> reverse_iterator;		
		typedef Reverse_Iterator<const_iterator> const_reverse_iterator;

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

	public:
		// 简单的基础功能
		size_t size() { return _size; }
		bool empty() { return _size == 0; }
		void clear() { 
			while (not empty()) pop_back();
		}

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

		// 对首尾元素的访问
		T& back() { return *(--end()); }
		const T& back()const { return *(--end()); }
		T& front() { return *begin(); }
		const T& front()const { return *begin(); }

		// 在迭代器 start 与 finish 构成的范围内查找值为 target 的节点
		iterator find(const iterator& start, const iterator& finish, const T& target) {
			for (iterator it = start;it != finish;++it) {
				if (*it == target) return it;
			}
			return finish;
		}

	public:
		//构造
		list() { initialize(); }

		list(size_t n, const T& data = T()) {
			initialize();
			while (n--) { push_back(data); }
		}
		list(int n, const T& data = T()) {
			initialize();
			while (n--) { push_back(data); }
		}

		template<class input_iterator>						/*使用迭代器构造*/
		list(input_iterator begin, input_iterator end) {
			initialize();
			while (begin != end) {
				push_back(*(begin++));
			}
		}

		//拷贝
		list(const list& lt) {
			initialize();
			for (const auto& data : lt) {
				push_back(data);
			}
		}

		self& operator=(list lt) {
			swap(lt);
			return *this;
		}

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

	public:
		//增
		void push_front(const T& data) { insert(begin(), data); }	// 头插新节点
		void push_back(const T& data) { insert(end(), data); }		// 尾插新节点
		// 在 pos 位置的前面插入一个值为 data 的新节点, 返回新插入的节点的迭代器
		iterator insert(iterator pos,const T& data) {
			Node* node = pos._node;
			Node* newNode = new Node(data);

			newNode->next = node;
			newNode->pre = node->pre;

			node->pre->next = newNode;
			node->pre = newNode;
			++_size;
			return newNode;
		}

		//删
		void pop_front() { erase(begin()); }	// 头删
		void pop_back() { erase(--end()); }		// 尾删
		// 删掉迭代器 pos 所指向的节点, 返回删掉的节点的位置的新节点迭代器
		iterator erase(iterator pos) {
			assert(pos != end());
			Node* tmp = pos._node;
			tmp->pre->next = tmp->next;
			tmp->next->pre = tmp->pre;

			Node* res = tmp->next;
			delete tmp;
			--_size;
			return res;
		}

	public:
		//C++ 11 
		//initializer_list构造
		list(const std::initializer_list<T>& lt) {
			initialize();
			for (const T& data : lt) {
				push_back(data);
			}
		}

		//右值引用相关
		//移动构造与移动赋值
		list(list&& lt) :_head(lt._head), _size(lt._size) {
			initialize();
			lt._head = nullptr;
			lt._size = 0;
		}

		self& operator=(list&& lt) {
			delete *this;
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		//插入
		void push_front(T&& data) { insert(begin(), std::forward<T>(data)); }
		void push_back(T&& data) { insert(end(), std::forward<T>(data)); }
		iterator insert(iterator pos, T&& data) {
			Node* node = pos._node;
			Node* newNode = new Node(std::forward<T>(data));

			newNode->next = node;
			newNode->pre = node->pre;

			node->pre->next = newNode;
			node->pre = newNode;
			++_size;
			return newNode;
		}

	};

}

二，queue

queue 是一种先进先出（First In First Out，FIFO）的数据结构，它有两个出口。queue 允许新增元素、移除元素、从最底端加人元素取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法可以存取 queue 的其它元素。也就是说，queue 不允许有遍历行为。将元素推人queue 的操作称为 push，将元素推出 queue 的操作称为 pop。

queue 与 stack 一样，都是容器适配器（container adapters），他们的底层都是其他的容器，STL 中的 stack 与 queue 实际上都是对其他容器的封装，其都不支持迭代器。

我们可以选择用 list 也可以选择用 deque 来当作 queue 的底层容器。

namespace mySTL {

	template<class T, class Container = list<T>>
	class queue {
	private:
		Container _cont;	// 底层使用的容器
	public:
		void push(const T& data) { _cont.push_back(data); }
		void push(T&& data) { _cont.push_back(std::forward<T>(data)); }
		void pop() { _cont.pop_front(); }

		T& back() { return _cont.back(); }
		const T& back()const { return _cont.back(); }
		T& front() { return _cont.front(); }
		const T& front()const { return _cont.front(); }

		size_t size() { return _cont.size(); }
		bool empty() { return _cont.empty(); }

	};

}

阅读全部

相关推荐

  2. c++STL list 简单模拟实现

    2024-03-26 10:56:02       33 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-26 10:56:02       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-26 10:56:02       101 阅读

  9. 在Django里面运行非项目文件

    2024-03-26 10:56:02       82 阅读

  19. Python语言-面向对象

    2024-03-26 10:56:02       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-03-26 10:56:02       85 阅读

热门阅读

  1. 使用 Vite 和 Bun 构建前端

    2024-03-26 10:56:02       43 阅读

  3. Docker 安装HBase 并使用

    2024-03-26 10:56:02       41 阅读

  5. 【笔记】Hbase基础笔记

    2024-03-26 10:56:02       44 阅读

  6. qt5-入门-容器类

    2024-03-26 10:56:02       40 阅读

  7. 计算机视觉的研究方向

    2024-03-26 10:56:02       43 阅读

  8. 2024.3.25

    2024-03-26 10:56:02       35 阅读

  9. C语言随记——八道C语言简单算法题

    2024-03-26 10:56:02       39 阅读

  15. HTML快速入门笔记

    2024-03-26 10:56:02       38 阅读

  16. OpenCV图像像素值统计

    2024-03-26 10:56:02       41 阅读

  18. 智慧商场数字化创新需要有数字能力帮手

    2024-03-26 10:56:02       42 阅读

  19. flutter路由跳转

    2024-03-26 10:56:02       40 阅读

  20. 3月25日，每日信息差

    2024-03-26 10:56:02       44 阅读

  22. P5740 【深基7.例9】最厉害的学生

    2024-03-26 10:56:02       43 阅读

  23. 3544: 【C1】【基础】输出小数部分

    2024-03-26 10:56:02       36 阅读

  25. 九、Spring源码学习之initApplicationEventMulticaster方法

    2024-03-26 10:56:02       41 阅读

  26. 动物是否具有学习编程的能力——一次跨物种智能探索之旅

    2024-03-26 10:56:02       41 阅读

  30. AI：133-基于深度学习的工业质检自动化

    2024-03-26 10:56:02       44 阅读