欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL::deque 双端队列

程序员文章站 2024-02-11 23:37:52
...

STL::deque 双端队列的具体实现(C++高仿版本)

附有详细注释,静下心来,认真看,会懂的。

Coded By
东华大学 151340112
联系方式 [email protected]
或者 [email protected]

一直以来,都是某人的真真的树洞噢~

程序运行结果(VS 2017, 15.9.11版本)
STL::deque 双端队列

程序源码:

// ConsoleApplication_OJ.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//虚函数是指一个类中你希望重载的成员函数 ,当你用一个基类指针或引用
//指向一个继承类对象的时候,调用一个虚函数时, 实际调用的是继承类的版本
//

// std::deque ( double-ended queue ,双端队列)是可以进行下标访问的顺序容器,它允许在其首尾两端快速插入及删除元素。
// 本程序为 双端队列 STL::deque 的简单实现,C++高仿版本(含详细注释)
// 参考文献 https://blog.csdn.net/blood_flowing/article/details/27830905
// 参考文献2 https://blog.csdn.net/haluoluo211/article/details/80766150
// 参考文献3 https://blog.csdn.net/codedoctor/article/details/78107043
// 参考文献4 《STL源码剖析》by 侯捷 华中科技大学出版社
//
#include<iostream>
#include<algorithm>
#include<type_traits>
using namespace std;

//buffer size set,即缓冲区大小计算
/* iterator中需要缓冲区的长度,当n不等于0,return n,表示buffer size使用指定值
*如果n == 0,buffer size使用默认值
*/
inline size_t _deque_buf_size(size_t n, size_t sz) {
	return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

/*一些空间配置器里面的函数*/
struct __false_type {};
struct __true_type {};
struct input_iterator_tag {};

// deque 迭代器的实现(以Deque_iterator类包装、实现)
template<class T, class Ref, class Ptr, size_t BufSiz>
class Deque_iterator {
public:
	//迭代器
	typedef Deque_iterator<T, T&, T*, BufSiz> iterator; 
	typedef Deque_iterator<T, const T&, const T*, BufSiz> const_iterator;

	//缓冲区大小
	static size_t buffer_size() { return _deque_buf_size(BufSiz, sizeof(T)); } 

	//5个基本的迭代器型别
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef T* pointer;
	typedef T& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T** map_pointer;

	typedef Deque_iterator self; //保持与容器的联结
	T* cur; //访问缓冲区,指向缓冲区中的现行元素
	T* first; //指向缓冲区头,即指向缓冲区中的头元素
	T* last; // 指向缓冲区尾,即指向缓冲区中的尾元素
	
	 //由于,指针肯会遇到缓冲区边缘,因此需要跳到下一个缓冲区
	//于是需要指向map回去下一个缓冲区地址
	map_pointer node; //map中控器,指向管控中心

	Deque_iterator() :first(0), cur(0), last(0), node(0) {}
	Deque_iterator(T* x, map_pointer y) :cur(x), first(*y), last(*y + Deque_iterator::buff_size()), node(y) {}
	Deque_iterator(const Deque_iterator& x) :
		cur(x.cur), first(x.first), last(x.last), node(x.node) {}
	void set_node(map_pointer new_node) {
		node = new_node;
		first = *new_node;
		last = first + difference_type(Deque_iterator::buffer_size());
	}

	//重载*(显然返回的是引用)
	reference operator*()const { return *cur; }
	pointer operator->()const { return &(operator*()); }
	difference_type operator -(const self& x)const { //量迭代器之间的距离
		return difference_type(Deque_iterator::buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur);
	}
	self& operator++() {
		++cur;
		if (cur == last) { //如果已达所在缓冲区的尾端
			set_node(node + 1); //切换至下一节点(缓冲区)
			cur = first; //新起点(现行元素指向首部)
		}
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		++*this;
		return tmp;
	}
	self& operator--() {
		if (cur == first) {
			set_node(node - 1);
			cur = last;
		}
		--cur;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		--*this;
		return tmp;
	}
	self& operator+=(difference_type n) { // n 可正可负
		difference_type offset = n + (cur - first);
		if (offset >= 0 && offset <= difference_type(buffer_size()))  // 同一个缓冲区内
			cur += n;
		else { //不在同一个缓冲区
			difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) :
				-difference_type((-offset - 1) / buffer_size()) - 1;

			set_node(node + node_offset); // 切换至正确的缓冲区
			cur = first + (offset - node_offset * difference_type(buffer_size()));   // 现行切换至正确的元素(首部)
		}
		return *this;
	}
	self operator+(difference_type n) const{ // 返回的不是引用,因此const函数
		self tmp = *this;
		return tmp += n; //直接调用operator +=
	}
	self& operator-=(difference_type n) { return *this += -n; }
	self operator-(difference_type n)const {
		self tmp = *this;
		return tmp += -n; //直接调用operator +=
	}
	bool operator==(const self& x)const { return (cur == x.cur); }
	bool operator!=(const self& x)const { return (cur != x.cur); }
	bool operator<(const self& x)const {//同一个节点或者不同节点
		return node == x.node ? (cur < x.cur) : (node < x.node); // 三目运算符
	}
	// 随机存取,迭代器可以直接跳跃 n 个距离
    // 调用上面的 operator + ,以及operator *
	reference operator[](difference_type n) const { return *(*this + n); }
};

// deque类的设计与实现
template<class T, size_t BufSize = 0> // buffsize 置0,因为创建对象、一开始为空队列
class Deque {
public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
public:
	typedef Deque_iterator<T, T&, T*, BufSize> iterator;
protected:
	typedef pointer* map_pointer; // 中控器
	static size_type buffer_size() {
		return _deque_buf_size(BufSize, sizeof(value_type));
	}
	static size_type initial_map_size() { return 8; }
protected:
	iterator start;
	iterator finish;
	map_pointer map;
	size_type map_size; // map容量
private:
	// 因为都是内联函数inline,因此
	//无需再注意函数彼此调用时候的声明的先后顺序
	inline void destroy(iterator first1, iterator last1){
		__destroy(first1, last1, pointer(0));
	}
	inline void __destroy(iterator first, iterator last, T*){
		//typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;  
		//__destroy_aux(first, last, __false_type);  
		__destroy_aux(first, last);
	}
	inline void  __destroy_aux(iterator first, iterator last){
		for (; first < last; ++first)
			destroy(&*first);
	}
	inline void destroy(pointer first, pointer last) {
		for (; first < last; ++first)
			destroy(first); //接下来的第三行
	}
	inline void destroy(T* pointer){
		pointer->~T();
	}
public:
	iterator begin() { return start; }
	iterator end() { return  finish; }
	reference operator[](size_type n) { return start[difference_type(n)]; }
	reference front() { return *start; }
	reference back(){
		iterator tmp = finish;
		--tmp;
		return *tmp;
	}
	size_type size() const { return finish - start; }
	size_type max_size() const { return size_type(-1); }
	bool empty() const { return finish == start; }
private:
	void construct(pointer p, const value_type& value) { new (p) value_type(value); }
	void push_back_aux(const value_type& t) {
		value_type t_copy = t;
		reserve_map_at_back();
		*(finish.node + 1) = allocate_node(buffer_size());
		try {
			construct(finish.cur, t_copy);
			finish.set_node(finish.node + 1);
			finish.cur = finish.first;
		}
		catch (...) {
			deallocate_node(*(finish.node + 1));
			cout << "node add failed." << endl;
			throw;
		}

	}
	void reserve_map_at_back(size_type nodes_to_add = 1) {
		if (nodes_to_add + 1 > map_size - (finish.node - map))
			reallocate_map(nodes_to_add, false);
	}
	void reserve_map_at_front(size_type nodes_to_add = 1) {
		if (nodes_to_add > start.node - map)
			reallocate_map(nodes_to_add, true);
	}
	void new_elements_at_front(size_type new_elements) {
		size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
		reserve_map_at_front(new_nodes);
		size_type i;
		try {
			for (i = 1; i <= new_nodes; ++i)
				*(start.node - i) = allocate_node(buffer_size());
		}
		catch (...) {
			for (size_type j = 1; j < i; ++j)
				deallocate_node(*(start.node - j));
			throw;
		}
	}
	void new_elements_at_back(size_type new_elements) {
		size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
		reserve_map_at_back(new_nodes);
		size_type i;
		try {
			for (i = 1; i <= new_nodes; ++i)
				*(finish.node + i) = allocate_node(buffer_size());
		}
		catch (...) {
			for (size_type j = 1; j < i; ++j)
				deallocate_node(*(finish.node + j));
			throw;
		}
	}
	iterator reserve_elements_at_front(size_type n) {
		size_type vacancies = start.cur - start.first;
		if (n > vacancies)
			new_elements_at_front(n - vacancies);
		return start - difference_type(n);
	}
	iterator reserve_elements_at_back(size_type n) {
		size_type vacancies = (finish.last - finish.cur) - 1;
		if (n > vacancies)
			new_elements_at_back(n - vacancies);
		return finish + difference_type(n);
	}
	void reallocate_map(size_type nodes_to_add, bool add_at_front) {
		size_type old_num_nodes = finish.node - start.node + 1;
		size_type new_num_nodes = old_num_nodes + nodes_to_add;

		map_pointer new_nstart;
		if (map_size > 2 * new_num_nodes) {
			new_nstart = map + (map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
			if (new_nstart < start.node)
				copy(start.node, finish.node + 1, new_nstart);
			else
				copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
		}
		else {
			size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;

			map_pointer new_map = allocate_map(new_map_size);
			new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
			copy(start.node, finish.node + 1, new_nstart);
			deallocate_map(map, map_size);
			map = new_map;
			map_size = new_map_size;
		}

		start.set_node(new_nstart);
		finish.set_node(new_nstart + old_num_nodes - 1);
	}
	void push_front_aux(const value_type& t) {
		value_type t_copy = t;
		reserve_map_at_front();
		*(start.node - 1) = allocate_node(buffer_size());
		try {
			start.set_node(start.node - 1);
			start.cur = start.last - 1;
			construct(start.cur, t_copy);
		}
		catch (...) {
			start.set_node(start.node + 1);
			start.cur = start.first;
			deallocate_node(*(start.node - 1));
			throw;
		}
	}
	void  pop_back_aux() {
		deallocate_node(finish.first);
		finish.set_node(finish.node - 1);
		finish.cur = finish.last - 1;
		destroy(finish.cur);
	}
	void pop_front_aux() {
		destroy(start.cur);
		deallocate_node(start.first);
		start.set_node(start.node + 1);
		start.cur = start.first;
	}
	iterator insert_aux(iterator pos, const value_type& x) { //随机插入需要移动数据,效率很低
		difference_type index = pos - start;
		value_type x_copy = x;
		if (index < size() / 2) {
			push_front(front());
			iterator front1 = start;
			++front1;
			iterator front2 = front1;
			++front2;
			pos = start + index;
			iterator pos1 = pos;
			++pos1;
			copy(front2, pos1, front1);
		}
		else {
			push_back(back());
			iterator back1 = finish;
			--back1;
			iterator back2 = back1;
			--back2;
			pos = start + index;
			copy_backward(pos, back2, back1);
		}
		*pos = x_copy;
		return pos;
	}
	void insert_aux(iterator pos, size_type n, const value_type& x) {
		const difference_type elems_before = pos - start;
		size_type length = size();
		value_type x_copy = x;
		if (elems_before < length / 2) {
			iterator new_start = reserve_elements_at_front(n);
			iterator old_start = start;
			pos = start + elems_before;
			try {
				if (elems_before >= difference_type(n)) {
					iterator start_n = start + difference_type(n);
					uninitialized_copy(start, start_n, new_start);
					start = new_start;
					copy(start_n, pos, old_start);
					fill(pos - difference_type(n), pos, x_copy);
				}
				else {
					__uninitialized_copy_fill(start, pos, new_start, start, x_copy);
					start = new_start;
					fill(old_start, pos, x_copy);
				}

			}
			catch (...) {
				destroy_nodes_at_front(new_start);
				throw;
			}
		}
		else {
			iterator new_finish = reserve_elements_at_back(n);
			iterator old_finish = finish;
			const difference_type elems_after = difference_type(length) - elems_before;
			pos = finish - elems_after;
			try {
				if (elems_after > difference_type(n)) {
					iterator finish_n = finish - difference_type(n);
					uninitialized_copy(finish_n, finish, finish);
					finish = new_finish;
					copy_backward(pos, finish_n, old_finish);
					fill(pos, pos + difference_type(n), x_copy);
				}
				else {
					__uninitialized_fill_copy(finish, pos + difference_type(n), x_copy,
						pos, finish);
					finish = new_finish;
					fill(pos, old_finish, x_copy);
				}
			}
			catch (...) {
				destroy_nodes_at_back(new_finish);
				throw;
			}
		}
	}
	iterator __uninitialized_fill_copy(iterator result, iterator mid,
		const value_type& x,
		iterator first, iterator last) {
		uninitialized_fill(result, mid, x);
		try {
			return uninitialized_copy(first, last, mid);
		}
		catch (...) {
			destroy(result, mid);
			throw;
		}
	}
	void __uninitialized_copy_fill(iterator first1, iterator last1,
		iterator first2, iterator last2,
		const value_type& x) {
		iterator mid2 = uninitialized_copy(first1, last1, first2);
		try {
			uninitialized_fill(mid2, last2, x);
		}
		catch (...) {
			destroy(first2, mid2);
			throw;
		}
	}
	void destroy_nodes_at_front(iterator before_start) {
		for (map_pointer n = before_start.node; n < start.node; ++n)
			deallocate_node(*n);
	}
	void destroy_nodes_at_back(iterator after_finish) {
		for (map_pointer n = after_finish.node; n > finish.node; --n)
			deallocate_node(*n);
	}
	void deallocate(pointer p, size_type n) {
		::operator delete(p);
	}
	/*template <class InputIterator>
	void insert(iterator pos,InputIterator first, InputIterator last,
									   input_iterator_tag) {
		copy(first, last, inserter(*this, pos));
	}
	template <class Container, class Iterator>
	inline insert_iterator<Container> inserter(Container& x, Iterator i) {
		typedef typename Container::iterator iter;
		return insert_iterator<Container>(x, iter(i));
	}*/
	void creat_map_and_nodes(size_type num_elements) {
		size_type num_nodes = num_elements / buffer_size() + 1;
		//在map的前后各预留一个节点,以备扩充
		map_size = max(initial_map_size(), num_nodes + 2);
		map = allocate_map(map_size);
		map_pointer nstart = map + (map_size - num_nodes) / 2;
		map_pointer nfinish = nstart + num_nodes - 1;
		map_pointer cur;
		try {
			for (cur = nstart; cur <= nfinish; ++cur) //为map中的每个节点配置缓冲区
				*cur = allocate_node(buffer_size());
		}
		catch (...) { //若不成功,回滚
			for (map_pointer ptr = nstart; ptr < cur; ++ptr)
				deallocate_node(*ptr);
			deallocate_map(map, map_size);
			throw;
		}
		start.set_node(nstart);
		finish.set_node(nfinish);
		start.cur = start.first;
		finish.cur = finish.first + num_elements % buffer_size();
	}
	void deallocate_map(map_pointer tmp, size_type n) {
		::operator delete(tmp);
	}
	void deallocate_node(pointer tmp) {
		::operator delete(tmp);
	}
	inline pointer allocate_node(ptrdiff_t size) {
		set_new_handler(0);
		pointer tmp = (pointer)(::operator new((size_t)(size * sizeof(value_type))));
		if (tmp == 0) {
			cout << "out of memory" << endl;
			exit(1);
		}
		return tmp;
	}
	inline map_pointer allocate_map(ptrdiff_t size) {
		set_new_handler(0);
		map_pointer tmp = (map_pointer)(::operator new((size_t)(size * sizeof(pointer))));
		if (tmp == 0) {
			cout << "out of memory" << endl;
			exit(1);
		}
		return tmp;
	}
	void fill_initialize(size_type n, const value_type& value) {
        // 分配map以及缓冲区的内存
	    // 初始化好对应的指针位置
		creat_map_and_nodes(n);

		// 缓冲区每个节点设置初始值
		// 最后一个缓冲区设置有所不同(因为尾端可能有备用空间,不必设置初始值)
		map_pointer cur;
		try {
			for (cur = start.node; cur < finish.node; ++cur)
				uninitialized_fill(*cur, *cur + buffer_size(), value);
			uninitialized_fill(finish.first, finish.cur, value);
		}
		catch (...) {
			for (map_pointer p = start.node; p < cur; ++p)
				deallocate_node(*p);
			deallocate_map(map, map_size);
			throw;
		}
	}
	void destroy_map_and_nodes() {
		for (map_pointer curr = start.node; curr <= finish.node; ++curr) {
			deallocate_node(*curr);
		}
		deallocate_map(map, map_size);
	}
public:
	Deque() :start(), finish(), map(0), map_size(0) { creat_map_and_nodes(0); }
	Deque(size_type n, const value_type& value) :start(), finish(), map(0), map_size(0) {
		fill_initialize(n, value);
	}
	explicit Deque(size_type n) : start(), finish(), map(0), map_size(0)
	{
		fill_initialize(n, value_type());
	}
	Deque(Deque& x) : start(), finish(), map(0), map_size(0)
	{
		creat_map_and_nodes(x.size());
		try {
			uninitialized_copy(x.begin(), x.end(), start);
		}
		catch (...) {
			cout << "copy failed." << endl;
			destroy_map_and_nodes();
			throw;
		}

	}
	~Deque() {
		destroy(start, finish);
		destroy_map_and_nodes();
	}
	void push_back(const value_type& t) {
		if (finish.cur != finish.last - 1) {
			construct(finish.cur, t);
			++finish.cur;
		}
		else {
			push_back_aux(t);
		}
	}
	void push_front(const value_type& t) {
		if (start.cur != start.first) {
			construct(start.cur - 1, t);
			--start.cur;
		}
		else
			push_front_aux(t);
	}
	void pop_back() {
		if (finish.cur != finish.first) {
			--finish.cur;
			destroy(finish.cur);
		}
		else
			pop_back_aux();
	}
	void pop_front() {
		if (start.cur != start.last - 1) {
			destroy(start.cur);
			++start.cur;
		}
		else
			pop_front_aux();
	}
	iterator insert(iterator position, const value_type& x) {
		if (position.cur == start.cur) { //头部插入
			push_front(x);
			return start;
		}
		else if (position.cur == finish.cur) { //尾部插入
			push_back(x);
			iterator tmp = finish;
			--tmp;
			return tmp;
		}
		else {
			return insert_aux(position, x);
		}
	}
	void  insert(iterator pos, size_type n, const value_type& x) {
		if (pos.cur == start.cur) {
			iterator new_start = reserve_elements_at_front(n);
			uninitialized_fill(new_start, start, x);
			start = new_start;
		}
		else if (pos.cur == finish.cur) {
			iterator new_finish = reserve_elements_at_back(n);
			uninitialized_fill(finish, new_finish, x);
			finish = new_finish;
		}
		else
			insert_aux(pos, n, x);
	}
	void insert(iterator pos, iterator first, iterator last) {
		//insert(pos, first, last, iterator_category(first));
		iterator tmp = pos; //这样易于实现,但是效率极低
		while (first != last) {
			insert(tmp, (*first));
			++first;
			++tmp;
		}
	}
	iterator erase(iterator pos) { //将要删除的对象移动到队首或者队尾,然后pop
		iterator next = pos;
		++next;
		difference_type index = pos - start;
		if (index < (size() >> 1)) {
			copy_backward(start, pos, next);
			pop_front();
		}
		else {
			copy(next, finish, pos);
			pop_back();
		}
		return start + index;
	}
	iterator erase(iterator first, iterator last) {
		if (first == start && last == finish) {
			clear();
			return finish;
		}
		else {
			difference_type n = last - first;
			difference_type elems_before = first - start;
			if (elems_before < (size() - n) / 2) {
				copy_backward(start, first, last);
				iterator new_start = start + n;
				destroy(start, new_start);
				for (map_pointer cur = start.node; cur < new_start.node; ++cur)
					deallocate(*cur, buffer_size());
				start = new_start;
			}
			else {
				copy(last, finish, first);
				iterator new_finish = finish - n;
				destroy(new_finish, finish);
				for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
					deallocate(*cur, buffer_size());
				finish = new_finish;
			}
			return start + elems_before;
		}
	}
	void clear() {
		for (map_pointer node = start.node + 1; node < finish.node; ++node) {
			destroy(*node, *node + buffer_size());
			deallocate(*node, buffer_size());
		}
		if (start.node != finish.node) {
			destroy(start.cur, start.last);
			destroy(finish.first, finish.cur);
			deallocate(finish.first, buffer_size());
		}
		else
			destroy(start.cur, finish.cur);

		finish = start;
	}
};
//模板函数测试队列大小、以及队列是否为空
template<class T>
void test_Deque_Size_And_IsEmptyOrNot(const T& deque) {
	cout << "deque size is " << deque.size() << endl;
	if (deque.empty())
		cout << "The deque is already empty!" << endl;
	else
		cout << "The deque is not empty!" << endl;
}

void test_Deque_By_Data_Types() { // 存储数据类型测试
	cout << "Test Int Type:" << endl;
	Deque<int> dequeInt1;
	Deque<int> dequeInt2(10);
	Deque<int> dequeInt3(10, 9);
	for (Deque<int>::iterator iteInt = dequeInt3.begin(); iteInt != dequeInt3.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	Deque<int> dequeInt4(dequeInt3);
	for (Deque<int>::iterator iteInt = dequeInt4.begin(); iteInt != dequeInt4.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;

	cout << "Test Double Type:" << endl;
	Deque<double> dequeDou1;
	Deque<double> dequeDou2(10);
	Deque<double> dequeDou3(10, 2.3);
	for (Deque<double>::iterator iteDou = dequeDou3.begin(); iteDou != dequeDou3.end(); ++iteDou)
		cout << *iteDou << " ";
	cout << endl;
	Deque<double> dequeDou4(dequeDou3);
	for (Deque<double>::iterator iteDou = dequeDou4.begin(); iteDou != dequeDou4.end(); ++iteDou)
		cout << *iteDou << " ";
	cout << endl;

	cout << "Test Class Type:" << endl;
	class A {
		int data;
	public:
		A(int a = 0) :data(a) {}
		operator int() {
			return data;
		}
	};
	A a(7);
	Deque<A> dequeA1;
	Deque<A> dequeA2(10);
	Deque<A> dequeA3(10, a);
	for (Deque<A>::iterator iteA = dequeA3.begin(); iteA != dequeA3.end(); ++iteA)
		cout << *iteA << " ";
	cout << endl;
	Deque<A> dequeA4(dequeA3);
	for (Deque<A>::iterator iteA = dequeA4.begin(); iteA != dequeA4.end(); ++iteA)
		cout << *iteA << " ";
	cout << endl;
}

void test_Functions_By_Using_Int_Type() { //部分功能测试(进、出队列成员函数)
	Deque<int> dequeInt(10, 9);
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	dequeInt.push_back(10);
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	dequeInt.push_front(10);
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	dequeInt.pop_back();
	dequeInt.pop_front();
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	dequeInt.insert(--dequeInt.end(), 12);
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	dequeInt.insert(--dequeInt.end(), 3, 11);
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	Deque<int> dequeInt1(10, 0);
	Deque<int>::iterator tmp = dequeInt.end();
	dequeInt.insert(----tmp, dequeInt1.begin(), dequeInt1.end());
	for (Deque<int>::iterator iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
}

void test_Erase_By_Using_Int_Type() { //擦除测试
	Deque<int> dequeInt(10, 9);
	Deque<int>::iterator iteInt;

	for (iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	test_Deque_Size_And_IsEmptyOrNot(dequeInt);

	dequeInt.erase(--iteInt);
	cout << "After earsing the last one element:" << endl;
	for (iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	test_Deque_Size_And_IsEmptyOrNot(dequeInt);

	Deque<int>::iterator iteInt1 = dequeInt.begin();
	Deque<int>::iterator iteInt2 = dequeInt.end();
	cout << "After earsing all elements but the first and the last:" << endl;
	dequeInt.erase(++iteInt1, --iteInt2);
	for (iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	test_Deque_Size_And_IsEmptyOrNot(dequeInt);

	cout << "After earsing all elements:" << endl;
	dequeInt.erase(dequeInt.begin(), dequeInt.end());
	for (iteInt = dequeInt.begin(); iteInt != dequeInt.end(); ++iteInt)
		cout << *iteInt << " ";
	cout << endl;
	test_Deque_Size_And_IsEmptyOrNot(dequeInt);
}


int main() {
	cout << "---------Data type test-------------" << endl;
	test_Deque_By_Data_Types();
	cout << "---------function  test-------------" << endl;
	test_Functions_By_Using_Int_Type();
	cout << "---------- erase  test--------------" << endl;
	test_Erase_By_Using_Int_Type();
	return 0;
}

祝福 所有看到这篇文字的人们都能每天开心!
最重要的,是和你的那个她一起天天开心!
别的,真的没必要计较了。

LYY,
你还好吗?
我……
我是树洞呀。
……
哎~

2019.05.07 02:00
蒙 ~