一、deque工作原理：

deque容器内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据；中控器维护的每个缓冲区的地址，使得使用deque时像一片连续的内存空间，如下图所示：

二、deque构造函数：

1、功能描述：

deque容器构造

2、函数原型：

• dequedeqT;//默认构造函数

• deque(beg,end);//构造函数将[beg,end)区间中的元素拷贝给本身

• deque(n,elem);//构造函数将n个elem拷贝给本身

• deque(const deque &deq);//拷贝构造函数

  
  

代码应用：

#include <iostream>
0 Z* E: W/ _% g3 C6 L#include <deque>
using namespace std;
/ j1 k+ C4 u3 o( W# i' q. Evoid print(const deque<int>&d)
0 ^3 H- Z; \& {/ G) U# ^{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
* o  C$ v& I3 j( ~0 S. \       cout<<*it<<" ";
    }
& x+ [9 {/ @, {2 L# b    cout<<endl;
1 R$ w9 K& m7 }, D8 r3 v3 Z}
) W3 p( j9 P3 Y( R/ V- ]/ nvoid test()
! G9 B* p# e1 J* m5 }8 G{
8 l1 Z4 u  J. x* N6 Z    deque<int>d1;
, c4 a% L' w9 X0 N- D8 T) S    for(int i =0; i<10;i++)
    {
; y' b7 o9 g4 \+ L        d1.push_back(i);
    }
+ e+ w2 W; ?( s    print(d1);

( C# g  ]" b- O$ }    deque<int>d2(d1.begin(),d1.end());
" D; ^9 F; c, M    print(d2);
' t% T2 x/ |4 w; `
4 ^0 h5 i. v! N" g/ F2 h    deque<int>d3(10,100);
    print(d3);
1 G6 V; n7 r7 x' n$ H# n7 Z7 [" t3 D
% }- O) g2 D; S9 R( P$ v; e    deque<int>d4(d3);
; m" i: k: C1 ^' O' R& h    print(d4);

}
( E' _$ `) ?0 o- Kint main()
{
   test();
, G/ z  S8 f, K/ N, U}
- Z) T7 v2 X$ H- E* X0 v
' b9 s; z3 J2 z" A9 S

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
8 a# N5 ?8 Q! J* R, x& c0 1 2 3 4 5 6 7 8 9
( o9 E. N$ I; S$ Z8 g7 f0 1 2 3 4 5 6 7 8 9
! m9 ]* [$ d0 C# \. M3 l: N9 {* l100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

三、deque赋值操作：

1、功能描述：

给deque容器进行赋值

2、函数原型：

• deque operator=(const deque &deq);//重载等号操作符

• assign(beg,end);//将[beg,end)区间中的数据拷贝赋值给本身

• assign(n,elem);//将n个elem拷贝赋值给本身

  
  ( e* z3 u) m$ N8 D. O$ I

代码应用：

#include <iostream>
) F$ C; w* D: ]1 m#include <deque>
using namespace std;
void print(const deque<int>&d)
{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
       cout<<*it<<" ";
1 ]  M" z9 P5 y    }
' V9 h  @: x  k+ E0 ~" I    cout<<endl;
  b2 y/ D9 T4 q  D}
7 ^1 ?. B# C+ gvoid test()
; I/ ?3 y* S; y' m{
$ Z6 Y! Z+ [+ b3 M3 O7 [! a6 b/ G    deque<int>d1;
; f. ?7 Y8 k  l1 L    for(int i =0; i<10;i++)
    {
: H2 Z  ^- {: ]$ F) n        d1.push_back(i);
1 K/ L% h3 D8 i    }
8 E+ h  N; Q& `( x8 a    print(d1);
  B1 ^6 f) @% U
7 [) S7 ^4 v2 I+ ?    deque<int>d2;
    d2=d1;
    print(d2);

6 f: i- L8 ]7 ]& u6 w9 J& z( ?    deque<int>d3;
0 `  d/ q: w& _8 I  @5 Y5 j    d3.assign(d1.begin(),d1.end());
    print(d3);
+ y4 K3 B  T- c2 E; @9 ^+ T# A
    deque<int>d4;
2 s) V  b8 Y. p3 o    d4.assign(10,100);
5 E/ h' b8 u$ J; `    print(d4);
}
int main()
0 V' b" W4 u, C$ Y2 |1 }5 B4 m{
1 v" H- }5 U1 h. l   test();
% \1 V( _) t! b% X! G2 K2 f}

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
6 C$ X6 b  v6 e' {4 Z; e100 100 100 100 100 100 100 100 100 100

0 Z! d; z9 M& y6 ?0 u* _4 X. y6 h

四、deque大小操作：

1、功能描述：

对deque容器的大小进行操作

2、函数原型：

• deque.empty();//判断容器是否为空

• deque.size();//返回容器中的元素个数

• deque.resize(num)；//重新指定容器的长度num,若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除

• deque.resize(num,elem);//重新指定容器的长度num,若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除

  
  

代码应用：

#include <iostream>
#include <deque>
using namespace std;
void print(const deque<int>&d)
{
, c- x" S& _. Y* _9 X/ K2 K/ @    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
       cout<<*it<<" ";
    }
    cout<<endl;
}
* b5 E1 T' D+ V5 b  Y4 Z7 @9 Wvoid test()
5 w6 L. H& w. C: {2 M{
/ {$ A# z4 M8 z1 Y5 M& u8 l8 f    deque<int>d1;
    for(int i =0; i<10;i++)
: `( J$ |; Z( p7 w; Q    {
        d1.push_back(i);
, R* G5 s2 U* y: ]0 W: `# q1 H0 K    }
/ T7 N, H$ h$ x7 ?    print(d1);
1 L1 ~' x# P$ u* D
+ V; z7 M2 N6 G' z# M    if(d1.empty())
    {
, }; U9 x$ s6 ]+ r" E2 c      cout<<"d1 is empty"<<endl;
    }
    else
    {
: t6 m2 y- l, e( b$ o      cout<<"d1 is not empty"<<endl;
      cout<<"d1 is : "<<d1.size()<<endl;
    }

( a3 D1 P$ c. n. _    d1.resize(15,1);
; e* n6 t) \  c( b5 f    print(d1);

    d1.resize(5);
    print(d1);
}
7 E4 ^& L  r: A& d& n/ d) r. f" \int main()
, `4 q2 S1 ~/ a{
   test();
}

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
5 S$ n3 Q! d- M! h: L0 1 2 3 4 5 6 7 8 9
d1 is not empty
d1 is : 10
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1
0 1 2 3 4
1 k" Z1 K; J: X: M) U  M
- ?( ]3 o6 V* u: p: Y' I

注：deque没有容量的概念！

五、deque插入和删除：

1、功能描述：向deque容器中插入和删除数据

2、函数原型：

(1)两端插入操作：push_back(elem);//在容器尾部添加一个数据

• push_front(elem);//在容器头部插入一个数据
  " z+ |" n+ q5 ~8 K/ G: J5 C
  
  

• pop_back();//删除容器最后一个元素数据

• pop_front();//删除容器第一数据

  
    w; y7 p! q: q3 P8 W2 T

(2)指定位置操作：

• insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置

• insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值

• insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值

• clear();//清空容器的所有数据

• erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置

• erase(pos);//删除pos位置的数据，返回下一个数据的位置

  
  . W& _! ~! T/ @0 @' K, S

两端代码应用：

#include <iostream>
. q& K' k- I% v( ~% O#include <deque>
2 p! l6 K1 W# P. Lusing namespace std;
( c3 `  S* q" `void print(const deque<int>&d)
5 p& T& O6 _; K3 L{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
       cout<<*it<<" ";
    }
    cout<<endl;
}
8 c& |$ O2 h+ @; v# w8 _void test()
{
    deque<int>d1;
   /* for(int i =0; i<10;i++)
    {
# I3 D$ y1 c3 Y. `8 J        d1.push_back(i);
    }
. ?# |- R5 ?, V  P/ Z# ]( L    print(d1);*/
7 x/ P% p3 _. C& p& @    d1.push_back(10);
    d1.push_back(20);

    d1.push_front(100);
: K$ ]' `4 b9 J& Y7 Z1 {    d1.push_front(200);

8 e$ U- d: F$ S  b    print(d1);

3 X- @. E, d+ Q% i+ I' X2 j    d1.pop_back();
" d5 ]: B; h2 j5 l5 B: q    print(d1);

$ x# X/ B% m5 R! ?    d1.pop_front();
    print(d1);
( }, }4 y( K6 X. Q
, F( m* y3 y4 H9 ?, o}
int main()
{
4 l) u+ g1 ?  A+ h* {" X4 u   test();
}

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
% w5 A% P9 K4 M) C200 100 10 20
5 K& q( a5 y6 v7 u& a200 100 10
" e( C0 Z7 ?1 \: i* O0 k" X100 10
, t- |' B- Q" O, V

代码应用：

#include <iostream>
#include <deque>
' z3 t  x4 l5 a  u2 Uusing namespace std;
void print(const deque<int>&d)
$ U% @) `6 s- L  |{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
  A* D& N* C1 \    {
       cout<<*it<<" ";
* I+ M: @: ]2 B. w* X    }
* x8 [; ?- u7 D1 J) ~6 P: B    cout<<endl;
}
- H7 d3 Y, B$ N; ~! g2 ?void test()
5 g$ q# Z; b2 p{
0 q! [/ }  L# h* v  ]! ^    deque<int>d1;
   /* for(int i =0; i<10;i++)
    {
# ^* {0 L/ i! F1 a% X/ x        d1.push_back(i);
    }
    print(d1);*/
    d1.push_back(10);
4 D. E! j4 g1 r; d! E    d1.push_back(20);
    d1.push_front(100);
    d1.push_front(200);
    print(d1);
    d1.insert(d1.begin(),1000);
5 y' x! X: s8 J  f1 s- h    print(d1);

    d1.insert(d1.begin(),2,10000);
- J  T$ U% U/ q8 a( V# `- D; {    print(d1);
    deque<int>d2;
    d2.push_back(1);
    d2.push_back(2);
    d2.push_back(3);

    d1.insert(d1.begin(),d2.begin(),d2.end());
    print(d1);
* Z) n, V+ S% A5 N- b8 x8 B' M}

- e4 s% n( @3 |( C5 ]int main()
1 l  K( l2 q+ `! W. p9 [: ]{
$ v9 R  Z) p( ~5 |   test();
1 g& ]5 \& X& b- M* }' N}

+ a& S, g$ X% }2 g4 q7 p2 g

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
200 100 10 20
1000 200 100 10 20
10000 10000 1000 200 100 10 20
5 @5 a9 ^7 n/ c7 F1 2 3 10000 10000 1000 200 100 10 20
7 Y) w# S/ _# A' m

代码应用：

#include <iostream>
9 J4 @5 W) M) q: q1 h/ h#include <deque>
using namespace std;
void print(const deque<int>&d)
3 E* O- Z4 i+ ~/ }* H: i{
( C# o/ A' ?4 j8 `. j    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
       cout<<*it<<" ";
2 n, N4 a  y1 `0 O$ Q    }
' Q8 F5 P, Y8 [  z7 g2 K    cout<<endl;
}
void test()
$ g2 K. u! r# H: |- b% ^{
    deque<int>d1;
+ a8 `" |* e0 f! L4 x# F9 q. n   /* for(int i =0; i<10;i++)
    {
        d1.push_back(i);
    }
    print(d1);*/
  e" C6 v8 O, r+ |- G- J    d1.push_back(10);
    d1.push_back(20);
    d1.push_front(100);
    d1.push_front(200);
- b$ }* F7 J- j* s" I- t    print(d1);
3 u$ N$ G% C+ q1 M1 b
    deque<int>::iterator it = d1.begin();//d1.erase(d1.begin())
: m8 h" `4 ^" D" f$ A* Q    it++;
    d1.erase(it);
    print(d1);
1 w! ^: P! I' I& M6 J
    d1.erase(d1.begin(),d1.end());
" S, q, T6 r% `( d! Y    print(d1);
- p; J1 U2 W/ D( l
3 P) s& @1 _# a* w    d1.clear();
    print(d1);
}

6 g1 \# K# f% [/ O; d! N0 Xint main()
( ?  t$ }7 J7 X/ Z) h, }0 S{
   test();
}
; u+ Z/ m( z/ L& i; A8 C# o+ E4 U, G
7 g0 W% }% o& J+ q+ R8 X4 a

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
200 100 10 20
200 10 20

+ c/ l- e4 p1 k. C' p/ @

六、deque数据存取：

1、功能描述：

对deque容器中的数据存取操作

2、函数原型：

• at(int idx);//返回索引idx所指的数据

• operator[];//返回索引idx所指的数据

• front();//返回容器中第一个元素

• back();//返回容器中最后数据元素

  
  & ^( h1 t. D' o7 ~' @/ W: s

代码应用：

#include <iostream>
  D& q# H1 l2 k  ^- y3 V- s' d3 y8 F#include <deque>
9 y3 q! D: p; F2 {using namespace std;
/ m& \+ L+ a) f3 @void print(const deque<int>&d)
{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
- i- Z1 ^: P/ r3 S- u       cout<<*it<<" ";
7 r" v5 H9 v% d2 i, ^    }
  t1 Z/ o% i& j7 P8 A: ~    cout<<endl;
2 F0 h' }2 f$ i$ \7 o}
void test()
{
: w( p0 B+ F  P3 [+ R    deque<int>d1;

! g7 x4 e! K! k, R" b& t" C% {+ z7 a    d1.push_back(10);
    d1.push_back(20);
    d1.push_front(100);
) [* R6 W2 x. q    d1.push_front(200);
( x4 }, X- t6 m   
  j. e/ B& j; f0 `3 K    for(int i =0; i<d1.size();i++)
& J/ w" w5 n5 ^& Y/ F    {
# x( q! j& l& m* p1 a) Z$ D# f        cout<<d1<<" ";
    }
    cout<<endl;
6 P% E# F5 g' ^- \- X$ l- e0 B
1 K  c% _, l8 S  P% c    for(int i=0;i<d1.size();i++)
( c' Y4 x0 Z! F$ X  J# g: c    {
2 ]! a. o: N* }       cout<<d1.at(i)<<" ";
    }
    cout<<endl;
! O5 L4 N$ h4 H% z: Z0 t- n3 @
8 n" N( [* O4 b; V8 E& z    cout<<"the first is : "<<d1.front()<<endl;
4 M, [, |6 m- U1 j, d% v+ Z2 g    cout<<"the last is : "<<d1.back()<<endl;
}
0 k1 c/ O; _7 m/ F* q
int main()
. y0 O& s4 x, O# }  Y{
( q: F$ v, s* l" @* m   test();
}
! G) T; U  M% J9 K' B% G7 ?9 t
+ c+ X' x3 x) x! Y9 T" ^' @, Q, S

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
3 V# V8 `' P; x! o200 100 10 20
200 100 10 20
the first is : 200
" v; b8 J! J. ]- _0 Mthe last is : 20
  k; }2 b* _3 R$ c

七、deque排序：

1、功能描述：

利用算法实现对deque容器进行排序

2、算法：

sort(iterator beg,iterator end);//对beg和end区间元素进行排序

代码应用：

#include <iostream>
#include <deque>
8 F; s' D, n- J, c% }$ @3 [% N#include <algorithm>
using namespace std;
( w/ |* m+ H4 F3 u1 uvoid print(const deque<int>&d)
{
7 n+ R* v( s; `" g5 j5 `( P$ ]3 X9 J    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
       cout<<*it<<" ";
: @$ a& h: Y' Q/ b2 B& H    }
    cout<<endl;
}
. ~" Y$ [5 ^9 m3 m! Pvoid test()
{
    deque<int>d1;
! P4 G4 R2 M6 m) l# J
    d1.push_back(10);
    d1.push_back(20);
8 X0 H+ \% C$ U& C* ^    d1.push_front(100);
$ w/ L( q8 f3 w# V9 }; U    d1.push_front(200);

6 f& B! \5 y' n# r9 C    print(d1);
    sort(d1.begin(),d1.end());
5 A, S& ~6 b, n3 _, s    print(d1);
}
( b0 y/ o1 B5 ~! T
* r# x$ F) E9 N& l; J8 B+ iint main()
' Y1 M. f! A  S4 x6 D{
   test();
) l( \9 U) w+ m: |* T}
# U; G8 h' d0 H' J$ z1 K

结果输出：

root@txp-virtual-machine:/home/txp/test2# ./a.out
/ q0 {$ z( p) S! a% }6 D; x200 100 10 20
10 20 100 200
; X; q; y) ?; \& U5 v, Z3 Z' X5 T