std::vector场景下std::remove与std::find的性能及复杂度对比

1. std::find 与 std::remove 的复杂度及开销差异 #

两者的单次操作时间复杂度均为O(n)，n为操作时对应vector的元素数量，核心差异来自整体逻辑的额外开销：

• 闭集方案的std::find：每次遍历长度为当前闭集的元素数k，k从0逐步增长到角色总数m。额外存在随机索引冲突开销：当房间总数为N时，k越接近N，生成重复索引的概率越高，极端场景（m=N）下最后一次生成有效索引的期望重试次数为N次，整体期望时间复杂度为O(N log N)，N较大时冲突开销会大幅上涨。
• 开集方案的std::remove：每次遍历长度为当前开集的元素数k，k从N逐步降低到N-m，无随机重试开销，总遍历次数为固定值，整体时间复杂度稳定为O(mN)，不会出现性能波动。

2. vector相关操作的性能影响 #

• 反复追加元素：原闭集方案提前调用reserve预分配了足够内存，push_back为均摊O(1)操作，几乎无额外性能损耗。
• erase-remove惯用法：std::remove会将匹配元素移动到vector末尾，erase直接截断尾部，不会触发多次内存重分配，但每次std::remove需要全量遍历当前开集，当N远大于m时，遍历开销会显著高于低冲突下的闭集方案。

两种方案的性能优劣取决于场景：

• 若放置的角色数m远小于房间总数N：闭集方案冲突概率极低，每次std::find遍历长度极小，性能优于开集方案。
• 若放置的角色数m接近房间总数N：开集方案无随机重试开销，性能比闭集方案稳定得多，不会出现后期多次重试的卡顿。

3. 开集方案的优化建议 #

当前开集实现存在不必要的遍历开销，可优化为O(1)级别的删除操作，总时间复杂度降至O(N)，无论m和N的比例如何，性能均远高于原有两种实现：

void RoomsAndCorridorsMapGenerator::PlaceActors() noexcept {
    auto open_set = std::vector<std::size_t>{};
    open_set.resize(rooms.size());
    std::iota(std::begin(open_set), std::end(open_set), std::size_t{0u});
    for(auto* actor : _map->_actors) {
        const auto room_idx = [&]() {
            auto idx_pos = static_cast<std::size_t>(MathUtils::GetRandomIntLessThan(static_cast<int>(open_set.size())));
            auto idx = open_set[idx_pos];
            // 选中元素与末尾元素交换后直接弹出末尾，无需遍历
            std::swap(open_set[idx_pos], open_set.back());
            open_set.pop_back();
            return idx;
        }();
        actor->SetPosition(IntVector2{rooms[room_idx].CalcCenter()});
    }
}

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