一文带你了解C++中deque的使用 |
||||||||
|
+ 目录
1）deque的定义及基本用法要使用deque，我们需要包含头文件，定义deque对象如下：
?
deque支持的基本操作如下：
示例代码如下：
?
执行结果：
2）deque的迭代器deque支持迭代器，可以按照指针的方式遍历deque中的所有元素。deque迭代器支持前向访问，但不支持随机访问，即不支持下标操作。deque迭代器又分为普通迭代器和反向迭代器，可以分别用begin()，end()，rbegin()，rend()方法来获取。 示例代码如下：
?
执行结果：
3）deque的性能对于在最差情况下，即内存池容量已满的情况，deque在表现上比较优，它的时间复杂度为O(1)，因为deque在前端和后端进行插入和删除的操作所需时间复杂度为O(1)，但如果在中间进行插入和删除，则时间复杂度为O(N)，因为因为需要把后面的元素往后移动。同时，它的空间复杂度为O(N)www.lu0.com，其中N表示deque中元素的个数。
4）deque的应用：滑动窗口问题滑动窗口问题是指在一个序列中找出所有长度为k的子序列，并且每次移动一个单位，重复执行这个操作，最终得到所有的子序列。这个问题在处理字符串问题，尤其是搜索问题中经常出现。我们可以用deque来解决这个问题，将待处理的数据元素存入到deque中，每次向右滑动窗口的时候从左边移除最先加入的元素，同时从右边添加一个新的元素。 示例代码如下：
?
|
