如何从排序的矢量中有效地清除值？

Question

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

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

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

什么是复杂性？ （考虑到擦除后需要的任何移动）。

Answer 1

我已经做了从排序容器擦除四种不同的方法一些简要的测试。

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一个元素，在范围[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) 

擦除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 

Erase 13（值不会在容器）：

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

的erase/remove方法总是在整个容器进行迭代，并且是越慢，lower_bound/upper_bound和equal_range方法是在多次运行几乎相同。我更喜欢最新的版本，因为它是正确的，更简单的代码，并减少打字。

编辑：定时Surt's code的要求。它始终是以不保存排序顺序为代价的快速。

Answer 2

这在value实际上并未出现在vec中的情况下不正确。因此，在最起码你必须做的：

auto lb = std::lower_bound(vec.begin(), vec.end(), value); 
if (lb != vec.end() && *lb == value) { 
    vec.erase(lb, std::upper_bound(std::next(lb), vec.end(), value)); 
} 

至于最有效的问题：我相信，在一般情况下，什么都不知道会发生什么是在vec，是的。复杂性仍然是O(N)，因为erase()是O(N) - 如果您像第二个元素一样擦除，则无法真正进行非线性擦除。但是在寻找擦除范围方面，O(log N)就像它得到的那样好，而且你得到了它。

upper_bound()或只是find_if()对第二部分更好的问题完全取决于您是否有可能拥有大量value s。更可能有很多，使用upper_bound()，更可能是唯一的，使用find_if()。

Answer 3

一个解决方案，使得矢量在擦除后不被排序。

// 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.last); 

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

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

std::remove是O（N），并将该溶液也做写操作最少。如果等于接近n这个可能没那么伟大的想法:)