第9.4章: 迭代器、左闭范围与失效

概述

本节解释所有 fast_io 容器采用的左闭范围约定，讨论迭代器失效规则，并说明为什么应当尽量优先使用 _index 系列操作。

1. 左闭范围

所有 fast_io 容器都采用左闭（也叫半开）范围约定：范围记作 [first, last)，意思是它包含 first 指向的元素，但不包含 last 指向的元素。

这个约定有几个好处：

begin() 到 end() 覆盖所有元素。
空范围就是 first == last。
距离 last - first 等于元素个数。


#include <fast_io_dsal/vector.h>
#include <fast_io.h>

int main() {
    ::fast_io::vector<::std::size_t> v{10zu, 20zu, 30zu, 40zu, 50zu};

    // Erase elements in range [begin()+1, begin()+3)
    // This removes elements at positions 1 and 2 (values 20 and 30)
    v.erase(v.begin() + 1, v.begin() + 3);
    // v is now {10zu, 40zu, 50zu}
}

2. 迭代器失效

当你修改容器时，已有的迭代器可能失效（指向已被释放或搬移的内存）。弄清哪些操作会使哪些迭代器失效非常关键：

容器	插入会使这些失效	删除会使这些失效
`vector`	所有迭代器（可能发生重新分配）	指向被删元素及其之后所有元素的迭代器
`deque`	所有迭代器（任一端插入都可能重新分配块索引表）	指向被删元素的迭代器；在头部或尾部删除时是所有迭代器；在中间删除时只有被删的迭代器
`list`	不会失效 — 已有迭代器仍然有效	只有指向被删元素的迭代器
`forward_list`	不会失效 — 已有迭代器仍然有效	只有指向被删元素的迭代器
`array`	不适用 — 大小固定，不能插入	不适用 — 大小固定，不能删除

危险：在 vector::push_back() 之后，指向该 vector 的每一个迭代器、引用和指针都可能失效，因为 vector 可能已经重新分配了存储。绝不要在 vector 上跨插入操作缓存迭代器。

3. 优先使用 _index 操作

由于迭代器可能在意想不到的时候失效，在 vector 和 deque 上操作时请优先使用基于下标的操作（insert_index、erase_index 和 operator[]）。它们带边界检查，也不会有失效问题：


// Preferred: index-based
for (::std::size_t i{}; i != v.size(); ++i) {
    if (v[i] == target) {
        v.erase_index(i);
        break;
    }
}

// Dangerous: iterator-based (iterator invalidated by erase)
// for (auto it = v.begin(); it != v.end(); ++it) {
//     if (*it == target) { v.erase(it); break; }  // OK with break
// }

要点

所有容器都使用左闭的 [first, last) 范围。
vector 和 deque 在插入时会使所有迭代器失效。
list 和 forward_list 在插入时从不会使已有迭代器失效。
绝不要在连续容器上跨插入操作缓存迭代器。
在 vector 和 deque 上，为了安全请优先使用 _index 系列操作。