C++
手写 std::deque
实现由固定大小块和块索引表组成的双端队列，分析随机访问与两端增长。
发布于 2026年7月23日
手写 std::deque
实现由固定大小块和块索引表组成的双端队列，分析随机访问与两端增长。
本系列代码使用 C++20 和
oc::handmade命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。
一、学习目标
- 理解分段连续布局
- 实现两端摊还常数时间插入
- 区分元素地址稳定与迭代器稳定
二、前置条件
掌握原始存储、vector 扩容和随机访问迭代器。
Linux/macOS：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure
Windows PowerShell：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure
三、问题与设计选择
块表保存固定大小原始存储块，逻辑下标映射为块号和块内偏移。块表两端不足时重居中，只移动块指针而不移动 T。
这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。
四、内存布局与核心不变量
有效元素占据从 begin_slot 起的连续逻辑槽位；每个有效槽位恰好构造一个 T，其余槽位只是原始存储。
每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。
五、核心实现
T& at_unchecked(std::size_t logical) noexcept {
const std::size_t absolute = begin_slot_ + logical;
block& b = *map_[absolute / BlockSize];
return *std::launder(reinterpret_cast<T*>(
b.bytes + (absolute % BlockSize) * sizeof(T)));
}
上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。
六、完整教学实现
下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。
namespace oc::handmade {
template<class T, std::size_t BlockSize = 32>
class deque {
static_assert(BlockSize > 0);
struct block {
alignas(T) std::byte bytes[sizeof(T) * BlockSize];
};
std::vector<std::unique_ptr<block>> blocks_;
std::size_t begin_slot_{};
std::size_t size_{};
void initialize_map() {
if (!blocks_.empty()) return;
blocks_.resize(4);
begin_slot_ = 2 * BlockSize;
}
void grow_front_map() {
const std::size_t extra = std::max<std::size_t>(4, blocks_.size());
std::vector<std::unique_ptr<block>> expanded(extra + blocks_.size());
std::move(
blocks_.begin(),
blocks_.end(),
expanded.begin() + static_cast<std::ptrdiff_t>(extra)
);
blocks_.swap(expanded);
begin_slot_ += extra * BlockSize;
}
T* slot(std::size_t absolute) {
const std::size_t block_index = absolute / BlockSize;
if (block_index >= blocks_.size()) blocks_.resize(block_index + 1);
if (!blocks_[block_index]) blocks_[block_index] = std::make_unique<block>();
return std::launder(reinterpret_cast<T*>(
blocks_[block_index]->bytes + (absolute % BlockSize) * sizeof(T)
));
}
const T* existing_slot(std::size_t absolute) const {
const std::size_t block_index = absolute / BlockSize;
return std::launder(reinterpret_cast<const T*>(
blocks_[block_index]->bytes + (absolute % BlockSize) * sizeof(T)
));
}
public:
class iterator {
deque* owner_{};
std::size_t index_{};
iterator(deque* owner, std::size_t index) : owner_(owner), index_(index) {}
friend class deque;
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
iterator() = default;
T& operator*() const { return (*owner_)[index_]; }
iterator& operator++() { ++index_; return *this; }
iterator& operator--() { --index_; return *this; }
iterator& operator+=(difference_type n) { index_ += n; return *this; }
iterator& operator-=(difference_type n) { index_ -= n; return *this; }
friend iterator operator+(iterator it, difference_type n) { return it += n; }
friend iterator operator-(iterator it, difference_type n) { return it -= n; }
friend difference_type operator-(iterator a, iterator b) {
return static_cast<difference_type>(a.index_) -
static_cast<difference_type>(b.index_);
}
friend bool operator==(iterator, iterator) = default;
friend auto operator<=>(iterator a, iterator b) { return a.index_ <=> b.index_; }
};
deque() { initialize_map(); }
deque(const deque& other) : deque() {
for (const T& value : other) push_back(value);
}
deque(deque&& other) noexcept = default;
deque& operator=(deque other) noexcept {
swap(other);
return *this;
}
~deque() { clear(); }
void swap(deque& other) noexcept {
blocks_.swap(other.blocks_);
std::swap(begin_slot_, other.begin_slot_);
std::swap(size_, other.size_);
}
iterator begin() const noexcept { return iterator(const_cast<deque*>(this), 0); }
iterator end() const noexcept { return iterator(const_cast<deque*>(this), size_); }
bool empty() const noexcept { return size_ == 0; }
std::size_t size() const noexcept { return size_; }
T& operator[](std::size_t index) { return *slot(begin_slot_ + index); }
const T& operator[](std::size_t index) const { return *existing_slot(begin_slot_ + index); }
T& front() { return (*this)[0]; }
const T& front() const { return (*this)[0]; }
T& back() { return (*this)[size_ - 1]; }
const T& back() const { return (*this)[size_ - 1]; }
template<class... Args>
T& emplace_back(Args&&... args) {
T* target = slot(begin_slot_ + size_);
std::construct_at(target, std::forward<Args>(args)...);
++size_;
return *target;
}
template<class... Args>
T& emplace_front(Args&&... args) {
if (begin_slot_ == 0) grow_front_map();
T* target = slot(--begin_slot_);
std::construct_at(target, std::forward<Args>(args)...);
++size_;
return *target;
}
void push_back(const T& value) { emplace_back(value); }
void push_back(T&& value) { emplace_back(std::move(value)); }
void push_front(const T& value) { emplace_front(value); }
void push_front(T&& value) { emplace_front(std::move(value)); }
void pop_back() noexcept {
assert(size_);
std::destroy_at(slot(begin_slot_ + size_ - 1));
--size_;
}
void pop_front() noexcept {
assert(size_);
std::destroy_at(slot(begin_slot_));
++begin_slot_;
--size_;
}
void clear() noexcept {
while (size_) pop_back();
}
};
} // namespace oc::handmade
生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。
七、使用示例与输出
预期输出或状态：
从两端插入 0、1、2、3 后逻辑顺序为 0 1 2 3，即使元素跨越两个块。
示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。
八、复杂度与失效规则
| 操作 | 复杂度 | 说明 |
|---|---|---|
| operator[] | O(1) | 两次索引 |
| push_front/back | 摊还 O(1) | 偶尔扩展块表 |
| pop_front/back | O(1) | 销毁一个对象 |
| 中间 insert | O(n) | 移动较短一侧 |
复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。
九、异常安全与资源管理
- 获取资源后立即交给 RAII 对象或明确记录已构造数量。
- 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
- 只有在所有后续步骤不会失败时才修改不可回滚的链接。
- 析构、释放和关闭路径不得抛异常。
- 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。
十、常见错误
1. 把分段存储误当成单一连续数组
把分段存储误当成单一连续数组会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
2. 扩展块表时移动元素而非块指针
扩展块表时移动元素而非块指针会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
3. 块内偏移没有满足 alignof(T)
块内偏移没有满足 alignof(T)会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
十一、面试追问
- deque 为什么支持随机访问却不保证 data()？
- 块大小如何影响缓存局部性？
- 块表重分配会使哪些迭代器失效？
回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。
十二、练习与自测
- 实现 push_front
- 写跨块边界测试
- 比较 16/64/256 三种块容量
自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。
十三、官方资料与延伸阅读
上一篇：手写 std::list ｜ 下一篇：手写 std::stack