手写容器：`flat_map` 与动态数组

flat_map 用一块连续内存表达有序表，插入/删除靠搬移；其底层即有序 vector。考察点：迭代器语义、扩容、异常安全、分配次数。典型题面："Implement std::flat_map in C++, including a working iterator."

一、题面与澄清

常见问法：

A：实现 FlatMap<Key, Value>（insert / find / erase / operator[] + 迭代器），说明设计取舍并写测试；
B：实现简化 vector<T>（push_back / reserve / 迭代器），重点考察扩容与强异常保证；
C：两者兼有（flat_map 的底层就是有序 vector）。

动手前需澄清：

insert 遇重复 key 是拒绝还是覆盖（std::map::insert 拒绝；operator[] / insert_or_assign 覆盖）；
是否提供 operator[]（它要求 Value 可默认构造，接口即约束）；
迭代器失效规则是否按 vector 语义（是，但需明确说明）；
是否需要容量承诺 reserve 与逐操作复杂度承诺。

二、接口与约束

接口：size / empty / capacity / reserve / clear / begin / end / lower_bound / upper_bound / find / operator[] / insert / erase
不变量：底层 vector 始终按 key 严格递增，即「有序且 key 唯一」
复杂度
- find / lower_bound / upper_bound：O(log n)，零分配
- insert / erase：O(n) 搬移 + 均摊一次分配
- 顺序遍历：O(n)，顺序访存
迭代器与失效：随机访问；规则同 vector（扩容后全部失效，否则插入点及其后失效）
生命周期：RAII，Rule of 0（成员 vector 自行管理）
异常安全：insert / operator[] 在扩容路径上为强保证
前置条件：Key 满足 Less 定义的严格弱序

三、精简版：有序数组 `FlatMap`（先交这个）

实现范围：最小可用集 —— size / empty / begin / end / find / insert / erase。只保留「增删查 + 顺序遍历」，返回值为指针而非迭代器，因此无需 const 重载。

cpp

#pragma once
#include <algorithm>
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template <class K, class V, class Less = std::less<K>>
class FlatMap {
 public:
  using value_type = std::pair<K, V>;
  using size_type = std::size_t;

  size_type size() const noexcept { return v_.size(); }
  bool empty() const noexcept { return v_.empty(); }
  value_type* begin() noexcept { return v_.data(); }
  value_type* end() noexcept { return v_.data() + v_.size(); }

  V* find(const K& k) {                                  // 命中返回指向值的指针，否则 nullptr
    iterator it = lower(k);
    return (it != v_.end() && !Less{}(k, it->first)) ? &it->second : nullptr;
  }
  std::pair<V*, bool> insert(K k, V val) {               // 已存在 -> {现有值, false}，不覆盖
    iterator it = lower(k);
    if (it != v_.end() && !Less{}(k, it->first)) return {&it->second, false};
    it = v_.emplace(it, std::move(k), std::move(val));
    return {&it->second, true};
  }
  size_type erase(const K& k) {
    iterator it = lower(k);
    if (it == v_.end() || Less{}(k, it->first)) return 0;
    v_.erase(it);
    return 1;
  }

 private:
  using iterator = typename std::vector<value_type>::iterator;
  iterator lower(const K& k) {                           // 第一个 >= k
    return std::lower_bound(v_.begin(), v_.end(), k,
                            [](const value_type& e, const K& key) { return Less{}(e.first, key); });
  }
  std::vector<value_type> v_;                            // 不变量：按 key 严格递增
};

小问答

这个版本差在哪？ 无 lower_bound / upper_bound / operator[] / capacity / reserve / clear，也无 const 重载。
与 std::flat_map 的差别？ 标准版把 keys 与 values 拆成两个 vector（二分不碰 values），并带 key_compare 与分配器模板参数；本版单向量 pair，代码短但比较路径访存更多。
与 std::map 的差别？ 无节点分配、二分顺序访存；代价是插入/删除 O(n) 搬移、迭代器随扩容失效。
复杂度与顺序？ find O(log n) 零分配；insert / erase O(n) 搬移 + 均摊一次分配；遍历顺序 = key 升序。
什么时候必须升级到完整版？ 调用方需要边界查询、operator[]、容量预留或 const 访问时。

四、完整版：全接口 `FlatMap`

实现范围：题面所需全部接口（size / empty / capacity / reserve / clear / begin / end / lower_bound / upper_bound / find / operator[] / insert / erase）。未实现 const 迭代器重载、erase(iterator)、swap、比较运算符与自定义分配器。

cpp

#pragma once
#include <algorithm>
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template <class K, class V, class Less = std::less<K>>
class FlatMap {
 public:
  using value_type = std::pair<K, V>;
  using iterator = typename std::vector<value_type>::iterator;
  using size_type = std::size_t;

  size_type size() const noexcept { return v_.size(); }
  bool empty() const noexcept { return v_.empty(); }
  size_type capacity() const noexcept { return v_.capacity(); }
  void reserve(size_type n) { v_.reserve(n); }
  void clear() noexcept { v_.clear(); }
  iterator begin() noexcept { return v_.begin(); }
  iterator end() noexcept { return v_.end(); }

  iterator lower_bound(const K& k) {                   // 第一个 >= k
    return std::lower_bound(v_.begin(), v_.end(), k,
                            [](const value_type& e, const K& key) { return Less{}(e.first, key); });
  }
  iterator upper_bound(const K& k) {                   // 第一个 > k，比较器方向与 lower_bound 相反
    return std::upper_bound(v_.begin(), v_.end(), k,
                            [](const K& key, const value_type& e) { return Less{}(key, e.first); });
  }
  iterator find(const K& k) {
    iterator it = lower_bound(k);
    return (it != v_.end() && !Less{}(k, it->first)) ? it : v_.end();   // 等价 = 互不小于
  }
  V& operator[](const K& k) {                          // 不存在则值初始化插入
    iterator it = lower_bound(k);
    if (it != v_.end() && !Less{}(k, it->first)) return it->second;
    return v_.emplace(it, k, V{})->second;
  }
  std::pair<iterator, bool> insert(K k, V val) {       // 已存在 -> {现有元素, false}，不覆盖
    iterator it = lower_bound(k);
    if (it != v_.end() && !Less{}(k, it->first)) return {it, false};
    it = v_.emplace(it, std::move(k), std::move(val)); // 由 vector 提供强异常保证
    return {it, true};
  }
  size_type erase(const K& k) {
    iterator it = find(k);
    if (it == v_.end()) return 0;
    v_.erase(it);
    return 1;
  }

 private:
  std::vector<value_type> v_;                          // 不变量：按 key 严格递增
};

技术选型

存储：单块有序 vector<pair<K, V>>，而非 std::map 之类的节点式容器
- 二分与顺序遍历都只做顺序访存，整个容器一次分配。
- 代价是插入/删除 O(n) 搬移、迭代器随扩容失效，因此读多写少时适用。
等价判定写作 !Less{}(k, it->first)
- 只依赖比较器（严格弱序），不要求 Key 定义 operator==。
- lower_bound 已保证 !less(*it, k)，故只需再判一次反向比较即等价。
lower_bound 与 upper_bound 使用方向相反的比较器
- 标准规定前者调用 comp(元素, 值)、后者调用 comp(值, 元素)，写反即边界 off-by-one。
插入用 v_.emplace(position, ...)，而非 push_back + 排序
- 就位插入到正确位置，同时获得 vector 的强异常保证与均摊一次分配。
- push_back + 排序会丢失强保证，并可能残留半排序状态。
insert 返回 std::pair<iterator, bool>
- 与 std::map::insert 一致：调用方一次拿到「是否新插入」与落点。
operator[] 单独实现，不复用 insert
- insert 对已存在的 key 不修改值，而 operator[] 需返回可写引用。
- operator[] 还额外要求 Value 可默认构造，这一约束应由接口说明而非隐藏。

小问答

比精简版多了什么？ lower_bound / upper_bound 边界查询、operator[] 插入式取值、容量接口，以及边界断言所需的随机访问迭代器。
与 STL 还差什么？ 无 erase(iterator) / swap / 比较运算符 / try_emplace / insert_or_assign、无分配器与 key_compare 模板参数、无 std::flat_map 的双 vector 布局。
迭代器失效规则？ 同 vector：扩容或 reserve 后全部失效，其余情况插入点及其后失效。
为什么返回 std::pair<iterator, bool>？ 与 std::map::insert 对齐，调用方一次拿到「是否新插入」与落点。

五、配套：动态数组（扩容与强异常保证）

实现范围：精简版，覆盖扩容与值语义（构造/拷贝/移动/析构、reserve / clear / swap / push_back / emplace_back、裸指针迭代器、operator[]）。未实现 insert / erase / resize / at / assign、比较运算符、分配器模板参数与迭代器封装。

cpp

template <class T>
class MyVector {
 public:
  MyVector() = default;
  MyVector(const MyVector& o) { reserve(o.size_); for (const T& x : o) emplace_back(x); }
  MyVector& operator=(const MyVector& o) { MyVector tmp(o); swap(tmp); return *this; }   // copy-and-swap
  MyVector(MyVector&& o) noexcept : data_(o.data_), size_(o.size_), cap_(o.cap_) {
    o.data_ = nullptr; o.size_ = o.cap_ = 0;            // 移动后源必须置空，否则 double free
  }
  MyVector& operator=(MyVector&& o) noexcept {
    if (this != &o) { clear(); ::operator delete(data_);
                      data_ = o.data_; size_ = o.size_; cap_ = o.cap_;
                      o.data_ = nullptr; o.size_ = o.cap_ = 0; }
    return *this;
  }
  ~MyVector() { clear(); ::operator delete(data_); }

  std::size_t size() const noexcept { return size_; }
  std::size_t capacity() const noexcept { return cap_; }
  bool empty() const noexcept { return size_ == 0; }
  T* data() noexcept { return data_; }
  T* begin() noexcept { return data_; }              T* end() noexcept { return data_ + size_; }
  const T* begin() const noexcept { return data_; }  const T* end() const noexcept { return data_ + size_; }
  T& operator[](std::size_t i) noexcept { return data_[i]; }
  const T& operator[](std::size_t i) const noexcept { return data_[i]; }

  void reserve(std::size_t n) { if (n > cap_) grow(n); }
  void clear() noexcept { for (std::size_t i = 0; i < size_; ++i) data_[i].~T(); size_ = 0; }
  void swap(MyVector& o) noexcept {
    std::swap(data_, o.data_); std::swap(size_, o.size_); std::swap(cap_, o.cap_);
  }
  void push_back(const T& x) { emplace_back(x); }
  void push_back(T&& x) { emplace_back(std::move(x)); }

  template <class... Args> T& emplace_back(Args&&... args) {
    if (size_ == cap_) grow(cap_ ? cap_ * 2 : 1);
    ::new (static_cast<void*>(data_ + size_)) T(std::forward<Args>(args)...);
    return data_[size_++];
  }

 private:
  void grow(std::size_t n) {
    T* p = static_cast<T*>(::operator new(n * sizeof(T)));
    std::size_t i = 0;
    try {
      // 移动构造 noexcept 才移动，否则拷贝：搬移途中抛异常时，已移动元素无法复原
      for (; i < size_; ++i)
        ::new (static_cast<void*>(p + i)) T(std::move_if_noexcept(data_[i]));
    } catch (...) {
      for (std::size_t j = 0; j < i; ++j) p[j].~T();   // 回滚已构造部分
      ::operator delete(p);
      throw;                                            // 旧缓冲保留，即强异常保证
    }
    for (std::size_t j = 0; j < size_; ++j) data_[j].~T();
    ::operator delete(data_);
    data_ = p; cap_ = n;
  }

  T* data_ = nullptr; std::size_t size_ = 0, cap_ = 0;
};

技术选型

存储与生命周期：::operator new 取原始内存 + placement new 构造 + 显式析构
- 因此不要求 T 可默认构造，也支持按需构造/析构。
扩容策略：容量翻倍
- 均摊 O(1)；若每次只增长 1，n 次插入的搬移总量为 O(n²)。
搬移方式由 std::move_if_noexcept 决定
- 搬移一半抛异常时，已被移动的元素处于 moved-from 状态、无法复原，容器无法回滚。
- 故仅当「移动构造 noexcept」或「类型不可拷贝」时才移动，否则退化为拷贝。
- 这是强异常保证成立的前提，细节见 vector-realloc.md。
强异常保证：先在新缓冲构造，成功后再析构并释放旧缓冲
- 中途抛异常时回滚已构造部分并释放新缓冲，旧缓冲原样保留。
拷贝赋值用 copy-and-swap
- 同时解决自赋值与异常泄漏；拷贝构造失败时目标对象未被改动。
移动构造标 noexcept 且将源置空
- 前者决定容器是否敢以移动方式搬移；后者避免 double free。

小问答

与 std::vector 的差别？ 无分配器模板参数、无 insert / erase / resize / at / assign，迭代器即裸指针（无调试迭代器检查），也没有 vector<bool> 特化。
扩容系数为什么取 2？ 保证均摊 O(1)；libc++ / MSVC 有 1.5 倍实现，省内存但复用性不同，均摊结论不变。
异常安全边界？ 扩容为强保证（新缓冲构造成功后才替换）；emplace_back 自身构造抛异常时元素集合不变。
移动后源对象的状态？ data_ == nullptr、size_ == 0（本版是确定状态，标准库只要求「合法但未指定」）。

六、边界与测试

空表：find / lower_bound / upper_bound 返回 end()，erase 返回 0，begin() == end()；
重复 key：insert 返回 {现有元素, false} 且值不变；operator[] 为覆盖语义；
删除首 / 中 / 尾、删除不存在的 key、连删两次、删空后重插；
极限 key：INT_MIN / INT_MAX、空串与超长串；
不变量：任一操作后按 key 严格递增且无重复；
对拍：与 std::map 执行同一随机操作序列，逐步比较 size 与全量遍历顺序；
分配纪律：插入 1000 个元素后容器仅有 1 块存活堆内存；find 零分配；n 次插入总分配数约 log2(n)+1；
强异常保证：在 size == capacity 时插中间位置、令元素构造抛异常，验证容器状态不变、无泄漏、仍可用。

七、高频问答

Q1. 为什么不用 `std::map`？

节点式容器每次查找需约 log n 次指针跳转（潜在 cache miss），且每元素一次分配； flat 版为连续二分加一次分配。代价是插入/删除 O(n) 搬移、迭代器会失效——读多写少时选 flat。

Q2. `std::flat_map` 为什么由两个 `vector`（keys + values）构成？

二分只访问 keys（8 字节/元素，相对 pair 的 16 字节以上），比较路径访存减半；代价是插入/删除需同时维护两个向量的一致性。

Q3. 迭代器何时失效？

同 vector：扩容或 reserve 导致全部失效；其余情况插入点及其后失效。reserve 是唯一会让迭代器提前失效的调用。

Q4. `insert` 的强异常保证来源？

来自 vector::emplace/insert 的先构造后替换。若手写为 push_back + std::sort，该保证丢失，且可能残留半排序状态。

Q5. 行为什么不统一用 `std::move`？

非 noexcept 的移动构造在搬移途中抛异常会使源对象不可恢复，容器无法回滚；标准库因此在 is_nothrow_move_constructible || !is_copy_constructible 时才移动。

Q6. `operator[]` 能否复用 `insert`？

不能。insert 对已存在的 key 不修改值，而 operator[] 需返回可写引用；且 operator[] 要求 Value 可默认构造。

Q7. `clear()` 之后是否 `shrink_to_fit`？

不必要。shrink_to_fit 为 O(n) 搬移加一次分配，而清空通常意味着即将复用。

Q8. 多线程与大规模场景

只读并发在容器已达最终大小且无写者时安全；单写多读可用「构造新副本 + 原子发布指针」（见并发件）。数据量放大后按 key 前缀或时间窗分片；再大则改用 LSM / 磁盘索引。

八、常见错误

错误	后果
插入位置写成 `end()`	顺序破坏，二分查找随之失效
`insert` 对已存在 key 覆盖值	语义与 `std::map::insert` 不符
`erase` 用 `pop_back` 或删错位置	删除的不是目标元素
`lower_bound` / `upper_bound` 比较器方向写反	边界查找 off-by-one
二分中写 `k == e.first`	`Key` 仅提供比较器时无法编译
每次插入都 `reserve(size()+1)`	均摊 O(1) 退化为 O(n) 搬移与 O(n) 次分配
先取 `it` 再 `reserve`，之后继续使用 `it`	迭代器已失效（段错误）
移动构造未标 `noexcept`	容器退回拷贝，零拷贝优化失效
移动后未将源置空	double free

评分器：livecoding/tasks/t04_flat_map/（15 个用例、与 std::map 的 20000 步对拍、分配纪律、强异常保证；上述错误以 mutation 注入参考实现时 10/10 全部被判定为红）。

手写容器：flat_map 与动态数组 ​

一、题面与澄清 ​

二、接口与约束 ​

三、精简版：有序数组 FlatMap（先交这个） ​

小问答 ​

四、完整版：全接口 FlatMap ​

技术选型 ​

小问答 ​

五、配套：动态数组（扩容与强异常保证） ​

技术选型 ​

小问答 ​

六、边界与测试 ​

七、高频问答 ​

Q1. 为什么不用 std::map？ ​

Q2. std::flat_map 为什么由两个 vector（keys + values）构成？ ​

Q3. 迭代器何时失效？ ​

Q4. insert 的强异常保证来源？ ​

Q5. 行为什么不统一用 std::move？ ​

Q6. operator[] 能否复用 insert？ ​

Q7. clear() 之后是否 shrink_to_fit？ ​

Q8. 多线程与大规模场景 ​

八、常见错误 ​

手写容器：`flat_map` 与动态数组

一、题面与澄清

二、接口与约束

三、精简版：有序数组 `FlatMap`（先交这个）

小问答

四、完整版：全接口 `FlatMap`

技术选型

小问答

五、配套：动态数组（扩容与强异常保证）

技术选型

小问答

六、边界与测试

七、高频问答

Q1. 为什么不用 `std::map`？

Q2. `std::flat_map` 为什么由两个 `vector`（keys + values）构成？

Q3. 迭代器何时失效？

Q4. `insert` 的强异常保证来源？

Q5. 行为什么不统一用 `std::move`？

Q6. `operator[]` 能否复用 `insert`？

Q7. `clear()` 之后是否 `shrink_to_fit`？

Q8. 多线程与大规模场景

八、常见错误