【C++】STL 容器 - deque 双端数组容器 ( deque 容器与 vector 容器区别 | 容器头部插入 / 删除元素 | 查询元素索引位置 | algorithm#find 函数 )

旧城等待， 2024-02-05 17:57 148阅读 0赞

#### 文章目录 ####

*  一、 deque 双端数组容器简介
 *   *  1、deque 容器引入
     *  2、deque 容器与 vector 容器区别
     *  3、deque 容器特点
 *  二、 deque 双端数组容器常用操作 ( 仅展示与 vector 容器的不同操作 )
 *   *  1、deque 容器头部插入元素 - push\_front 函数
     *  2、deque 容器头部删除元素 - pop\_front 函数
 *  三、 查询 deque 容器中指定元素的索引位置
 *   *  1、使用 algorithm\#find 函数查询 deque 容器中的元素对应的迭代器
     *  2、使用 algorithm\#distance 函数计算两个迭代器的距离
     *  3、完整代码示例

## 一、 deque 双端数组容器简介 ##

--------------------

### 1、deque 容器引入 ###

deque 是 " 双端数组容器 " , 全称 " 双端队列 " , 英文名称为 : " Double-Ended Queue " , 该容器可以在 首部 和 尾部 插入 和 删除 元素 ;

### 2、deque 容器与 vector 容器区别 ###

**deque 与 vector 区别 :** 与 " deque 双端数组容器 " 相对的是 " vector 单端数组容器 " ;

*  vector 只能在 尾部 插入 和 移除元素 ;
 *  deque 可以在 头部 和 尾部 插入 和 移除元素 ;

**deque 容器 与 vector 容器 的操作 , 绝大部分都是相同的 , 本篇博客中着重讲解 deque 容器的 不同操作 ;**

### 3、deque 容器特点 ###

**deque 容器特点 :**

*  **双端访问 :** deque 容器允许在头部和尾部进行快速的插入和删除操作 ;
 *  **动态数组 :** deque 容器底层基于动态数组实现 , 其内存是连续的 , 访问效率较高 ;
 *  **随机访问 :** deque 容器可以通过索引值访问容器中的元素 ;
 *  **时间复杂度 :** 该容器遍历的时间复杂度是 O(n) ;

## 二、 deque 双端数组容器常用操作 ( 仅展示与 vector 容器的不同操作 ) ##

--------------------

### 1、deque 容器头部插入元素 - push\_front 函数 ###

调用 `std::deque` 容器的 `push_front()` 函数 可以在容器的头部插入一个元素 ;

**函数原型如下 :** 该函数接受一个元素作为参数 , 并将其插入到容器的头部

// 接收一个常量引用参数 , 插入常量元素
    void push_front(const value_type& val);  
    
    // 接收一个右值引用参数 , 插入非常量元素
    void push_front(value_type&& val);

**代码示例 :**

// 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 向 deque 容器头部插入 888 元素
        deq.push_front(888);

**完整代码示例 :**

#include "iostream"
    using namespace std;
    #include "deque"
    
    // 打印 deque<int> 类型的 STL 容器
    void printV(deque<int>& deq)
    {
        
        cout << "deque 容器中的元素 : ";
        for (int i = 0; i < deq.size(); i++)
        {
        
            // 输出单个元素
            cout << deq[i] << " ";
        }
        // 输出回车换行
        std::cout << std::endl;
        cout << "   deque 容器大小 : " << deq.size();
        // 输出回车换行
        std::cout << std::endl;
    }
    
    int main() {
        
    
        // 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 打印 deque 容器中的元素
        printV(deq);
    
        // 向 deque 容器头部插入 888 元素
        deq.push_front(888);
    
    
        // 打印 deque 容器中的元素
        printV(deq);
    
    
        // 控制台暂停 , 按任意键继续向后执行
        system("pause");
    
        return 0;
    };

**执行结果 :**

deque 容器中的元素 : 1 2 3 4 5
       deque 容器大小 : 5
    deque 容器中的元素 : 888 1 2 3 4 5
       deque 容器大小 : 6
    Press any key to continue . . .

![在这里插入图片描述][bed797e2ebb343ee8b3d98defada1f25.png]

### 2、deque 容器头部删除元素 - pop\_front 函数 ###

调用 `std::deque` 容器的 `pop_front()` 函数 可以 删除容器的头部元素 ;

该函数原型如下 :

void pop_front();

该函数会删除 deque 容器的头部元素 , 并减小容器的大小 ;

**代码示例 :**

// 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 向 deque 容器 头部元素
        deq.pop_front();

**完整代码示例 :**

#include "iostream"
    using namespace std;
    #include "deque"
    
    // 打印 deque<int> 类型的 STL 容器
    void printV(deque<int>& deq)
    {
        
        cout << "deque 容器中的元素 : ";
        for (int i = 0; i < deq.size(); i++)
        {
        
            // 输出单个元素
            cout << deq[i] << " ";
        }
        // 输出回车换行
        std::cout << std::endl;
        cout << "   deque 容器大小 : " << deq.size();
        // 输出回车换行
        std::cout << std::endl;
    }
    
    int main() {
        
    
        // 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 打印 deque 容器中的元素
        printV(deq);
    
        // 向 deque 容器 头部元素
        deq.pop_front();
    
    
        // 打印 deque 容器中的元素
        printV(deq);
    
    
        // 控制台暂停 , 按任意键继续向后执行
        system("pause");
    
        return 0;
    };

**执行结果 :**

deque 容器中的元素 : 1 2 3 4 5
       deque 容器大小 : 5
    deque 容器中的元素 : 2 3 4 5
       deque 容器大小 : 4
    Press any key to continue . . .

![在这里插入图片描述][3eba3277455d47e79f5f20a222d99122.png]

## 三、 查询 deque 容器中指定元素的索引位置 ##

--------------------

### 1、使用 algorithm\#find 函数查询 deque 容器中的元素对应的迭代器 ###

在 <algorithm> 头文件中 定义了一个 `find()` 函数 , 该函数作用是 在一个序列中查找特定元素的 索引位置 ;

**algorithm\#find 函数原型 :**

template< class InputIt, class T >  
    InputIt find( InputIt first, InputIt last, const T& value );

*  **参数说明：**
    
     *  ***first :*** 指向序列起始位置的迭代器 ;
     *  ***last :*** 指向序列结束位置的迭代器 ;
     *  ***value :*** 要查找的元素的值 ;
 *  **返回值 :** 如果找到了该元素 , 则返回指向该元素的迭代器 , 否则返回 last ;

**代码示例 :**

// 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 查找 3 在 deque 容器中的 索引
        deque<int>::iterator it = find(deq.begin(), deq.end(), 3);

### 2、使用 algorithm\#distance 函数计算两个迭代器的距离 ###

在 <algorithm> 头文件中 定义了一个 `distance ()` 函数 , 该函数作用是 计算两个迭代器之间的距离 ;

**algorithm\#distance 函数原型 :**

template< class InputIt >  
    typename iterator_traits<InputIt>::difference_type distance( InputIt first, InputIt last );

*  **参数说明 :**
    
     *  ***first :*** 指向序列起始位置的迭代器 ;
     *  ***last :*** 指向序列结束位置的迭代器 ;
 *  **返回值 :** 返回 last 与 first 之间的距离 , 即它们之间的元素数量 ; 返回类型为 `typename iterator_traits<InputIt>::difference_type` , 通常是一个整数类型 ;

**代码示例 :**

// 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 查找 3 在 deque 容器中的 索引
        deque<int>::iterator it = find(deq.begin(), deq.end(), 3);
        if (it != deq.end())
        {
        
            cout << "3 对应的 索引位置 = " << distance(deq.begin(), it) << endl;
        }

### 3、完整代码示例 ###

**代码示例 :**

#include "iostream"
    using namespace std;
    #include "deque"
    #include "algorithm"
    
    // 打印 deque<int> 类型的 STL 容器
    void printD(deque<int>& deq)
    {
        
        cout << "deque 容器中的元素 : ";
        for (int i = 0; i < deq.size(); i++)
        {
        
            // 输出单个元素
            cout << deq[i] << " ";
        }
        // 输出回车换行
        std::cout << std::endl;
        cout << "   deque 容器大小 : " << deq.size();
        // 输出回车换行
        std::cout << std::endl;
    }
    
    int main() {
        
    
        // 创建空的 deque 容器
        std::deque<int> deq{
         1, 2, 3, 4, 5 };
    
        // 打印 deque 容器中的元素
        printD(deq);
    
        // 查找 3 在 deque 容器中的 索引
        deque<int>::iterator it = find(deq.begin(), deq.end(), 3);
        if (it != deq.end())
        {
        
            cout << "3 对应的 索引位置 = " << distance(deq.begin(), it) << endl;
        }
        else
        {
        
            cout << "没有找到元素 3" << endl;
        }
    
    
        // 控制台暂停 , 按任意键继续向后执行
        system("pause");
    
        return 0;
    };

**执行结果 :**

deque 容器中的元素 : 1 2 3 4 5
       deque 容器大小 : 5
    3 对应的 索引位置 = 2
    Press any key to continue . . .

![在这里插入图片描述][0a74d4ba583a4c05bde5e95feadbb51d.png]

[bed797e2ebb343ee8b3d98defada1f25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/53a9229a5c944d8ca650479fb1524d66.png
[3eba3277455d47e79f5f20a222d99122.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/eb1ba1235f8645f29174bc054e25a2c5.png
[0a74d4ba583a4c05bde5e95feadbb51d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/7c0e2cea65b34f70afc1bb9c3614e90b.png