vector
众所周知,存储元素,动态扩容,连续存储的容器 —— vector
不过对其的性能和一些使用上的坑点(?,进行一个简单的记录
对象理解
对于普通的数组而言,我们应该想两件事情 —— 首地址(指针,如何找到这一串连续空间),以及其存储的具体数据
那么对于 vector 也是同样的道理, 也是由 vector 对象本身和其管理的空间中存储的数据这两个部分.
对于最基础的实现,我们可以简单的认为是
template<class T>
class VectorLike
{
T* begin_;
T* end_;
T* capacity_end_;
};对应
vector 对象本身
┌───────────────────────────────────────┐
│ begin_ │ end_ │ capacity_end_ │
└────┬────────┬───────────────┬─────────┘
│ │ │
▼ ▼ ▼
堆内存：
┌─────────────┬─────────────────────────┐
│ 已构造对象 │ 已分配但尚未构造的空间 │
└─────────────┴─────────────────────────┘size / capacity
唔,size 和 capacity 是两个不同概念(废话
size 指的是当前已经存储了多少数据, capacity 是说当前 vector 申请到的总可容纳量 (还是废话
提供了两个方法 ——
reserve表示预留空间,它的语义是 ”我当前的容量至少到 N“, 所以可能改变 capacity ( reserve 传入参数大于当前 capacity 的时候), 但是不改变 sizeresize直接改变 size, 所以可能会触发删除或者新增元素
值得留意的是,clear方法只会清数据,使得size = 0,但是不会释放容量(即capacity不变).
扩容
那不得不先品下扩容过程, 显然,当 size < capacity 的时候,执行一次尾插是不需要执行扩容的,否则则需要扩容
所以此时我们先确定了扩容的时机,排除手动触发的情况,在size == capacity的时候,再插入元素(emplace_back, push_back, insert 等)大概率会自动触发一次扩容
扩容的时候不是简单的在尾部取一块空间然后直接接到现有的空间上,因为可能尾部的空间不足(已经被分配给其他地方占用了),因此扩容的时候实际上 —— (或许还要看看具体实现,不过大体上是这个思路)
- 分配一块更大的连续存储
- 在新存储中移动或复制旧元素
- 构造新元素
- 销毁旧元素
- 释放旧存储
- 更新 vector 的内部边界
所以触发一次扩容是O(N)的时间复杂度,虽然摊还分析一次尾插还是O(1),但是也要注意在使用中不要大量触发扩容行为,下面是 Benchmark 结果 ——
| 元素数量 | 自动扩容 | 预留足够容量 | 每次强制扩容 |
|---|---|---|---|
| 64 | 243 ns | 50.1 ns | 1,767 ns |
| 256 | 356 ns | 111 ns | 9,786 ns |
| 1,024 | 679 ns | 377 ns | 40,279 ns |
| 4,096 | 1,731 ns | 1,494 ns | 368,026 ns |
然后值得注意的是 —— 在发生整个重分配的时候,旧的元素指针/引用/迭代器等都会全部失效(上面其实也做出了解释,因为需要做整个内存的全量搬运)
下面先给出一张表说明指针失效对应情况
| 操作 | 失效范围 |
|---|---|
扩容或 reserve 引起重新分配 | 全部元素指针、引用和迭代器失效 |
| 尾部插入且未扩容 | 原元素仍有效，旧 end() 失效 |
| 中间插入且未扩容 | 插入位置及之后失效 |
erase(pos) | pos 及之后失效 |
clear() | 所有元素引用和迭代器失效，容量通常保留 |
所以一般会规避直接在遍历容器的时候对容器进行直接修改(规避指针失效问题),所以常见的如备份数据/存储commands等,都是不错的设计
删除陷阱
对于一次删除,由于我们需要移动其后续所有的元素,会导致效率比较低(同时也要注意迭代器失效的问题),所以不推荐在有条件的时候批量删除的时候直接使用erase方法
而是推荐使用erase_if方法来对所有符合条件的元素进行删除,因为它的执行逻辑为 ——
- 执行一次扫描
- 保留元素向前跑
- 一次性销毁尾部的所有元素
当然,如果要手动的话,同时不考虑元素之间的顺序或者旧的handle/index失效问题,也可以自己实现一个swap-and-pop方法 ——
void RemoveUnordered(std::vector<Entity>& entities, std::size_t index)
{
assert(index < entities.size());
if (index != entities.size() - 1)
{
entities[index] =
std::move(entities.back());
}
entities.pop_back();
}这样把一次删除中间元素化归成了尾删除的事情,把单次删除的时间复杂度近似降到了O(1),所以在合适的情况也可以试试这种方法
下面依旧给出这三种方法的 Benchmark 结果
| 元素数量 | erase + 迭代器 | std::erase_if | swap-and-pop |
|---|---|---|---|
| 64 | 99.4 ns / 644.100 M items/s | 49.8 ns / 1.284 G items/s | 51.4 ns / 1.245 G items/s |
| 256 | 467 ns / 548.666 M items/s | 93.3 ns / 2.745 G items/s | 98.3 ns / 2.604 G items/s |
| 1,024 | 5,480 ns / 186.868 M items/s | 331 ns / 3.090 G items/s | 363 ns / 2.824 G items/s |
| 4,096 | 81,996 ns / 49.954 M items/s | 1,296 ns / 3.160 G items/s | 1,427 ns / 2.871 G items/s |
高效原因和设计
连续的空间布局具有良好的空间局部性, 所以说在 CPU 载入一个 Cache Line 的时候,往往会载入多个相邻元素,提高访问效率.同时在编译器优化中,也可能通过SIMD等来提升计算效率
在实践中, 我们不能单纯的考虑理论上的时间复杂度,而是要根据实际情况来进行计算, 举个简单例子, 在小批量数据进行查找的时候 —— 看到「查找」第一反应或许是哈希表 (unordered_map) 或者考虑顺序的 map,但是如果在实际运用场景下,考虑到频繁的遍历?顺序要求?等,或许使用 vector + sort + lower_bound 也是一个不错的查找方式
综上所述, 一次构建的只读窗口+多次顺序遍历,那么基本上使用 vector 是不会踩雷(
btw, 合理的数据布局(AoS与SoA)也会影响效率(此事在SIMD与SIMT的note中亦有记录)