首页 > 代码库 > c++ stl deque容器

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