deque（double-ended queue，双端队列）是STL中一种重要的序列容器。与vector相比，deque在头部和尾部的插入删除操作具有常数时间复杂度优势。本文将深入探讨deque的内部实现机制、使用场景以及与vector的性能对比。
一、deque的基本特性
1. 什么是deque
deque是一种双端队列容器，支持在常数时间内对两端进行插入和删除操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <deque>
#include <iostream>
int main() {
std::deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);
dq.push_front(0);
dq.push_front(-1);
std::cout << "Element at index 2: " << dq[2] << std::endl;
for (const auto& elem : dq) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
|
2. deque的核心特性
| 特性 |
说明 |
| 双端操作 |
push_front、push_back、pop_front、pop_back均为O(1) |
| 随机访问 |
支持[]操作符和at()，为O(1) |
| 迭代器 |
双向迭代器 |
| 内存管理 |
多段连续内存块，通过中控器管理 |
| 插入删除 |
两端操作为O(1)，中间操作为O(n) |
二、deque的内部实现机制
1. 分段连续内存结构
deque的内部结构由多个固定大小的连续内存块（称为buffer）组成，通过一个map（指向这些buffer指针的数组）进行管理：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<typename T>
class deque {
private:
T** map_;
size_t map_size_;
size_t num_elements_;
size_t block_size_;
size_t start_index_;
size_t end_index_;
};
|
2. 中控器（Map）
deque使用一个"中控器"来管理多个内存块：
3. 迭代器实现
deque的迭代器需要处理跨块访问的情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
template<typename T>
struct deque_iterator {
T** cur;
T** first;
T** last;
void increment() {
++cur;
if (cur == last) {
first = *(++T** (cur = first));
last = first + block_size;
}
}
void decrement() {
if (cur == first) {
last = *(--T** (cur = last));
first = last - block_size;
}
--cur;
}
};
|
4. 内存重分配策略
当deque在头部或尾部扩展时，会分配新的buffer并更新中控器：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void push_back(const T& value) {
if (end_index_ < block_size_ - 1) {
construct_at(buffer_[last_buffer_] + end_index_, value);
++end_index_;
} else {
if (map_size_ < num_buffers_ + 1) {
reallocate_map();
}
map_[num_buffers_] = allocate_buffer();
construct_at(map_[num_buffers_], value);
end_index_ = 1;
++num_buffers_;
}
++num_elements_;
}
|
三、deque与vector对比
1. 底层结构对比
| 特性 |
deque |
vector |
| 内存布局 |
多段连续 + 中控器 |
单段连续 |
| 扩展方式 |
两端可扩展 |
尾部扩展 |
| 内存预留 |
不需要预留 |
通常需要reserve() |
| 迭代器类型 |
双向迭代器 |
随机访问迭代器 |
| 数据局部性 |
较差 |
较好 |
2. 性能对比测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <deque>
#include <vector>
#include <chrono>
#include <iostream>
const int N = 1000000;
void benchmark(const std::string& name, auto&& container, auto&& operation) {
auto start = std::chrono::high_resolution_clock::now();
operation();
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << name << ": " << duration.count() << " μs" << std::endl;
}
int main() {
benchmark("deque push_back", std::deque<int>{}, []() {
std::deque<int> dq;
for (int i = 0; i < N; ++i) {
dq.push_back(i);
}
});
benchmark("vector push_back", std::vector<int>{}, []() {
std::vector<int> vec;
vec.reserve(N);
for (int i = 0; i < N; ++i) {
vec.push_back(i);
}
});
benchmark("deque push_front", std::deque<int>{}, []() {
std::deque<int> dq;
for (int i = 0; i < N / 10; ++i) {
dq.push_front(i);
}
});
benchmark("vector insert(begin)", std::vector<int>{}, []() {
std::vector<int> vec;
for (int i = 0; i < N / 10; ++i) {
vec.insert(vec.begin(), i);
}
});
return 0;
}
|
3. 典型场景选择建议
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void scenario1() {
std::deque<int> dq;
dq.push_front(1);
dq.push_back(2);
}
void scenario2() {
std::vector<int> vec;
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
vec.push_back(i);
}
}
void scenario3() {
std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.push_back(2);
std::cout << dq[1] << std::endl;
}
|
四、deque的成员函数详解
1. 构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <deque>
int main() {
std::deque<int> dq1;
std::deque<int> dq2(10);
std::deque<int> dq3(10, 5);
std::vector<int> vec = {1, 2, 3, 4, 5};
std::deque<int> dq4(vec.begin(), vec.end());
std::deque<int> dq5(dq4);
std::deque<int> dq6(std::move(dq5));
std::deque<int> dq7 = {1, 2, 3, 4, 5};
return 0;
}
|
2. 元素访问
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <deque>
#include <stdexcept>
int main() {
std::deque<int> dq = {10, 20, 30, 40, 50};
std::cout << dq[2] << std::endl;
std::cout << dq.at(2) << std::endl;
try {
std::cout << dq.at(10) << std::endl;
} catch (const std::out_of_range& e) {
std::cerr << "Out of range: " << e.what() << std::endl;
}
std::cout << dq.front() << std::endl;
std::cout << dq.back() << std::endl;
return 0;
}
|
3. 迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <deque>
int main() {
std::deque<int> dq = {1, 2, 3, 4, 5};
for (auto it = dq.begin(); it != dq.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
for (auto cit = dq.cbegin(); cit != dq.cend(); ++cit) {
std::cout << *cit << " ";
}
std::cout << std::endl;
for (const auto& elem : dq) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
|
4. 容量操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <deque>
int main() {
std::deque<int> dq;
std::cout << std::boolalpha << dq.empty() << std::endl;
for (int i = 0; i < 100; ++i) {
dq.push_back(i);
}
std::cout << dq.size() << std::endl;
std::cout << dq.max_size() << std::endl;
dq.resize(50);
dq.resize(200, -1);
dq.shrink_to_fit();
return 0;
}
|
5. 修改器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <deque>
int main() {
std::deque<int> dq = {1, 2, 3, 4, 5};
dq.assign(5, 10);
dq.assign({1, 2, 3});
std::deque<int> dq2 = {100, 200};
dq.swap(dq2);
dq.clear();
dq.insert(dq.begin() + 2, 99);
dq.insert(dq.end(), 3, 88);
dq.insert(dq.begin(), vec.begin(), vec.end());
dq.erase(dq.begin());
dq.erase(dq.begin(), dq.begin() + 3);
dq.push_back(6);
dq.pop_back();
dq.push_front(0);
dq.pop_front();
dq.emplace_back(7);
dq.emplace_front(-1);
dq.emplace(dq.begin() + 3, 50);
return 0;
}
|
五、实战应用场景
1. 实现滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <deque>
#include <vector>
#include <iostream>
std::vector<int> slidingWindowMax(const std::vector<int>& nums, int k) {
std::deque<int> dq;
std::vector<int> result;
for (size_t i = 0; i < nums.size(); ++i) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
auto result = slidingWindowMax(nums, k);
for (int val : result) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
|
2. 实现LRU缓存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <deque>
#include <unordered_map>
#include <iostream>
template<typename K, typename V>
class LRUCache {
private:
size_t capacity_;
std::deque<K> recent_;
std::unordered_map<K, V> cache_;
std::unordered_map<K, typename std::deque<K>::iterator> pos_;
public:
explicit LRUCache(size_t capacity) : capacity_(capacity) {}
bool get(const K& key, V& value) {
auto it = cache_.find(key);
if (it == cache_.end()) {
return false;
}
value = it->second;
recent_.erase(pos_[key]);
recent_.push_front(key);
pos_[key] = recent_.begin();
return true;
}
void put(const K& key, const V& value) {
if (cache_.find(key) != cache_.end()) {
cache_[key] = value;
recent_.erase(pos_[key]);
recent_.push_front(key);
pos_[key] = recent_.begin();
} else {
if (cache_.size() >= capacity_) {
K lruKey = recent_.back();
cache_.erase(lruKey);
pos_.erase(lruKey);
recent_.pop_back();
}
cache_[key] = value;
recent_.push_front(key);
pos_[key] = recent_.begin();
}
}
void print() const {
std::cout << "Cache state (oldest -> newest): ";
for (const auto& key : recent_) {
std::cout << key << ":" << cache_.at(key) << " ";
}
std::cout << std::endl;
}
};
int main() {
LRUCache<int, int> cache(3);
cache.put(1, 100);
cache.put(2, 200);
cache.put(3, 300);
cache.print();
int value;
cache.get(2, value);
std::cout << "Key 2 value: " << value << std::endl;
cache.print();
cache.put(4, 400);
cache.print();
return 0;
}
|
3. 字符串编辑历史
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <deque>
#include <string>
#include <iostream>
#include <sstream>
class TextEditor {
private:
std::deque<std::string> history_;
size_t current_pos_;
public:
TextEditor() : current_pos_(0) {}
void edit(const std::string& text) {
if (current_pos_ < history_.size()) {
history_.erase(history_.begin() + current_pos_, history_.end());
}
history_.push_back(text);
++current_pos_;
}
std::string undo() {
if (current_pos_ == 0) {
return "";
}
--current_pos_;
return history_[current_pos_];
}
std::string redo() {
if (current_pos_ >= history_.size()) {
return "";
}
return history_[current_pos_++];
}
void printHistory() const {
std::cout << "History (current=" << current_pos_ << "): ";
for (size_t i = 0; i < history_.size(); ++i) {
if (i == current_pos_) {
std::cout << "[" << history_[i] << "] ";
} else {
std::cout << history_[i] << " ";
}
}
std::cout << std::endl;
}
};
int main() {
TextEditor editor;
editor.edit("Hello");
editor.edit("Hello World");
editor.edit("Hello World!");
editor.printHistory();
std::cout << "Undo: " << editor.undo() << std::endl;
editor.printHistory();
std::cout << "Undo: " << editor.undo() << std::endl;
editor.printHistory();
std::cout << "Redo: " << editor.redo() << std::endl;
editor.printHistory();
return 0;
}
|
4. 生产者消费者队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <deque>
#include <mutex>
#include <condition_variable>
#include <thread>
#include <iostream>
#include <chrono>
template<typename T>
class ThreadSafeQueue {
private:
std::deque<T> queue_;
std::mutex mtx_;
std::condition_variable cv_;
bool closed_ = false;
public:
void push(T value) {
{
std::lock_guard<std::mutex> lock(mtx_);
queue_.push_back(std::move(value));
}
cv_.notify_one();
}
bool pop(T& value) {
std::unique_lock<std::mutex> lock(mtx_);
cv_.wait(lock, [this] { return !queue_.empty() || closed_; });
if (queue_.empty()) {
return false;
}
value = std::move(queue_.front());
queue_.pop_front();
return true;
}
void close() {
{
std::lock_guard<std::mutex> lock(mtx_);
closed_ = true;
}
cv_.notify_all();
}
bool empty() const {
std::lock_guard<std::mutex> lock(mtx_);
return queue_.empty();
}
size_t size() const {
std::lock_guard<std::mutex> lock(mtx_);
return queue_.size();
}
};
int main() {
ThreadSafeQueue<int> queue;
std::thread producer([&queue]() {
for (int i = 1; i <= 10; ++i) {
queue.push(i);
std::cout << "Produced: " << i << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
queue.close();
});
std::thread consumer([&queue]() {
int value;
while (queue.pop(value)) {
std::cout << "Consumed: " << value << std::endl;
}
});
producer.join();
consumer.join();
return 0;
}
|
六、deque使用注意事项
1. 迭代器失效规则
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <deque>
int main() {
std::deque<int> dq = {1, 2, 3, 4, 5};
auto it = dq.begin() + 2;
dq.push_back(6);
dq.push_front(0);
dq.insert(it, 99);
auto it2 = dq.begin() + 3;
dq.erase(it2);
return 0;
}
|
2. 内存使用考量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <deque>
int main() {
std::deque<int> dq;
for (int i = 0; i < 1000000; ++i) {
dq.push_back(i);
}
return 0;
}
|
3. 性能优化建议
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <deque>
int main() {
std::deque<int> dq;
dq.resize(1000000);
struct Heavy {
std::string data;
Heavy(const std::string& s) : data(s) {}
};
std::deque<Heavy> hd;
hd.push_back(Heavy("test"));
hd.emplace_back("test");
return 0;
}
|
七、总结
deque作为STL中重要的序列容器，提供了vector和list所不具备的优势：
核心要点：
- 双端操作优势：在头部和尾部的插入删除都是O(1)
- 分段连续内存：通过中控器管理多个内存块，避免整体复制
- 随机访问支持：虽然迭代器不是真正随机访问，但支持下标操作
- 迭代器失效：两端操作不会使迭代器失效，中间操作会使迭代器失效
选择建议：
- 需要频繁在两端操作：使用deque
- 主要在尾部操作，追求缓存命中：使用vector
- 需要在中间频繁插入删除：使用list
- 需要在两端操作且需要频繁在中间插入删除：综合考虑或使用其他数据结构
理解deque的内部机制对于正确使用和优化C++程序至关重要，希望本文能帮助你更好地掌握这一重要容器。
