如何从排序的向量有效地清除值？ [英] How to erase a value efficiently from a sorted vector?

问题描述

假设 vec 是可移动和可复制对象的排序向量。什么是最有效的方法来删除所有匹配 value 的元素？

Assume that vec is a sorted vector of movable and copyable objects. What is the most efficient way to remove all elements that match value?

这是正确的和最有效的方式？

Is this correct and the most efficient way?

auto lb = std::lower_bound(vec.begin(), vec.end(), value);
vec.erase(lb, std::upper_bound(std::next(lb), vec.end(), value));

复杂性是什么？

推荐答案

我已经用 three 从已排序容器中擦除的四种不同方法。

I've done some brief testing with three four different methods of erasing from a sorted container.

void erase_v1(std::vector<int> &vec, int value)
{
    vec.erase(std::remove(std::begin(vec), std::end(vec), value), std::end(vec));
}

void erase_v2(std::vector<int> &vec, int value)
{
    auto lb = std::lower_bound(std::begin(vec), std::end(vec), value);
    if (lb != std::end(vec) && *lb == value) {
        auto ub = std::upper_bound(lb, std::end(vec), value);
        vec.erase(lb, ub);
    }
}

void erase_v3(std::vector<int> &vec, int value)
{
    auto pr = std::equal_range(std::begin(vec), std::end(vec), value);
    vec.erase(pr.first, pr.second);
}

// Surt's code, doesn't preserve sorted order
void erase_v4(std::vector<int> &vec, int value)
{
    // get the range in 2*log2(N), N=vec.size()
    auto bounds = std::equal_range(vec.begin(), vec.end(), value);

    // calculate the index of the first to be deleted O(1)
    auto last = vec.end() - std::distance(bounds.first, bounds.second);

    // swap the 2 ranges O(equals) , equal = std::distance(bounds.first, bounds.last)
    std::swap_ranges(bounds.first, bounds.second, last);

    // erase the victims O(equals)
    vec.erase(last, vec.end());
}

使用 std :: vector 10,000,000个元素，填充 [0..9] 范围内的随机数，然后排序（MS Visual C ++ 2013）。

Tested with a std::vector of 10,000,000 elements, filled with random numbers in the range [0..9], and then sorted (MS Visual C++ 2013).

清除值 0 （容器正面），代表时间如下：

Erase the value 0 (the front of the container), representative times look like:

time=14.3894 size=8999147 // v1, milliseconds and updated container size
time=11.9486 size=8999147 // v2
time=11.5548 size=8999147 // v3
time=1.78913 size=8999147 // v4 (Surt)

清除 5 （容器中间）：

time=12.8223 size=9000844
time=4.89388 size=9000844
time=4.87589 size=9000844
time=1.77284 size=9000844

擦除 9 （容器末尾）：

time=12.64 size=9000820
time=0.00373372 size=9000820
time=0.00339429 size=9000820
time=1.29899 size=9000820

擦除 13 （值不在容器中）：

Erase 13 (value not in container):

time=11.8641 size=10000000
time=0.002376 size=10000000
time=0.00203657 size=10000000
time=0.00220628 size=10000000

擦除/删除方法总是遍历整个容器并且速度较慢， lower_bound / upper_bound 和 equals_range 多次运行。我更喜欢最后一个版本，因为它是正确，更简单的代码，更少打字。

The erase/remove method always iterates over the entire container and is slower, the lower_bound/upper_bound and equal_range methods are nearly identical over multiple runs. I prefer the last version because it's correct, simpler code, and less typing.

编辑：Timed Surt的代码。它始终以不保留排序顺序为代价。

Timed Surt's code by request. It is consistently fast at the cost of not preserving sorted order.

这篇关于如何从排序的向量有效地清除值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！