c++ - 什么容器允许二进制搜索和随机删除元素？

Question

我一直在使用 std::vector 但它变得笨拙，因为它迭代的数据不断增长，我希望能够在随机元素变得多余时过滤掉它们。我在 std::list 的其他地方有这种行为，但无法让 binary_search 很好地处理它。

是否有一些代码可以让 binary_search 重新工作，或者我必须使用更复杂的容器和语法？

        if(binary_search(iter + 1, myLines.end(), line)) {
            firstFound.assign(line);
            if (numFinds++) break;
        }

Answer 1

std::set的查找是O(log(N))，和binary_search完全一样，删除是O(1) 如果你有一个迭代器，如果你没有(查找 + 删除)，则为 O(log(N))。尽管该集合将存储排序的元素，但这对您来说一定没问题，因为 binary_search 也仅适用于排序的范围。