什么容器允许binary_search'ing和随机删除元素？

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也仅适用于已排序的范围.