c++ - 如何有效地从 vector c++ 中删除元素

Question

我有一个名为 pairV1V2 的 vector 对 (V1,V2) 的 vector ，形式如下:

(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 中删除相交的元素。我写了下面的代码来做同样的事情。然而，我的代码非常低效，因为我的 vector 对 V1V2 很大并且它在 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;
}

有人能帮我改进我现在的代码——它给出了正确的答案(在这个例子中，我可能为了简洁而错过了一些案例——但代码处理了所有这些)但是速度非常慢(因为对角化)通过性能)。如果在我目前的代码中提出改进建议，我将不胜感激。但是，如果两个代码的逻辑相同，那么新的算法也是可以接受的

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 的范围重载删除从这个开始到 vector 末尾的所有元素。 .

例如，假设我们有 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是稳定的，即它不会改变剩余元素的顺序。