C++ STL 双端队列(Deque)

STL 中的 deque 是双端队列容器,deque 容器和 vector 容器有很多相似之处,deque 容器也擅长在序列尾部添加或删除元素(时间复杂度为 O(1)),而不擅长在序列中间添加或删除元素。deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,所耗费的时间复杂度也为常数阶 O(1)。并且更重要的一点是,deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

当需要向序列两端频繁的添加或删除元素时,应首选 deque 容器。

deque 语法

使用 deque 容器,必须先引入 <deque> 头文件。

#include <deque>

std::deque<type> values;

下面代码演示了如何创建并使用 deque 容器:

#include <iostream>
#include <deque>

using namespace std;

int main(void)
{
    deque<string> d;

    d.push_back("GetIoT.tech ");
    d.push_back("C++ STL");

    for (auto i=d.begin(); i<d.end(); i++) {
        cout  << *i << endl;
    }
    return 0; 
}

执行 g++ main.cpp && ./a.out 编译运行以上程序,输出结果如下:

GetIoT.tech 
C++ STL

这个示例创建了一个 deque 双端队列,并使用 push_back() 存放了元素,最后使用迭代器遍历了所有元素。

deque 成员函数

函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。
insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

Leave a Reply