STL_Deque

迷南。 2022-09-23 05:55 156阅读 0赞

**C++ Deque(**双向队列**)**

是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。

实际上，deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。

**Deque ****的特点：**

(1) 随机访问方便，即支持\[ \] 操作符和vector.at() ，但性能没有vector 好；

(2) 可以在内部进行插入和删除操作，但性能不及list ；

(3) 可以在两端进行push 、pop ；

(4) 相对于verctor 占用更多的内存。

双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）。

1.Constructors 创建一个新双向队列

语法:

deque();//创建一个空双向队列

deque( size\_type size );// 创建一个大小为size的双向队列

deque( size\_type num, const TYPE &val ); //放置num个val的拷贝到队列中

deque( const deque &from );// 从from创建一个内容一样的双向队列

deque( input\_iterator start, input\_iterator end );

// start 和 end - 创建一个队列，保存从start到end的元素。

// constructing deques
 #include <iostream>
 #include <deque>
 int main()
 {
 	unsigned int i;
 	std::deque<int> first; //构造一个空的双向队列 // empty deque of ints
 	std::deque<int> second(4, 100); //设置4个值为100的双向队列
 	std::deque<int> third(second.begin(), second.end()); //以第二个为基本拷贝
 	std::deque<int> fourth(third);//以第三个为准进行构造
 
 	int myints[] = { 16, 2, 77, 29 };
 	std::deque<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
 
 	std::cout << "The contents of fifth are:";
 	for (std::deque<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
 		std::cout << ' ' << *it;
 
 	std::cout << '\n';
 	system("pause");
 	return 0;
 }

2.Operators 比较和赋值双向队列

//可以使用\[\]操作符访问双向队列中单个的元素

3.assign() 设置双向队列的值

语法:

void assign( input\_iterator start, input\_iterator end);

//start和end指示的范围为双向队列赋值

void assign( Size num, const TYPE &val );//设置成num个val。

// deque::assign
 #include <iostream>
 #include <deque>
 
 int main()
 {
 	std::deque<int> first;
 	std::deque<int> second;
 	std::deque<int> third;
 
 	first.assign(7, 100); //设置7个值为100的双端队列
 
 	std::deque<int>::iterator it;
 	it = first.begin() + 1;
 	//it指向第二个，end()-1---->共5个
 	second.assign(it, first.end() - 1); 
 
 	int myints[] = { 1776, 7, 4 };
 	third.assign(myints, myints + 3); // assigning from array.
 
 	std::cout << "Size of first: " << int(first.size()) << '\n';
 	std::cout << "Size of second: " << int(second.size()) << '\n';
 	std::cout << "Size of third: " << int(third.size()) << '\n';
 
 	system("pause");
 	return 0;
 }

4.at() 返回指定的元素   
   语法:

reference at( size\_type pos ); 返回一个引用，指向双向队列中位置pos上的元素

std::deque<unsigned> mydeque(10); // 10 zero-initialized unsigneds
 	for (unsigned i = 0; i<mydeque.size(); i++)
 		mydeque.at(i) = i; //0 1 2 3 4 5 6 7 8 9
 	std::cout << "mydeque contains:";
 	for (unsigned i = 0; i<mydeque.size(); i++)
 		std::cout << ' ' << mydeque.at(i);

5.back() 返回最后一个元素

语法:

reference back();//返回一个引用，指向双向队列中最后一个元素

// deque::back
 #include <iostream>
 #include <deque>
 
 int main()
 {
 	std::deque<int> mydeque;
 
 	mydeque.push_back(10);//压入一个10
 	while (mydeque.back() != 0)
 		mydeque.push_back(mydeque.back() - 1);
 	//back每次得到最后一个元素，然后在减一，所以压入9-0
 	std::cout << "mydeque contains:";
 	for (std::deque<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
 		std::cout << ' ' << *it;
 
 	std::cout << '\n';
 	system("pause");
 	return 0;
 }

6.begin() 返回指向第一个元素的迭代器

语法:

iterator begin();//返回一个迭代器，指向双向队列的第一个元素

7.clear() 删除所有元素

8.empty() 返回真如果双向队列为空

9.end() 返回指向尾部的迭代器

10.erase() 删除一个元素

语法:

iterator erase( iterator pos ); //删除pos位置上的元素

iterator erase( iterator start, iterator end ); //删除start和end之间的所有元素

//返回指向被删除元素的后一个元素

11.front() 返回第一个元素的引用

12.get\_allocator() 返回双向队列的配置器

13.insert() 插入一个元素到双向队列中

语法:

iterator insert( iterator pos, size\_type num, const TYPE &val ); //pos前插入num个val值

void insert( iterator pos, input\_iterator start, input\_iterator end );

//插入从start到end范围内的元素到pos前面

// inserting into a deque
 #include <iostream>
 #include <deque>
 #include <vector>
 int main()
 {
 	std::deque<int> mydeque;
 	for (int i = 1; i<6; i++) mydeque.push_back(i); // 1 2 3 4 5
 	std::deque<int>::iterator it = mydeque.begin();
 	++it;
 	it = mydeque.insert(it, 10); //it指向2，在2的前面插入10// 1 10 2 3 4 5
 	mydeque.insert(it, 2, 20);//it此时指向10，在10前面插入2个20 // 1 20 20 10 2 3 4 5
 	it = mydeque.begin() + 2;//it指向第二个20。
 	std::vector<int> myvector(2, 30);//2个30构造
 	mydeque.insert(it, myvector.begin(), myvector.end());
 	//在第二个20前插入两个30 // 1 20 30 30 20 10 2 3 4 5
 	std::cout << "mydeque contains:";
 	for (it = mydeque.begin(); it != mydeque.end(); ++it)
 		std::cout << ' ' << *it;
 	std::cout << '\n';
 	system("pause");
 	return 0;
 }

14.max\_size() 返回双向队列能容纳的最大元素个数

15.pop\_back() 删除尾部的元素

16.pop\_front() 删除头部的元素

17.push\_back() 在尾部加入一个元素

18.push\_front() 在头部加入一个元素

19.rbegin() 返回指向尾部的逆向迭代器

20.rend() 返回指向头部的逆向迭代器

21.resize() 改变双向队列的大小

22.size() 返回双向队列中元素的个数

23.swap() 和另一个双向队列交换元素

语法：

void swap( deque &target );// 交换target和现双向队列中元素