vector::insert在中间插入的开销本质是内存搬移，需将插入点后所有元素向后平移，时间复杂度O(n)，与是否reserve无关；仅push_back或空vector的insert(begin(),val)接近O(1)。
vector::insert 在中间位置插入的开销本质是什么
本质是内存搬移：vector::insert 在非尾部位置插入时，必须将插入点之后的所有元素向后平移一位。这涉及 std::move（或拷贝）操作，时间复杂度为 O(n)，其中 n 是插入点后的元素个数。
不是“慢”，而是“必然搬移”——只要底层是连续内存，就绕不开这个代价。
- 插入位置越靠前（比如
begin()），搬移量越大；插入末尾（end()）则不搬移，仅可能触发扩容 - 若元素类型不可移动（如无移动构造函数的类），会退化为深拷贝，开销进一步放大
- 即使预留了足够容量（
reserve()），也**无法避免搬移**——reserve()只影响扩容，不影响插入逻辑
哪些 insert 调用其实很快？
只有两类情况真正接近 O(1)：
-
push_back()或insert(end(), val)：不搬移，仅检查容量；若已reserve()好，就是纯写入 -
insert(begin(), val)且size() == 0（空 vector）：等价于push_back()
注意：insert(begin() + k, val) 即使 k == size() - 1（倒数第二位），也要搬移 1 个元素——它仍触发搬移路径，不是常数时间。
想在中间高效“插入”，该换什么容器？
连续内存和随机访问不能兼得，必须做取舍：
- 需要频繁中间插入/删除 + 不要求随机访问 → 改用
std::list或std::forward_list（insert()是 O(1)，但失去下标访问能力） - 需要随机访问 + 中间修改较频繁 → 考虑
std::deque：两端插入是 O(1)，中间插入仍是 O(n)，但常数因子比vector小（分段内存，搬移的是指针而非元素） - 真要保留 vector 接口又需局部插入优化？可延迟处理：先
push_back()所有新元素，最后统一排序或用索引映射，避免实时搬移
实测差异有多大？一个关键提醒
搬移开销取决于元素大小和构造成本，不是单纯看元素个数：
- 插入 1000 个
int到 10 万元素 vector 的中间：快，因为int移动是 memcpy 级别 - 插入 1 个含
std::string成员的大对象到 100 元素 vector 中间：可能比前者还慢，因为每个后续对象都要调用移动构造函数
别只盯着 insert() 调用本身——检查你插入的类型是否定义了高效的移动构造函数，以及是否真的需要在运行时动态插入。很多场景其实可以预分配+重排，或者改用索引间接访问，绕过物理插入。
