• 双端队列(Deque)


    一、简介

            deque,即双端队列(double ended queue),是一种可以在两端扩展或收缩的序列化容器。

            deque是C++ 标准模板库的一部分,想要使用deque,需要在程序中包含头文件deque。

    #include
    

    二、定义和初始化

    1.格式:

            包含头文件deque之后,我们可以使用下边的格式定义deque:

    std::deque variable_name;
    

        object_type规定了deque中可以存放哪种类型的元素。
        variable_name为deque名。

    2.方法:

    1. deque v1; //v1是一个空deque,可存储元素类型为T,执行默认初始化
    2. deque v2(v1); //v2中包含v1中的所有元素
    3. deque v2=v1; //等价于v2(v1)
    4. deque v3(n,value); //v3中有n个元素,并且值都为value
    5. deque v4(n); //v4包含了n个重复执行了值初始化的对象
    6. deque v5{a,b,c...}; //v5包含大括号中的所有元素
    7. deque v6={a,b,c...} //等价于v5{a,b,c....}

    三、迭代器

    1.deque中的迭代器

    deque.begin():指向deque首个元素。
    deque.end():指向deque尾元素的下一个位置。
    deque.rbegin():指向deque尾元素的反向迭代器,即rbegin()指向尾元素,rbegin-1指向倒数第二个元素。
    deque.rend():指向deque头元素前一个位置的反向迭代器,即rend()指向头元素前一个位置元素,rbegin-1指向第一个元素
    deque.cbegin():指向deque首元素,与begin()相同。增加了const属性,不能用于修改元素。
    deque.cend():指向deque尾元素下一个位置,与end()相同。增加了const属性,不能用于修改元素。
    deque.crbegin():指向deque尾元素的反向迭代器,与rbegin()相同。增加了const属性,不能用于修改元素。
    deque.crend():指向deque头元素前一个位置的反向迭代器,与rend()相同。增加了const属性,不能用于修改元素。

    2.示例代码

    1. #include
    2. #include
    3. using namespace std;
    4. int main()
    5. {
    6. deque<int> test={1,2,3,4};
    7. cout<<"初始化后deque为:";
    8. for(auto num:test)
    9. {
    10. cout<" ";
    11. }
    12. cout<
    13. deque<int>::iterator begin_iterator = test.begin();
    14. cout<<"begin() 指向的元素:"<<*begin_iterator<
    15. auto end_iterator = test.end();
    16. cout<<"end()-1 指向的元素:"<<*(end_iterator-1)<
    17. auto rbegin_iterator = test.rbegin();
    18. cout<<"rbegin() 指向的元素:"<<*rbegin_iterator<
    19. auto rend_iterator = test.rend();
    20. cout<<"rend()-1 指向的元素:"<<*(rend_iterator-1)<
    21. deque<int>::const_iterator cbegin_iterator=test.cbegin();
    22. cout<<"cbegin() 指向的元素:"<<*cbegin_iterator<
    23. deque<int>::const_iterator cend_iterator=test.cend();
    24. cout<<"cend()-1 指向的元素:"<<*(cend_iterator-1)<
    25. auto crbegin_iterator=test.crbegin();
    26. cout<<"crbegin() 指向的元素:"<<*crbegin_iterator<
    27. auto crend_iterator=test.crend();
    28. cout<<"crend()-1 指向的元素:"<<*(crend_iterator-1)<
    29. return 0;
    30. }

    输出:

    初始化后deque为:1 2 3 4

    begin() 指向的元素:1

    end()-1 指向的元素:4

    rbegin() 指向的元素:4

    rend()-1 指向的元素:1

    cbegin() 指向的元素:1

    cend()-1 指向的元素:4

    crbegin() 指向的元素:4

    crend()-1 指向的元素:1

    四、deque成员使用方法 

    (1) size()——元素个数

            要想知道deque中有多少元素,就需要使用deque.size()。它的作用是返回deque中元素的个数。

    1. int main()
    2. {
    3. deque<int> mydeque={2,3};
    4. cout<<"添加元素前mydeque.size() = "<size()<
    5. mydeque.push_front(5);
    6. mydeque.push_back(1);
    7. cout<<"添加元素后mydeque.size() = "<size()<
    8. }

    输出:

    添加元素前mydeque.size() = 2
    添加元素后mydeque.size() = 4 


     (2)max_size()——最多能容纳元素个数:

            要想知道deque最多可以有多少元素,就需要使用deque.max_size()。它的作用是返回deque中最多能容纳元素个数(一般情况下不会使用到这个)。

    1. int main()
    2. {
    3. deque<int> mydeque={2,3};
    4. cout<<"mydeque最多可容纳元素个数尾max_size() = "<max_size()<
    5. }

    输出:

    mydeque最多可容纳元素个数尾max_size() = 2305843009213693951


     (3) resize(n)——改变deque大小为n

            如果想要改变deque的size,则使用deque.resize(n),将deque的size改为n。

    1. int main()
    2. {
    3. deque<int> mydeque={1,2};
    4. mydeque.resize(5);
    5. cout<<"第一次resize后deque中元素为";
    6. for(auto a:mydeque)
    7. {
    8. cout<" ";
    9. }
    10. cout<
    11. mydeque.resize(1);
    12. cout<<"第二次resize后deque中元素为:";
    13. for(auto a:mydeque)
    14. {
    15. cout<" ";
    16. }
    17. }

    输出:

    第一次resize后deque中元素为:1 2 0 0 0
    第二次resize后deque中元素为:1


     (4) empty()——判断deque是否为空

            empty()是用来判断deque中是否有元素的。如果有元素,就返回false;如果没有元素,就返回true。即为空返回true,非空返回false。

    1. int main()
    2. {
    3. deque<int> mydeque;
    4. cout<<"mydeque是否为空?"<empty();
    5. mydeque.push_back(5);
    6. cout<<"\nmydeque是否为空?"<empty();
    7. }

    输出:

    mydeque是否为空?1
    mydeque是否为空?0 


      (5) shrink_to_fit()——要求deque减小容量已适应元素个数 

            dequen减小内存以适配size,即将分配给deque的内存减小到当前deque中元素实际使用的内存大小。由于deque的实现机制大多为一个动态数组,可以保留已被删除的元素的内存空间或者提前分配的额外内存空间以快速插入,因此一个deque分配的内存空间可能比deque保存当前元素所需的内存要多。使用shrink_to_fit()就会释放这些多余暂未被用到的内存。

    1. int main()
    2. {
    3. deque<int> mydeque;
    4. mydeque.resize(100);
    5. cout<<"mydeque.size()="<size()<<"\n";
    6. mydeque.resize(10);
    7. cout<<"mydeque.size()="<size()<<"\n";
    8. mydeque.shrink_to_fit();
    9. }

    输出:

    mydeque.size() = 100
    mydeque.size() = 10


      (6) at()——访问deque元素

            at(索引),使用元素的索引来访问deque。

    1. int main()
    2. {
    3. deque<int> mydeque;
    4. for (int i=1; i<=5; i++)
    5. {
    6. mydeque.push_back(i);
    7. }
    8. cout<<"初始化后的mydeque:";
    9. for(auto num:mydeque)
    10. {
    11. cout<" ";
    12. }
    13. int num2=mydeque.at(2);
    14. cout<<"\nmydeque中索引为2的元素为:"<
    15. }

    输出:

    初始化后的mydeque:1 2 3 4 5
    mydeque中索引为2的元素为:3


     (7) front()和back()——访问deque头尾元素 

            front()返回deque第一个元素,back()返回deque最后一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4,5,6,7,8};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. int front=mydeque.front();
    10. int back=mydeque.back();
    11. cout<<"\nmydeque的头元素为:"<
    12. cout<<"\nmydeque的尾元素为:"<
    13. }

    输出:

    初始化后的mydeque为:1 2 3 4 5 6 7 8
    mydeque的头元素为:1
    mydeque的尾元素为:8


    (8) assign()——指定deque元素

            assign的作用就是用新的元素替换deque中旧的元素。

    用法一:deque.assign(num,value)

            这种用法会用num个value填充deque,如果操作前deque中有其他元素,会被覆盖掉。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.assign(3,2);
    10. cout<<"\nassign之后mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

    输出:

    初始化后的mydeque为:1 2 3 4
    assign之后mydeque为:2 2 2

    用法二:deque.assign(iterator1,iterator2)

            这种用法会用两个迭代器iterator1和iterator2之间的元素覆盖deque的元素,迭代器可以是原来deque的迭代器,也可以是其他deque的迭代器,注意区间是左闭右开[iterator1,iterator2),即iterator1指向的元素在区间内,iterator2指向的元素不在区间内,iterator2可以是deque.end()。

    1. int main()
    2. {
    3. deque<int> mydeque1{1,2,3,4};
    4. deque<int> mydeque2{5,6,7,8};
    5. cout<<"初始化后的mydeque1为:";
    6. for(auto num:mydeque1)
    7. {
    8. cout<" ";
    9. }
    10. cout<<"\n初始化后的mydeque2为:";
    11. for (auto num:mydeque2)
    12. {
    13. cout<" ";
    14. }
    15. deque<int>::iterator it1=mydeque1.begin()+1;
    16. deque<int>::iterator it2=mydeque1.end()-1;
    17. mydeque2.assign(it1,it2);
    18. cout<<"\nassign后的mydeque2为:";
    19. for (auto num:mydeque2)
    20. {
    21. cout << num << " ";
    22. }
    23. }

    输出:

    初始化后的mydeque1为:1 2 3 4
    初始化后的mydeque2为:5 6 7 8
    assign后的mydeque2为:2 3

    用法三:deque.assign(address1,address2) 

            这种用法会用两个数组元素地址address1和address2之间的元素覆盖deque的元素,注意区间仍是左闭右开[*address1,*address2),即address1指向的元素在区间内,address2指向的元素不在区间内。

    1. int main()
    2. {
    3. deque<int> mydeque1{1,2,3,4};
    4. int a[5]={10,20,30,40,50};
    5. cout<<"初始化后的mydeque1为:";
    6. for(auto num:mydeque1)
    7. {
    8. cout<" ";
    9. }
    10. mydeque1.assign(&a[2],&a[4]);
    11. cout<<"\nassign后的mydeque1为:";
    12. for(auto num:mydeque1)
    13. {
    14. cout << num << " ";
    15. }
    16. }

    输出:

    始化后的mydeque1为:1 2 3 4
    assign后的mydeque1为:30 40


    (9) push_back()——添加元素(deque尾部) 

            向deque中添加元素,就需要使用push_back()。它的作用是向deque尾部添加一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque) {
    6. cout<" ";
    7. }
    8. mydeque.push_back(8);
    9. cout<<"\n尾部插入一个元素后的mydeque为:";
    10. for(auto num:mydeque)
    11. {
    12. cout << num << " ";
    13. }
    14. }

    输出:

    初始化后的mydeque为:1 2 3 4
    尾部插入一个元素后的mydeque为:1 2 3 4 8


    (10) push_front()——添加元素(deque头部)

            在deque中添加元素,就需要使用push_front()。它的作用是向deque头部添加一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.push_front(8);
    10. cout<<"\n头部插入一个元素后的mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

    输出:

    初始化后的mydeque为:1 2 3 4
    头部插入一个元素后的mydeque为:8 1 2 3 4


    (11) pop_back()——移除deque元素(尾部) 

            删除deque中的元素,就使用pop_back()。它的作用是删除deque尾部的一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.pop_back();
    10. cout<<"\n尾部删除一个元素后的mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

    输出:

    初始化后的mydeque为:1 2 3 4
    尾部删除一个元素后的mydeque为:1 2 3


    (12) pop_front()——删除deque元素(头部)

            想要删除deque中的元素,就需要使用pop_front()。它的作用是删除deque头部的一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.pop_front();
    10. cout<<"\n头部删除一个元素后的mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

    输出:

    初始化后的mydeque为:1 2 3 4
    头部删除一个元素后的mydeque为:2 3 4


    (13) insert()——添加元素(任意位置) 

            作用是向deque中添加元素。

    用法一:deque.insert(iterator,value)

            insert(iterator,value)的作用是向iterator迭代器指向元素的前边添加一个元素value,并返回一个迭代器指向新插入的元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. deque<int>::iterator it=mydeque.begin()+1;
    10. deque<int>::iterator itnew=mydeque.insert(it,10);
    11. cout<<"\n返回的迭代器指向的元素为"<<*itnew;
    12. cout<<"\ninsert添加一个元素后的mydeque为:";
    13. for(auto num:mydeque)
    14. {
    15. cout<" ";
    16. }
    17. }

    输出:

    初始化后的mydeque为:1 2 3 4
    返回的迭代器指向的元素为10
    insert添加一个元素后的mydeque为:1 10 2 3 4

    用法二:deque.insert(iterator,num,value)

            insert(iterator,num,value)的作用是向iterator迭代器指向元素的前边添加num个元素value,并返回一个迭代器指向新插入的第一个元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for (auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. deque<int>::iterator it=mydeque.begin()+1;
    10. mydeque.insert(it,2,20);
    11. cout<<"\n使用insert插入元素后:";
    12. for(auto num:mydeque)
    13. {
    14. cout << num << " ";
    15. }
    16. }

    输出:

    初始化后的mydeque为:1 2 3 4
    使用insert插入元素后:1 20 20 2 3 4

     用法三:deque.erase(iterator,iterator1,iterator2)

            insert(iterator, iterator1, iterator2)的作用是向iterator迭代器指向元素的前边添加[iterator1,iterator2)之间的元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. deque<int>::iterator it=mydeque.begin()+1;
    10. deque<int>::iterator it1=deque2.begin();
    11. deque<int>::iterator it2=deque2.end();
    12. mydeque.insert(it,it1,it2);
    13. cout<<"\n使用insert插入元素后:";
    14. for(auto num:mydeque)
    15. {
    16. cout<" ";
    17. }
    18. }

    输出:

    初始化后的mydeque为:1 2 3 4
    使用insert插入元素后:1 10 20 30 2 3 4


    (14) erase()——删除元素(任意位置) 

            erase的作用就是根据传入的迭代器删除deque中的元素,参数为一个迭代器,只删除迭代器指向的元素;参数为两个迭代器,删除两个迭代器之间的元素。

    用法一:deque.erase(iterator)

            这种用法会删除迭代器iterator指向的元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout " ";
    8. }
    9. deque<int>::iterator it=mydeque.begin()+1;
    10. deque<int>::iterator itnew=mydeque.erase(it);
    11. cout<<"\n删除元素后返回的迭代器itnew指向的元素为:"<<*itnew;
    12. cout<<"\n使用erase删除元素后:";
    13. for(auto num:mydeque)
    14. {
    15. cout<" ";
    16. }
    17. }

    输出 :

    初始化后的mydeque为:1 2 3 4
    删除元素后返回的迭代器itnew指向的元素为:3
    使用erase删除元素后:1 3 4

     用法二:deque.erase(iterator1,iterator2)

            这种用法会删除迭代器iterator1指向的元素到iterator2指向元素之间的元素,包括iterator1指向的元素但不包括iterator2指向的元素,即擦除[iterator1,iterator2]。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. deque<int>::iterator it1=mydeque.begin()+1;
    10. deque<int>::iterator it2=mydeque.end();
    11. mydeque.erase(it1,it2);
    12. cout<<"\n使用erase删除元素后:";
    13. for(auto num:mydeque)
    14. {
    15. cout<" ";
    16. }
    17. }

    输出:

    初始化后的mydeque为:1 2 3 4
    使用erase删除元素后:1


    (15) clear()——清空元素

            clear的作用就是清空deque中的所有元素。想要清空deque中所有元素,并且deque的大小变为0,就要使用clear()

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.clear();
    10. cout<<"\n使用erase清空元素后mydeque.size() ="<size();
    11. cout<<"\n使用erase清空元素后:";
    12. for(auto num:mydeque)
    13. {
    14. cout<" ";
    15. }
    16. }

    输出:

    初始化后的mydeque为:1 2 3 4
    使用erase清空元素后mydeque.size() =0
    使用erase清空元素后:


    (16) swap()——交换元素

            swap的作用就是交换两个deque的元素

            交换两个deque的元素,就需要·使用swap()deque1.swap(deque2),两个deque存储的元素类型必须相同,元素个数可以不同。

    1. int main()
    2. {
    3. deque<int> mydeque1{1,11,111,1111};
    4. deque<int> mydeque2{2,22,222};
    5. cout<<"初始化后的mydeque1为:";
    6. for(auto num:mydeque1)
    7. {
    8. cout<" ";
    9. }
    10. cout<<"\n初始化后的mydeque1为:";
    11. for(auto num:mydeque2)
    12. {
    13. cout<" ";
    14. }
    15. mydeque1.swap(mydeque2);
    16. cout<<"\n使用swap交换元素后mydeque1:";
    17. for(auto num:mydeque1)
    18. {
    19. cout<" ";
    20. }
    21. cout<<"\n使用swap交换元素后mydeque2:";
    22. for(auto num:mydeque2)
    23. {
    24. cout<" ";
    25. }
    26. }

    输出:

    始化后的mydeque1为:1 11 111 1111
    初始化后的mydeque1为:2 22 222
    使用swap交换元素后mydeque1:2 22 222
    使用swap交换元素后mydeque2:1 11 111 1111


    (17) emplace()——插入元素 

            向deque中添加元素,使用emplace(iterator,value)方法,作用是向iterator迭代器指向元素的前边添加一个元素value。返回一个迭代器,指向新添加的元素。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque1为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. deque<int>::iterator it=mydeque.begin()+1;
    10. deque<int>::iterator it1=mydeque.emplace(it,10);
    11. cout<<"\n第一次插入后返回的迭代器it1指向元素为:"<<*it1;
    12. deque<int>::iterator it2=mydeque.emplace(it1,20);
    13. cout<<"\n第二次插入后返回的迭代器it2指向元素为:"<<*it2;
    14. mydeque.emplace(mydeque.end(),30);
    15. cout<<"\n三次插入元素后,mydeque为:";
    16. for(auto num:mydeque)
    17. {
    18. cout<" ";
    19. }
    20. }

    输出:

    初始化后的mydeque1为:1 2 3 4
    第一次插入后返回的迭代器it1指向元素为:10
    第二次插入后返回的迭代器it2指向元素为:20
    三次插入元素后,mydeque为:1 20 10 2 3 4 30

    备注: 

    emplace和insert的区别:
            emplace和insert插入元素最大的区别是emplace不会产生不必要的变量,使用insert插入元素时,需要申请内存空间创建临时对象,而申请内存空间就需要消耗一定时间;而使用emplace插入元素时,直接在原来容器的内存空间上 ,调用构造函数,不需要额外申请内存空间,就节省了很多时间,效率较高。


    (18) emplace_back()——在deque尾部插入元素

            在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.emplace_back(10);
    10. cout<<"\n尾部插入一个元素后的mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

    输出:

    初始化后的mydeque为:1 2 3 4
    尾部插入一个元素后的mydeque为:1 2 3 4 10


    (19) emplace_front()——在deque尾部插入元素

            在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。

    1. int main()
    2. {
    3. deque<int> mydeque{1,2,3,4};
    4. cout<<"初始化后的mydeque为:";
    5. for(auto num:mydeque)
    6. {
    7. cout<" ";
    8. }
    9. mydeque.emplace_front(10);
    10. cout<<"\n头部插入一个元素后的mydeque为:";
    11. for(auto num:mydeque)
    12. {
    13. cout<" ";
    14. }
    15. }

     输出:

    初始化后的mydeque为:1 2 3 4
    头部插入一个元素后的mydeque为:10 1 2 3 4


    以上就是本文的全部内容啦!感谢阅读!

    希望大家积极提出意见! 

  • 相关阅读:
    Express操作MongoDB【一.Express框架通过Mongoose模块操作MongoDB数据库;二.在接口中间件中使用Mongoose模块】
    前端新手Vue3+Vite+Ts+Pinia+Sass项目指北系列文章 —— 系列文章目录
    windows && es Install
    积分商城该如何帮助商家盈利
    反转单词前缀
    Django系列:Django简介与MTV架构体系概述
    maven运行报错解决
    19、Flink 的Table API 和 SQL 中的自定义函数及示例(3)
    汽车行业“墨守成规”?VR全景助力车企打开新局面
    linux学习 day05 基础 I/O
  • 原文地址:https://blog.csdn.net/weixin_46522531/article/details/127702340