使用索引擦除stl :: vector中的元素

Question

我有一个stl::vector<int>,我需要删除给定索引处的所有元素(向量通常具有高维度).我想知道,考虑到原始矢量的顺序应该保留,这是进行这种操作的最有效方法.

虽然,我在这个问题上发现了相关的帖子,但有些人需要删除一个单元素或多个元素,其中删除 - 删除成语似乎是一个很好的解决方案.但是,在我的情况下,我需要删除多个元素,因为我使用的是索引而不是直接值,remove-erase idiom所以无法应用,对吧？我的代码如下所示,我想知道在效率方面是否可以做得更好？

bool find_element(const vector<int> & vMyVect, int nElem){
    return (std::find(vMyVect.begin(), vMyVect.end(), nElem)!=vMyVect.end()) ? true : false;
}

void remove_elements(){

    srand ( time(NULL) );

    int nSize = 20;
    std::vector<int> vMyValues;
    for(int i = 0; i < nSize; ++i){
            vMyValues.push_back(i);
    }

    int nRandIdx;
    std::vector<int> vMyIndexes;
    for(int i = 0; i < 6; ++i){
        nRandIdx = rand() % nSize;
        vMyIndexes.push_back(nRandIdx);
    }

    std::vector<int> vMyResult;
    for(int i=0; i < (int)vMyValues.size(); i++){
        if(!find_element(vMyIndexes,i)){
            vMyResult.push_back(vMyValues[i]);
        }
    }
}

Answer 1

我认为它可能更有效,如果你只是对索引进行排序,然后从矢量中删除从最高到最低的那些元素.删除列表中的最高索引不会使您要删除的较低索引无效,因为只有高于已删除元素的元素才会更改其索引.

如果它真的更有效将取决于排序的速度.关于这个解决方案的另一个专家是,你不需要你的值向量的副本,你可以直接在原始向量上工作.代码看起来像这样:

... fill up the vectors ...

sort (vMyIndexes.begin(), vMyIndexes.end());

for(int i=vMyIndexes.size() - 1; i >= 0; i--){
    vMyValues.erase(vMyValues.begin() + vMyIndexes[i])
}

Answer 2

为避免多次移动相同的元素,我们可以按删除的索引之间的范围移动它们

// fill vMyIndexes, take care about duplicated values
vMyIndexes.push_back(-1); // to handle range from 0 to the first index to remove
vMyIndexes.push_back(vMyValues.size()); // to handle range from the last index to remove and to the end of values
std::sort(vMyIndexes.begin(), vMyIndexes.end());
std::vector<int>::iterator last = vMyValues.begin();
for (size_t i = 1; i != vMyIndexes.size(); ++i) {
    size_t range_begin = vMyIndexes[i - 1] + 1;
    size_t range_end = vMyIndexes[i];
    std::copy(vMyValues.begin() + range_begin, vMyValues.begin() + range_end,   last);
    last += range_end - range_begin;
}
vMyValues.erase(last, vMyValues.end());

PS修正了一个错误,感谢Steve Jessop耐心地试图向我展示它

Answer 3

在给定索引处擦除删除多个元素

更新：从@kory获得有关性能的反馈后，我修改了算法，不使用标记和大块（不是一对一地）移动/复制元素。

笔记：

• 索引需要排序和唯一
• 用途std::move（用std::copyc ++ 98 替换）：

Github Live example

码：

template <class ForwardIt, class SortUniqIndsFwdIt>
inline ForwardIt remove_at(
    ForwardIt first,
    ForwardIt last,
    SortUniqIndsFwdIt ii_first,
    SortUniqIndsFwdIt ii_last)
{
    if(ii_first == ii_last) // no indices-to-remove are given
        return last;
    typedef typename std::iterator_traits<ForwardIt>::difference_type diff_t;
    typedef typename std::iterator_traits<SortUniqIndsFwdIt>::value_type ind_t;
    ForwardIt destination = first + static_cast<diff_t>(*ii_first);
    while(ii_first != ii_last)
    {
        // advance to an index after a chunk of elements-to-keep
        for(ind_t cur = *ii_first++; ii_first != ii_last; ++ii_first)
        {
            const ind_t nxt = *ii_first;
            if(nxt - cur > 1)
                break;
            cur = nxt;
        }
        // move the chunk of elements-to-keep to new destination
        const ForwardIt source_first =
            first + static_cast<diff_t>(*(ii_first - 1)) + 1;
        const ForwardIt source_last =
            ii_first != ii_last ? first + static_cast<diff_t>(*ii_first) : last;
        std::move(source_first, source_last, destination);
        // std::copy(source_first, source_last, destination) // c++98 version
        destination += source_last - source_first;
    }
    return destination;
}

用法示例：

std::vector<int> v = /*...*/; // vector to remove elements from
std::vector<int> ii = /*...*/; // indices of elements to be removed

// prepare indices
std::sort(ii.begin(), ii.end());
ii.erase(std::unique(ii.begin(), ii.end()), ii.end());

// remove elements at indices
v.erase(remove_at(v.begin(), v.end(), ii.begin(), ii.end()), v.end());