C++ std::vector 异常安全

C++ std::vector 的各种实现细节

Posted by Ciel's Paperplane on October 31, 2024

图片

1. 分配器

(1) 空基类优化

std::vector 的内部需要存储一个分配器，而默认分配器 std::allocator 是一个空类，所以需要 EBO。需要注意的是很多标准库（比如 libstdc++）乃至第三方库（比如 folly）实现都直接让本体（或者内部实现类）继承了分配器。这种实现的问题在于标准从未规定分配器是不能为 final 类的，所以严格意义上来说这是这些实现的一个缺陷。

libc++ 的实现就比较好，用 compressed_pair 把一根指针和分配器打包在了一起，这个类会判断它的两个组成部分是否为空类且不为 final 类，来选择继承与否。

(2) fancy pointer

分配器的 pointer 别名是可以为 fancy pointer 的，意思是虽然 std::allocator<T> 里的 pointer 就是 T*，但是自定义的分配器的 pointer 可以为任何包装类型（也就是一个用户定制点）。而 std::vector<T> 里的 pointer 也是 std::allocator_traits<Allocator>::pointer，所以这代表了各种对 pointer 的操作前都需要进行解包操作。

最简单的例子就是 T* data(); 函数，如果直接返回成员变量 pointer begin_; 是不行的（如果有非 explicit 的自动解包倒也行）。

最脑溢血的地方在于这个解包用的 std::to_address 函数是 C++20 才进入标准，而标准库在此之前都有自己的 std::__to_address 内部函数。

这个函数的 cppreference 的例子就是最重要的使用场景：

template<class A>
auto allocator_new(A& a) {
    auto p = a.allocate(1);
    try {
        std::allocator_traits<A>::construct(a, std::to_address(p));
    } catch (...) {
        a.deallocate(p, 1);
        throw;
    }
    return p;
}

template<class A>
void allocator_delete(A& a, typename std::allocator_traits<A>::pointer p) {
    std::allocator_traits<A>::destroy(a, std::to_address(p));
    a.deallocate(p, 1);
}

2. 迭代器

(1) SFINAE

std::vector 的构造函数、assign、insert 等都会有类似如下的重载版本：

vector(size_type count, const T& value, const Allocator& alloc = Allocator());

template<class InputIt>
vector(InputIt first, InputIt last, const Allocator& alloc = Allocator());

对于迭代器范围版本，标准说“此重载只有在 InputIt 满足输入迭代器时才会参与重载决议，以避免与重载 (3) 的歧义”。因为如果是 std::vector<size_t> 的话，迭代器版本构造函数也能实例化成 InputIt 为 size_t 的版本。所以这里需要 SFINAE 来限制 InputIt，具体写法有很多种，个人觉得最有意思的一个写法是：

template<class InputIt, class IteratorCategory = typename std::iterator_traits<InputIt>::iterator_category>
vector(InputIt first, InputIt last, const Allocator& alloc = Allocator());

在这个写法下，如果 InputIt 不为迭代器那么就取不出 iterator_category，自然就丢弃了这个重载。然后取出的 IteratorCategory 可以帮助下面第 (2) 点完成标签分发。

(2) input iterator

std::vector 在可知插入元素个数的情况下，可以提前分配好足够的内存，避免重分配，所以对于大多数迭代器范围来说，事先 std::distance(first, last) 拿到长度也是必须的。

但是有一个特殊的迭代器叫输入迭代器，比如说从标准输入里读取数据时用的就是这种迭代器。这种迭代器有一个特点是它只能单趟迭代，每次 operator++ 都会使当前的数据失效。所以绝不能用 std::distance(first, last) 来计算长度，而只能选择不停 emplace_back。

而对于 insert 来说，如果碰上输入迭代器了，一般做法是先全部 emplace_back 至末尾，再调用 std::rotate 将末尾那部分插入的数据旋转至插入位置。

(3) contiguous iterator

这是一个显而易见的优化，当迭代器满足 C++20 contiguous iterator（比如指针）且类型 T 满足 std::is_trivially_copyable 时，可以直接调用 std::memcpy 而不必循环范围一个个构造元素。

3. 自引用

(1) 扩容时

以 emplace_back 为例，标准没有明确规定这样的操作是否合法：v.emplace_back(v[0]);，但是标准库都应该支持这样的操作因为标准没有允许它不合法。而 folly 的实现则不支持。

所以问题在于 emplace_back 的参数都是引用，所以 v[0] 需要直到构造元素时都一直合法。但是天真的实现里遇到空间不够扩容时会直接写类似 reserve(v.capacity() * 2); 再重复一次 emplace_back 的代码，那么 v[0] 此时已经是一个悬空引用了。

(2) insert 时

v.insert(v.begin(), v[0]) 需要将包括插入位置 v.begin() 的后续所有元素全部往后移动一个单位，所以如果插入元素在需要移动元素的范围内，也需要妥善处理。

4. 异常安全

(1) deallocate 后继续 allocate 前记得指针赋空

由于 allocate 可能抛出异常，抛出异常会调用 std::vector 的析构函数，如果 deallocate 后没有赋空就直接 allocate 的话，析构函数时判断野指针不为空就会导致程序崩溃。

(2) emplace_back 的强异常保证

强异常保证指的是当抛出异常时，保证当前状态与调用此函数前完全一样。

由于标准规定 emplace_back 在内的某些函数需要强异常保证，在扩容时将元素一个个从旧内存移动到新内存时，会判断 T 是否满足 std::is_nothrow_move_constructible。如果移动构造可能会抛出异常，那么在移动过程中可能就会出现抛出了异常而原始位置的部分元素已经被移动而无法恢复到之前状态的情况。当然肯定不能在 catch 块中再搬回去因为这个过程还可能抛出异常让程序直接终止。

所以为了强异常保证，如果移动构造会抛出异常这个过程就会选择调用拷贝构造，来保证原始位置的元素完整性。

但是如果元素压根不能拷贝构造，而移动构造还会抛出异常的话，标准这时就不要求强异常保证了，而会直接调用会抛出异常的移动构造。

5. 其它

(1) emplace 与 insert 并不相同

push_back 的实现可以直接调用 emplace_back，但是 insert 的实现不可以直接调用 emplace。因为如果插入位置 pos 不合适的话，场景将会是对某个元素赋值成插入元素。所以 insert 代表的是 *pos = value; 而 emplace 则是 *pos = T(std::forward<Args>(args)...);。

所以 emplace(value) 会先拷贝构造一遍 value 再移动赋值给 *pos，而 insert(value) 则是直接拷贝赋值给 *pos。

(2) emplace_back 不是 push_back 的超集

虽然 push_back 的实现可以直接调用 emplace_back，但是 emplace_back 不是 push_back 的超集，因为之前帖子中讲过 {...} 不能被模板推导出 std::initializer_list。

此外，emplace_back 相比 push_back 需要做模板类型推导和实例化等额外的工作，对于编译期时间负担会稍微重一点，当然我并不在乎。

Ciel's Paperplane

作诗中...
CATALOG