目录
什么时候用deque，什么时候用vector，什么时候用list?
deque在C++的STL(Standard Template Library)中是一个非常强大的容器，它的全称是“Double-Ended Queue”，即双端队列。deque结合了数组和链表的优点，提供了在两端进行高效插入和删除操作的能力，同时保持了随机访问的特性。
双端队列和普通队列的区别？
普通队列（queue）
- 先进先出（FIFO）原则：普通队列遵循先进先出的原则，这意味着最先加入队列的元素将是最先被移除的。
- 操作限制：在普通队列中，新的元素只能从队尾（rear）添加（enqueue），而元素的移除只能从队头（front）进行（dequeue）。
双端队列（deque）
- 灵活的操作：双端队列允许在队列的两端进行插入和删除操作。这意呀着元素可以从队头（front）或队尾（rear）添加或移除。
- 不限制操作端：双端队列没有固定的操作端限制，因此它不是严格意义上的FIFO数据结构，而是更加灵活。
总结区别
- 操作端：
- 普通队列只允许在一端插入（队尾）和另一端删除（队头）。
- 双端队列允许在两端进行插入和删除。
- 数据访问：
- 普通队列中，数据访问遵循先进先出原则。
- 双端队列中，数据访问更灵活，可以在两端进行访问，不严格遵循先进先出原则。
- 使用场景：
- 普通队列常用于需要按顺序处理任务的情况，如打印机任务队列、事件处理队列等。
- 双端队列适用于需要灵活操作数据的情况，如滑动窗口算法、最近最少使用（LRU）缓存算法等。
deque的特点：
- 动态大小：
deque可以动态地增加或减少元素数量。 - 随机访问：
deque支持通过下标直接访问元素，时间复杂度为O(1)。 - 两端操作：
deque可以在头部和尾部进行快速的插入和删除操作，时间复杂度通常为O(1)。 - 内部实现：
deque使用一种复杂的内部结构来实现其特性，它将数据分割成多个连续的块，每个块的大小通常是固定的，这样既保证了随机访问的效率，又允许在两端进行高效的插入和删除。
deque的基本操作：
- 构造与初始化：
std::deque<int> d;// 创建一个空的dequestd::deque<int> d(10, 5);// 创建一个含有10个元素，每个元素值为5的deque
- 插入与删除：
d.push_front(1);// 在deque前端插入元素d.push_back(2);// 在deque后端插入元素d.pop_front();// 删除deque前端的元素d.pop_back();// 删除deque后端的元素d.insert(d.begin(), 0);// 在指定位置插入元素d.erase(d.begin());// 删除指定位置的元素
- 访问元素：
d.front();// 访问deque的第一个元素d.back();// 访问deque的最后一个元素d.at(index);// 访问指定索引的元素，如果索引越界会抛出异常d[index];// 直接通过下标访问元素
- 其他操作：
d.size();// 获取deque中的元素数量d.empty();// 检查deque是否为空d.clear();// 清空deque中的所有元素
示例代码：
Cpp
#include <iostream> #include <deque> int main() { std::deque<int> d; // 插入元素 d.push_back(1); d.push_front(2); d.push_back(3); // 访问元素 std::cout << "Front: " << d.front() << ", Back: " << d.back() << std::endl; // 删除元素 d.pop_front(); d.pop_back(); for (std::size_t i = 0; i < d.size(); ++i) { std::cout << "d-value: " << d[i] << std::endl; } return 0; }
编辑
什么时候用deque，什么时候用vector，什么时候用list?
std::vector
- 使用场景：
- 当你需要频繁的随机访问元素时。
- 当插入和删除操作主要发生在容器的末端时。
- 当容器的大小在初始化后变化不大，或者可以预先分配足够空间时。
- 优点：
- 提供随机访问，访问时间复杂度为O(1)。
- 插入和删除元素在末尾时效率高，时间复杂度为O(1)。
- 内存使用紧凑，元素在一块连续的内存区域中。
- 缺点：
- 在中间或开头插入或删除元素时效率低，时间复杂度为O(n)。
std::deque
- 使用场景：
- 当你需要在容器的头部和尾部频繁地插入和删除元素时。
- 当你希望保持随机访问能力时。
- 优点：
- 支持在头部和尾部的高效插入和删除，时间复杂度通常为O(1)。
- 提供随机访问，时间复杂度为O(1)。
- 缺点：
- 在中间位置插入或删除元素效率不如
std::list。 - 内存使用比
std::vector分散，因为元素分布在多个块中。
std::list
- 使用场景：
- 当你需要在容器的任意位置频繁插入和删除元素时。
- 当随机访问不是主要操作时。
- 优点：
- 在列表的任意位置插入和删除元素都非常高效，时间复杂度为O(1)。
- 不需要连续的内存空间，因此在内存分配方面更灵活。
- 缺点：
- 不支持随机访问，访问时间复杂度为O(n)。
- 遍历整个列表时可能比
std::vector或std::deque慢。
总结
- 如果需要大量随机访问且插入删除操作集中在末尾，使用
std::vector。 - 如果需要在两端高效插入删除且随机访问，使用
std::deque。 - 如果需要在任意位置频繁插入删除且不关心随机访问，使用
std::list。
