如何从排序向量中有效地删除一个值？

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

这是正确且最有效的方法吗？

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

复杂程度如何？ （考虑到擦除后所需的任何移动）。

我已经使用三四种不同的从排序容器中擦除的方法进行了一些简短的测试。

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::vector10,000,000 个元素，用范围内的随机数填充[0..9]，然后排序 (MS Visual C++ 2013)。

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

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)

Erase 5（容器的中间）：

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

Erase 9（容器的末端）：

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

Erase 13（值不在容器中）：

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

The erase/remove方法总是迭代整个容器并且速度较慢，lower_bound/upper_bound and equal_range多次运行的方法几乎相同。我更喜欢最后一个版本，因为它正确、代码更简单并且打字更少。

编辑：定时苏尔特的代码按要求。它始终保持快速，但代价是不保留排序顺序。