目录

deque的实现原理

deque

1. deque的初始化

2. deque的赋值操作

3. deque的大小操作

4. deque双端插入和删除操作

5. deque数据存取操作

6. deque的insert操作

7. deque的删除操作


        上一章节,小编已经讲了vector容器,它就是一个桶,所有添加新的数值都是在一端进行操作(其实也可以从开头操作,不过太麻烦了,反正我是无法接受的,嘿嘿嘿~)。而且vector容器申请到的内存是连续的空间。

        在这一节中,小编偷偷告诉你还有另外一种容器,它也是连续线性空间的,但是它的特点是双向开口,就是说它不像vector一样只开一个口,它有两个,它长如下的形状,它可以在尾部进行插入和删除元素,也可以在头部添加和删除元素。

deque的实现原理

        从逻辑上来讲,deque容器的元素存放是连续线性的内存空间,说到了连续、线性,你是不是想到了vector、array了,是的,vector和array的元素存放也是连续和线性的,虽然vector可以自动扩容,但是只能向尾端生长,这个生长从实现原理的角度上看是三个步骤:(1)申请更大的内存空间;(2)将原来容器中的数据拷贝到新的容器空间;(3)释放原来的容器空间。因为vector每一次扩容都是原本容器空间的n倍,不会只扩容一个空间,因为要是这么做的话那设计者也太蠢了,代价太大了,不值得。

        deque是由一段一段的定量的连续空间构成,当再增加新空间而不足的时候,会配置一段连续的定量空间,串联在deque的头端或者尾端。deque这样做的好处就是避免了vector的那三个步骤,即开启新空间,拷贝数据,释放旧空间的轮回,但是呢,有优点就会有缺点,deque的缺点就是维护扩容后的迭代器架构。

        deque的结构就是一个中控器和一个缓冲区,中控器就是采取所谓的map(这里的map不是STL容器里面的map)作为主控,这里所谓的map就是一小块连续的内存空间,这段空间里面的每一个元素(可以看成是一个结点)都是一个指针,指向另外一段连续的内存空间,叫做缓冲区。这里的缓冲区才是deque的主体。

        底层实现原理就是一个二维数组,第一维用来存放中控区,第二维用来存放缓冲区的数据。

deque

    如果你要使用deque容器,那么需要添加头文件

# include<deque>

1. deque的初始化

// deque<T> deqT;//默认构造形式
// deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
// deque(n, elem);//构造函数将n个elem拷贝给本身。
// deque(const deque &deq);//拷贝构造函数。
  
  
int arrays[7] = {1,2,3,4,5,6,7};
deque<int> serven_1;                   // 创建一个空容器
deque<int> serven_2(arrays, arrays + sizeof(arrays)/sizeof(arrays[0]));      // 构造函数,将[begin,end)拷贝给serven_2
deque<int> serven_3(serven_2);         // 拷贝构造函数,将serven_2拷贝给serven_3
deque<int> serven_4(5,3);              // 将创建5个3给容器serven_4
​
cout<<"serven_2的数值为:";
iterator_deque_show(serven_2);

运行结果:

2. deque的赋值操作

  • assign():赋值函数,赋值后将把原来的容器deque覆盖了;

  • ser1. swap(ser2):ser1和ser2交换;

  • operator=:重写了operator进行赋值;

// assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
// assign(n, elem);//将n个elem拷贝赋值给本身。
// deque& operator=(const deque &deq); //重载等号操作符
// swap(deq);// 将deq与本身的元素互换
​
/* deque的赋值操作 */
serven_4.assign(arrays, arrays + sizeof(arrays)/sizeof(arrays[0]));
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4.assign(5,6);
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4.assign(serven_3.begin(), serven_3.end());
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4 = serven_2;
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4.swap(serven_3);
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);

运行结果:

3. deque的大小操作

  • size():返回deque容器的大小,也就是容器中元素的个数;

  • empty():返回deque是否为空,空的话返回1;

  • resize(n):容器deque重新确定大小;

  • resize(n,val):容器重新确定大小后,超过的部分就填充val。​

// deque.size();//返回容器中元素的个数
// deque.empty();//判断容器是否为空
// deque.resize(num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
// deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。
​
/* deque的大小操作 */
serven_4.assign(arrays, arrays+sizeof(arrays)/sizeof(int));
​
cout<<"serven_4的大小:"<<serven_4.size()<<endl;
cout<<"serven_4是否为空:"<<serven_4.empty()<<endl;
​
serven_4.resize(3);
cout<<"serven_4的大小为:"<<serven_4.size()<<endl;
​
serven_4.resize(9);
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4.resize(12,8);
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);

运行结果:

4. deque双端插入和删除操作

  • push_back(val):向容器的尾端添加元素val;

  • push_front(val):向容器的头端添加元素val;

  • pop_back():容器的尾端删除元素;

  • pop_front():容器的头端删除元素。

    // push_back(elem);//在容器尾部添加一个数据
    // push_front(elem);//在容器头部插入一个数据
    // pop_back();//删除容器最后一个数据
    // pop_front();//删除容器第一个数据
    ​
    ​
    /* deque的插入和删除操作 */
    serven_4.assign(arrays, arrays+sizeof(arrays)/sizeof(int));
    ​
    cout<<"serven_4的数值为:";
    iterator_deque_show(serven_4);
    ​
    serven_4.push_back(9);
    cout<<"serven_4在尾端添加9:";
    iterator_deque_show(serven_4);
    ​
    serven_4.push_front(4);
    cout<<"serven_4在头端添加4:";
    iterator_deque_show(serven_4);
    ​
    serven_4.pop_back();
    cout<<"serven_4删掉尾端元素:";
    iterator_deque_show(serven_4);
    ​
    serven_4.pop_front();
    cout<<"serven_4删掉头端元素:";
    iterator_deque_show(serven_4);

    运行结果:

5. deque数据存取操作

  • ser.at(i):获取第i个位置的数值,如果i越界会有越界异常抛出;

  • operator[i]:获取第i个位置的数值,越界了不抛出异常;

  • front():获取容器的首位置的数值;

  • back():获取容器的末尾数值。​

// at(idx);//返回索引idx所指的数据,如果idx越界,抛出out_of_range。
// operator[];//返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
// front();//返回第一个数据。
// back();//返回最后一个数据
​
  /* deque容器元素的获取 */
  serven_4.assign(arrays, arrays+sizeof(arrays)/sizeof(int));
​
  cout<<"serven_4第二个位置的元素为:"<<serven_4.at(1);
  cout<<"serven_4第二个位置的元素为:"<<serven_4[1];
  cout<<"serven_4第一个位置的元素为:"<<serven_4.front();
  cout<<"serven_4第一个位置的元素为:"<<serven_4.back();

运行结果:

6. deque的insert操作

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

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

  • insert(pos, beg, end):在pos插入[beg,end)区间的数据,无返回值。

// insert(pos,elem);//在pos位置插入一个elem元素的拷贝,返回新数据的位置。
// insert(pos,n,elem);//在pos位置插入n个elem数据,无返回值。
// insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据,无返回值。
​
serven_4.assign(arrays, arrays+sizeof(arrays)/sizeof(int));
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4); 
​
serven_4.insert(serven_4.begin()+0,5);
cout<<"serven_4第一个位置插入0元素为:";
iterator_deque_show(serven_4);
​
serven_4.insert(serven_4.begin()+1,2,8);
cout<<"serven_4第二个位置插入2个8元素为:";
iterator_deque_show(serven_4);
​
serven_4.insert(serven_4.begin()+6,arrays, arrays+4);
cout<<"serven_4第七个位置插入数组arrays的前4个元素为:";
iterator_deque_show(serven_4);

运行结果:

7. deque的删除操作

  • clear():清空所有元素;

  • erase(beg, end):擦除区间[begin,end)的数据;

  • erase(pos): 删除位置pos的数据。

// clear();移除容器的所有数据
// erase(beg,end);删除[beg,end)区间的数据,返回下一个数据的位置。
// erase(pos); 删除pos位置的数据,返回下一个数据的位置。
​
​
/* deque 的删除操作 */
serven_4.assign(arrays, arrays+sizeof(arrays)/sizeof(int));
cout<<"serven_4的数值为:";
iterator_deque_show(serven_4);
​
serven_4.erase(serven_4.begin()+0);
cout<<"删除容器第一个位置元素:";
iterator_deque_show(serven_4);
​
serven_4.erase(serven_4.begin(),serven_4.begin()+2);
cout<<"删除容器前两个元素:";
iterator_deque_show(serven_4);
​
serven_4.clear();
cout<<"容器清空:"<<serven_4.empty()<<endl;

运行结果:

​欢迎关注微信公众号 “三贝勒文子” , 每天学习一点C++

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐