如何高效地从C++向量中删除元素

Question

我有一个形如以下所示的一对向量(V1,V2)的向量对pairV1V2：

(1,2,3),(938,462,4837) -> (V1,V2)
(3,9,13),(938,0472,944)
(81,84,93),(938,84,845)

然后我需要保留以下内容：

(1,2,3),(938,462,4837) -> (V1,V2)
(3,9,13),(938,0472,944)
(81,84,93),(84,845)

我需要从头开始扫描pairV1V2，只要任何两个V1不相等，我就需要从V2中删除交集元素。我编写了以下代码来执行此操作。然而，我的代码非常低效，因为我的向量pairV1V2很大，而且它在V2中有许多元素（约十亿个）。

int main(int argc, char** argv) {
    std::vector<std::pair<std::vector<unsigned>, std::vector<unsigned> > > pairV1V2;
    std::vector<std::pair <std::vector<unsigned>,std::vector<unsigned> > >::iterator itm2,lm2=pairV1V2.end();
    for(std::vector<std::pair <std::vector<unsigned>,std::vector<unsigned> > >::iterator itm=pairV1V2.begin(), lm=pairV1V2.end(); itm!=lm; ++itm)
    {
        //Outer values
        vector<unsigned> outerV1=(*itm).first;
        vector<unsigned> outerV2=(*itm).second;
        sort(outerV2.begin(), outerV2.end());
        itm2=itm;
        itm2++;
        for(itm2;itm2!=lm2;++itm2)
        {
            vector<unsigned> innerV1=(*itm2).first;
            vector<unsigned> innerV2=(*itm2).second;
            vector<unsigned> setDiffV1;
            std::set_difference(innerV1.begin(), innerV1.end(), outerV1.begin(), outerV1.end(),
                                                      std::inserter(setDiffV1, setDiffV1.end()));            
            if(setDiffV1.size()==0) //check whether any two V1's are different
            {                 
                sort(innerV2.begin(), innerV2.end());
                if((itm->second.size()!=0)&&(itm2->second.size()!=0)){                                
                    std::vector<unsigned> delIntersectingElem;
                    std::set_intersection(outerV2.begin(),outerV2.end(),innerV2.begin(), innerV2.end(),
                              std::back_inserter(delIntersectingElem));

                   if(delIntersectingElem.size()!=0) //if there are intersecting V2's
                   {                    
                        for(std::vector<unsigned>::iterator its=(itm2->second).begin(),ls=(itm2->second).end();its!=ls;)
                        { 
                            //if *its is present in delIntersectingElem then delete it.
                            if(!(std::find(delIntersectingElem.begin(), delIntersectingElem.end(), (*its)) == delIntersectingElem.end()))
                            {
                                (itm2->second).erase(its); //delete intersecting elements from inner v2
                                ls--;
                            }else{
                                ++its;
                            }
                        }                    
                    }
                }
            } 
        }
    }    
    return 0;
}

请有人帮我改进我的现有代码——它可以给出正确答案（在这个例子中，为了简洁起见，可能会漏掉一些情况——但是该代码可以处理所有情况），但是非常慢（由perf对角化）。如果能在我的现有代码中提出改进意见，我将不胜感激。然而，如果两种代码的逻辑相同，则新算法也是可接受的。

- Steg Verner

---

如果你要进行大量的删除和顺序访问，你考虑使用std::list了吗？ - user4581301

@user4581301 好的，我不知道std::list，你能告诉我如何使用std::list来改进我的现有代码吗？ - Steg Verner

如果您需要帮助改进代码，建议您访问http://codereview.stackexchange.com/而不是Stack Overflow。 - kfsone

@Christophe 嗯...你是正确的。 - Steg Verner

另一个想法，不是使用std::set_intersection然后删除，为什么不使用std::set_difference呢？ - user4581301

Answer 1

有一个不太常用的STL算法叫做remove_if，它允许您高效地（O(n)）从容器中删除所有与谓词匹配的元素。如果您有一个vector或deque，它会非常有用，因为它们对于在“中间”位置上的元素进行昂贵的（O(n)）删除操作。但是，您需要知道remove_if并没有实际删除任何元素，它只是将不符合谓词的所有元素移动到您指定的范围的前面。因此，“erase_if”的规范方式是（在此示例中，将删除所有奇数整数）：

std::vector ints = …;
ints.erase(std::remove_if(begin(ints), end(ints), [](int i) { return i%2 != 0; }), end(ints));

解释： remove_if 移动所有与谓词不匹配的整数（即此示例中的偶数整数）到前面，并返回一个迭代器，指向这些元素的最后一个。然后，我们使用 vector<int>::erase 的区间重载实际上删除从此元素开始到向量末尾的所有元素。

例如，假设我们有 ints == {5,7,4,10,9,16,20,6}。 remove_if 会将 ints 转换为 {4,10,16,20,6,UNSPEC,UNSPEC,UNSPEC}，其中我使用 UNSPEC 表示任何未指定的值，并且它还会返回一个迭代器，指向第一个 UNSPEC 元素。然后，我们删除具有未指定值的所有元素，并得到所需的结果 {4,10,16,20,6}。

更新：关于之前的答案，我想指出 remove_if 是稳定的，即它不会更改剩余元素的顺序。

- Arne Vogel

Answer 2

从向量中删除元素的最有效方法是后置交换技巧，但这仅适用于您不关心顺序的情况。

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    auto it = v.begin() + 5;
    // replace the current element with the back of the vector,
    // then shrink the size of the vector by 1.
    *it = std::move(v.back());
    v.pop_back();

    for (auto n : v) {
        std::cout << n << " ";
    }
    std::cout << "\n";
}

http://ideone.com/0jbWHZ

如果你知道将会有很多删除或一个非常大的向量，你可以通过使用这个技巧来保持效率，在进行删除后不要++当前迭代器，并在到达末尾时使用std::sort()对向量进行排序。

#include <algorithm>
#include <iostream>
#include <vector>

//! Efficiently remove an element from a vector without
//! preserving order. If the element is not the last element
//! in the vector, transfer the last element into its position
//! using a move if possible.
//! Regardless, we then shrink the size of the vector deleting
//! the element at the end, which will either be destructed or
//! the element we were deleting.
//! @note: Effectively invalidates the current iterator.
template<class ValueType>
bool unstable_remove(
    typename std::vector<ValueType>& container,
    typename std::vector<ValueType>::iterator it
    )
{
    // Leave in-situ if we are already the tail element.
    auto lastEl = container.end() - 1;
    if (it != lastEl) {
        // overwrite this element with what is in the last,
        // which should have the same effect as deleting this.
        *it = std::move(*lastEl);
    }
    // release the last cell of the vector, because it should
    // now either be destructed or contain the value we were
    // deleting.
    container.pop_back();
}

int main()
{
    std::vector<int> ints { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    auto it = ints.begin();
    while (it != ints.end()) {
        if ((*it % 3) == 0) {
            unstable_remove(ints, it);
            // do not pass go / ++it
            continue;
        }
        ++it;
    }
    std::cout << "after removes:\n";
    for (auto val : ints)
        std::cout << val << " ";
    std::cout << "\n";
    std::sort(ints.begin(), ints.end());
    std::cout << "after sort:\n";
    for (auto val : ints)
        std::cout << val << " ";
    std::cout << "\n";
}

生成(http://ideone.com/hGZPOC)

after removes:
1 2 10 4 5 8 
after sort:
1 2 4 5 8 10 

--- 编辑 2 ---

这是您的代码可读性的清理，我还放弃了您的结尾捕获，因为...您正在删除元素。

#include <vector>
#include <cstdint>

using vec_t = std::vector<uint32_t>;
using vecpair_t = std::pair<vec_t, vec_t>;
using pairvec_t = std::vector<vecpair_t>;

int main(int argc, char** argv) {
    pairvec_t pairV1V2;
    for(auto itm = pairV1V2.begin(); itm != pairV1V2.end(); ++itm)
    {
        //Outer values
        auto& outerV1 = itm->first; // NOTE '&' - reference not copy!
        auto& outerV2 = itm->second;
        sort(outerV2.begin(), outerV2.end());
        for(auto itm2 = itm + 1; itm2 != pairV1V2.end(); ++itm2)
        {
            auto& innerV1 = itm2->first;
            auto& innerV2 = itm2->second;
            vec_t setDiffV1;

关于另一种优化方法 - 由于您的列表已经排序 - 可以同时遍历两个列表并比较值。

template<typename ValueType>
void dedupe_vectors(
    typename std::vector<ValueType>& lhs,
    typename std::vector<ValueType>& rhs
    )
{
    auto lit = lhs.begin();
    auto rit = rhs.begin();
    while (rit != rhs.end) {
        while (lit != lhs.end() && *lit < *rit)
            ++lit;
        if (lit == lhs.end())
            break;
        if (*lit == *rit) {
            v2.erase(rit);
            continue;
        }  
        ++rit;
    }
}

我知道 - 我们测试 lit 和 lhs.end 两次。查看使用 -O3 编译器生成的代码，看看它是否能自行检测到这一点。如果是这样，那么你可以开始考虑优化它。

- kfsone

---

或者如果您不关心顺序并且可以进行更改，请考虑使用 std::unordered_set。 - Persixty