如何高效向已排序std::vector插入元素？寻求最优实现方案

针对有序数字场景，原有的insert_sorted实现依赖std::upper_bound配合vector::insert，但insert操作会触发插入位置后所有元素的移动，若未提前预留空间还会导致内存重新分配，效率不如直接在末尾插入的emplace_back。下面提供一种利用std::rotate优化的实现思路：

核心思路 #

当vector已有足够预留空间时，先通过emplace_back在末尾原地构造元素（避免额外拷贝），再用std::rotate将末尾元素旋转到正确的有序位置——这种方式的元素移动次数和insert相当，但构造环节更高效；若vector空间不足，则 fallback 到原有的insert逻辑（此时扩容不可避免）。

优化后的代码实现 #

template <typename T>
typename std::vector<T>::iterator insert_sorted(std::vector<T>& vec, T item) {
    // 确定元素应插入的位置
    auto insert_pos = std::upper_bound(vec.begin(), vec.end(), item);

    // 若vector有剩余空间，用emplace_back+rotate优化
    if (vec.size() < vec.capacity()) {
        // 在末尾原地构造元素，利用移动语义避免拷贝
        vec.emplace_back(std::move(item));
        // 将最后一个元素旋转到目标位置，完成有序插入
        std::rotate(insert_pos, vec.end() - 1, vec.end());
        return insert_pos;
    }

    // 空间不足时，使用原有insert逻辑（扩容不可避免）
    return vec.insert(insert_pos, std::move(item));
}

效率说明 #

• 有预留空间的场景：emplace_back直接在末尾构造元素，避免了insert操作中“先移动元素再拷贝插入值”的额外拷贝开销；std::rotate的元素移动次数和insert一致，但整体流程更贴合vector的内存布局特性。
• 无预留空间的场景：此时无论哪种方式都需要触发内存扩容，元素移动成本相当，因此直接沿用insert逻辑即可。

使用提示 #

要最大化该实现的效率，建议提前调用vector::reserve预留足够的存储空间，确保大部分插入操作都能走emplace_back+rotate的优化路径。

内容的提问来源于stack exchange，提问作者Ted Zach