c++ - 与 std::vector 的 std::find 相比，std::remove 的性能如何？

Question

背景

我最近重构了一些将演员置于世界中的代码。每个房间一名演员。

我最初的实现使用一个封闭集std::vector来跟踪不再可用的房间的索引：

void RoomsAndCorridorsMapGenerator::PlaceActors() noexcept {
    const int room_count = static_cast<int>(rooms.size());
    auto closed_set = std::vector<std::size_t>{};
    closed_set.reserve(room_count);
    for(auto* actor : _map->_actors) {
        const auto room_idx = [&]() {
            auto idx = static_cast<std::size_t>(MathUtils::GetRandomIntLessThan(room_count));
            while(std::find(std::begin(closed_set), std::end(closed_set), idx) != std::end(closed_set)) {
                idx = static_cast<std::size_t>(MathUtils::GetRandomIntLessThan(room_count));
            }
            closed_set.push_back(idx);
            return idx;
        }(); //IIIL
        actor->SetPosition(IntVector2{rooms[room_idx].CalcCenter()});
    }
}

那是：

1. 生成随机索引。
2. 在向量中搜索生成的索引。
3. 如果找到，请转到步骤 1。
4. 将新生成的房间索引添加到封闭集中。
5. 对于每个参与者，从步骤 1 继续。

我重构的实现使用了一个开放集：

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 = open_set[static_cast<std::size_t>(MathUtils::GetRandomIntLessThan(static_cast<int>(open_set.size())))];
            open_set.erase(std::remove(std::begin(open_set), std::end(open_set), idx), std::end(open_set));
            return idx;
        }(); //IIIL
        actor->SetPosition(IntVector2{rooms[room_idx].CalcCenter()});
    }
}

IE：

1. 根据房间数量预先生成可用索引列表。
2. 从列表中选择一个随机值。
3. 从列表中删除该值。
4. 对于每个参与者，从步骤 2 继续。

这简化了代码和算法，但我不确定复杂性。

问题

std::find向量与std::remove时间和复杂度相比如何？

我不确定重复的附加/擦除删除习语是否也有效果。

标签： c++time-complexityc++17big-o