c++ stl deque容器

c++中,Deque容器和vector相似,deque内部也采用动态数组来管理元素,支持随机存取。。头文件<deque>

1.deque和vector的不同之处:

1)两端都可以较快速地按插元素和删除元素,而vector只能在尾端进行

2)在对内存有所限制的系统中,deque可以包含更多的元素,因为它不止一块内存。因此deque的max_size()可能更大

3)deque不支持对容量和内存的重分配时机的控制。

4)deque的内存区块不再被使用时,会被释放。deque的内存大小是可缩减的,由实作版本定义。

2.和vecotr差不多的特性:

1)在中端部分按插、移除元素的速度相对较慢。

2)迭代器属于random access iterator(随机存取迭代器)

3.deque的常用函数:

1)构造函数

deque<T> c

deque<T> c(n) 产生一个deque,含有n个元素,这些元素均以default构造函数产生

deque<T> c(n,elem)  产生一个含有n个值都是elem的deque

deque<T> c(c2)    c2中的所有元素都被拷贝来初始化c

deque<T> c(beg,end) 以[beg,end]内的元素为初值

2)非变动性操作:

c.size()   实际元素个数

c.empty()   判空

c.max_size()  返回容器所能容纳的最大元素数量

c1 ==c2

c1 !=c2

c1 <c2

c1 <=c2

c1 >c2

c1 >=c2

c.at(idx) 返回索引idx的元素,如果idx越界,会抛出out_of_range

c[idx]  和vector一样,deque支持下标操作,

c.front()  返回第一个元素,不检查元素是否存在

c.back() 返回最后一个元素,不检查元素是否存在

c.begin()   f返回一个随机迭代器,指向第一个元素

c.end()  返回一个随机迭代器,指向最后一个元素

c.rbegin()   返回一个逆向迭代器,指向逆向迭代时的第一个元素

c.rend() 返回一个逆向迭代器,指向逆向迭代时的第一个元素

3)deque的变动性操作:

c1 =c2  将c2的所有元素赋值给c1

c.assign(n,elem) 将n个elem副本赋值给c

c.assign(beg,end)  将区间[beg,end]中的元素赋值给c

c1.swap(c2) 将c1和c2的元素互换

swap(c1,c2)  同上,全局函数

c.insert(pos,elem)  在pos位置插入元素elem,并返回新元素的位置

c.insert(pos,n,elem)  在pos位置插入elem的n个副本,无返回值

c.insert(pos,beg,end)  在pos位置插入在区间[beg,end]所有元素的副本,无返回值

c.push_back(elem)  z在尾部插入elem

c.push_front(elem)  在头部插入elem

c.pop_back()  移除最后一个元素

c.pop_front()  移除头部元素

c.erase(pos)  移除pos位置上的元素,返回下一个元素位置

c.erase(beg,end)  移除[beg,end]内的所有元素,返回一个元素位置

c.resize(num)  将大小(元素个数)改为num,如果size()增长了,新增元素都以default构造函数产生出来

c.resize(num,elem)  将大小(元素个数)改为num。如果size()增长了,新增的元素都是elem的副本

c.clear()   移除所有元素,将容器清空

deque和vector不同的操作

1)deque不提供容量操作(capacity()和reserve())

2)deque直接提供函数,用以完成头部元素的安插和删除(push_front()和pop_front())

deque除了在头部和尾部插入元素,pointers和references仍然有效外,在其他地方插入和删除元素,都会使指向deque元素的pointers,references和iterators失效。

实例:


#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
deque<string> dq;
dq.assign(3,"string");
dq.push_back("last string");
dq.push_front("first string");

copy(dq.begin(),dq.end(),ostream_iterator<string>(cout,"\n"));
cout <<endl;

dq.pop_front();
dq.pop_back();

for (int i =1; i < dq.size(); ++i)
dq[i] = "another" +dq[i];

dq.resize(4,"resized string");

copy(dq.begin(),dq.end(),ostream_iterator<string>(cout,"\n"));
}

输出:

first string
string
string
string
last
string

string
anotherstring
anotherstring
resized
string
实例2:


#include <iostream>
#include <deque>
using namespace std;

int main()
{
deque <char > dq,dq2;

cout << "deque push_back()后插法:";
for (int i =0; i <26; i++)
dq.push_back(‘a‘+i);
for (int i =0; i < dq.size(); i++)
cout << dq[i] << ‘ ‘;
cout <<endl;

cout << "deque push_front()前插法:";
for (int i =0; i <26; i++)
dq2.push_front(‘a‘+i);
for (int i =0; i < dq2.size(); i++)
cout << dq2[i] << ‘ ‘;
cout <<endl;

deque<char> dq3(dq2);
deque<char>::iterator it;

cout << "用dq2初始化dq3:";
for (it =dq3.begin(); it !=dq3.end(); ++it)
cout << *it << ‘ ‘;
cout <<endl;

deque<char> dq4(10,*(dq3.begin()));

cout << "dp4(10,*(dp3.begin())): ";
for (it =dq4.begin(); it !=dq4.end(); ++it)
cout << *it << ‘ ‘;
cout <<endl;

deque<char> dq5(dq.begin()+4,dq.begin()+14);

cout << "dp5(dp.begin()+4,dq.begin()+14): ";
for (it =dq5.begin(); it !=dq5.end(); ++it)
cout << *it << ‘ ‘;
cout <<endl;

cout << "dq5.size()= "<<dq5.size() <<endl;
cout << "dq5.max_size() = " <<dq5.max_size() <<endl;

dq5.assign(5,*(dq.begin()));
cout << "dq5.assign(5,*(dq.begin()))(会清空旧的元素): ";
for (it =dq5.begin(); it !=dq5.end(); ++it)
cout << *it << ‘ ‘;
cout << endl;

dq5.assign(dq.begin()+7,dq.begin()+17);
cout << "dp5.assign(dq.begin()+7,dq.begin()+17):";
for (it =dq5.begin(); it !=dq5.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq5.swap(dq4);
cout << "dq5.swap(dq4):"<<endl;
cout << "dq4:" ;
for (it =dq4.begin(); it !=dq4.end();++it)
cout << *it << ‘ ‘;
cout <<endl;
cout << "dq5:";
for (it =dq5.begin(); it !=dq5.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq5.insert(dq5.begin()+2,5,*(dq.begin()));
cout << "dq5.insert(dq5.begin()+2,5,*(dq.begin())):";
for (it =dq5.begin(); it !=dq5.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq4.insert(dq4.begin()+2,dq.begin(),dq.begin()+3);
cout << "dq4.insert(dq4.begin()+2,dq.begin(),dq.begin()+3):";
for (it =dq4.begin(); it !=dq4.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq.pop_front();
cout <<"dq.pop_front()删除头元素:";
for (it =dq.begin(); it !=dq.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq.pop_back();
cout << "dq.pop_back()删除尾元素:";
for (it =dq.begin(); it !=dq.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq.erase(dq.begin()+3,dq.end()-3);
cout << "dq.erase(dq.begin()+3,dq.end()-3):";
for (it =dq.begin(); it !=dq.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

dq.resize(10,*(dq.begin()));
cout << "dq.resize(10,*(dq.begin())):";
for (it =dq.begin(); it !=dq.end();++it)
cout << *it << ‘ ‘;
cout <<endl;

cout << "dq.size()=" <<dq.size() <<endl;
cout << "dq.max_size() =" << dq.max_size() <<endl;

cout << "dq.clear()前dq.empty()= "<< dq.empty() <<endl;
dq.clear();
cout << "dq.clear()后dq.empty()=" << dq.empty() <<endl;

return 0;
}

输出:

deque push_back()后插法:a b c d e f g h i j k l m n o p q r s t u v w x y z

deque push_front()前插法:z y x w v u t s r q p o n m l k j i h g f e d c b a

用dq2初始化dq3:z y x w v u t s r q p o n m l k j i h g f e d c b a

dp4(10,*(dp3.begin())): z z z z z z z z z z

dp5(dp.begin()+4,dq.begin()+14): e f g h i j k l m n
dq5.size()=
10
dq5.max_size() = 4294967295
dq5.assign(5,*(dq.begin()))(会清空旧的元素): a a a
a a
dp5.assign(dq.begin()+7,dq.begin()+17):h i j k l m n o p q

dq5.swap(dq4):
dq4:h i j k l m n o p q
dq5:z z z z z z z z z z

dq5.insert(dq5.begin()+2,5,*(dq.begin())):z z a a a a a z z z z z z z z

dq4.insert(dq4.begin()+2,dq.begin(),dq.begin()+3):h i a b c j k l m n o p q

dq.pop_front()删除头元素:b c d e f g h i j k l m n o p q r s t u v w x y z

dq.pop_back()删除尾元素:b c d e f g h i j k l m n o p q r s t u v w x y

dq.erase(dq.begin()+3,dq.end()-3):b c d w x y

dq.resize(10,*(dq.begin())):b c d w x y b b b b

dq.size()=10
dq.max_size() =4294967295
dq.clear()前dq.empty()=
0
dq.clear()后dq.empty()=1

c++ stl deque容器,码迷,mamicode.com

时间: 04-29

c++ stl deque容器的相关文章

浅谈C++ STL deque 容器

浅谈C++ STL deque 容器 本篇随笔简单介绍一下\(C++STL\)中\(deque\)容器的使用方法及常见使用技巧. deque容器的概念 \(deque\)的意义是:双端队列.队列是我们常用而且必须需要掌握的数据结构.\(C++STL\)中的确有模拟队列的模板:#include<queue>中的\(queue\)和\(priority\_queue\).队列的性质是先进先出,即从队尾入队,从队首出队.而\(deque\)的特点则是双端进出,即处于双端队列中的元素既可以从队首进/出

c++ STL deque容器成员函数

deque是双向队列,即可以在头部插入删除,也可以在尾部插入删除.内部并不连续,这一点和vector并不一样.可能第1个元素和第2个元素的地址是不连在一起的.在使用时用it迭代器会安全一点. 这是c++ 98标准的,不是c++11的.11标准新加的函数没在这里说明.里面大部分函数是经过测试的才得出的结论. 函数(下面将iterator简化为it) 描述 Void c.assign(it beg,it end)void c.assign(it n,元素类型  elem) 将拷贝[beg; end)

STL学习三:deque容器

1.Deque简介 deque是“double-ended queue”的缩写,和vector一样都是STL的容器,deque是双端数组,而vector是单端的. deque在接口上和vector非常相似,在许多操作的地方可以直接替换. deque可以随机存取元素(支持索引值直接存取, 用[]操作符或at()方法,这个等下会详讲). deque头部和尾部添加或移除元素都非常快速.但是在中部安插元素或移除元素比较费时. 2.deque对象的默认构造 deque采用模板类实现,deque对象的默认构

带你深入理解STL之Deque容器

在介绍STL的deque的容器之前,我们先来总结一下vector和list的优缺点.vector在内存中是分配一段连续的内存空间进行存储,其迭代器采用原生指针即可,因此其支持随机访问和存储,支持下标操作符,节省空间.但是其在分配的内存不够的情况下,需要对容器整体进行重新分配.拷贝和释放等操作,而且在vector中间插入或删除元素效率很低. 而list是以节点形式来存放数据,使用的是非连续的内存空间来存放数据,因此,在其内部插入和删除元素的时间复杂度都是O(1),但是其不支持随机访问和存取,不支持

STL之deque容器的实现框架

说明:本文仅供学习交流,转载请标明出处,欢迎转载! vector底层采用的是一个数组来实现,list底层采用的是一个环形的双向链表实现,而deque则采用的是两者相结合,所谓结合,并不是两种数据结构的结合,而是某些性能上的结合.我们知道,vector支持随机访问,而list支持常量时间的删除,deque支持的是随机访问以及首尾元素的删除. deque是double ended queue的缩写,读作deck.首先我们用一个图来说明deque底层所采用的数据结构. 这个数据结构有一种似曾相识的感觉

STL学习系列三:Deque容器

1.Deque简介 deque是“double-ended queue”的缩写,和vector一样都是STL的容器,deque是双端数组,而vector是单端的. deque在接口上和vector非常相似,在许多操作的地方可以直接替换. deque可以随机存取元素(支持索引值直接存取, 用[]操作符或at()方法,这个等下会详讲). deque头部和尾部添加或移除元素都非常快速.但是在中部安插元素或移除元素比较费时. 2.deque对象的默认构造 deque采用模板类实现,deque对象的默认构

STL顺序容器【vector】【deque】【list】

我们都知道,stl容器中将容器分为两类,顺序容器和关联容器. 顺序容器有三种即vector,deque,以及list 一:顺序容器的常用操作 1:首先顺序容器的迭代器 定义:T<C>::iterator iter; /*支持所有顺序容器*/ *iter返回迭代器的引用 iter->mem 对iter解引用,等效于(*iter).men ++iter|iter++自加 --iter|iter--自减 iter1==iter2  |  iter1!=iter2比较 /*只支持vector 和

C++——STL之vector, list, deque容器对比与常用函数

STL 三种顺序容器的特性对比: vector 可变数组,内存空间是连续的,容量不会进行缩减.支持高效随机存取,即支持[]和at()操作.尾部插入删除效率高,其他位置插删效率较低: list 双向链表,内存空间可不连续,不支持随机存取.插入和删除的效率很高: deque  双端队列,内存空间是多个连续的内存块,在一个映射结构中保存对这些块以及顺序的跟踪,可利用的内存更大,且内存大小是可以自动缩减的.支持随机存取,但是随机存取性能没有vector 好.首尾插入效率高,其他位置插删效率低: 使用注意

c++STL容器之deque容器

deque是双端数组. deque和vector的区别: vector对于头部的插入和删除效率低,数据量越大,效率越低: deque相对于而言,对头部的插入和删除比vector快: vector访问元素时速度比deque快,这和两者的内部实现有关: deque内部工作原理: deque内部有个中控器,维护每段缓冲区中的内容,缓冲区中存放着真实数据.中控器维护的是每个缓冲区的地址,使得使用每个deque时像一块连续的内存空间. deque容器的迭代器是支持随机访问的. 一.deque构造函数 de