Erasing elements in stl::vector by using indexes

问题:

I've a stl::vector<int> and I need to remove all elements at given indexes (the vector usually has high dimensionality). I would like to know, which is the most efficient way to do such an operation having in mind that the order of the original vector should be preserved.

Although, I found related posts on this issue, some of them needed to remove one single element or multiple elements where the remove-erase idiom seemed to be a good solution. In my case, however, I need to delete multiple elements and since I'm using indexes instead of direct values, the remove-erase idiom can't be applied, right? My code is given below and I would like to know if it's possible to do better than that in terms of efficiency?

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]);
        }
    }
}

回答1:

I think it could be more efficient, if you just just sort your indices and then delete those elements from your vector from the highest to the lowest. Deleting the highest index on a list will not invalidate the lower indices you want to delete, because only the elements higher than the deleted ones change their index.

If it is really more efficient will depend on how fast the sorting is. One more pro about this solultion is, that you don't need a copy of your value vector, you can work directly on the original vector. code should look something like this:

... fill up the vectors ...

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

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

回答2:

to avoid moving the same elements many times, we can move them by ranges between deleted indexes

// 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());

P.S. fixed a bug, thanks to Steve Jessop that patiently tried to show me it

回答3:

What you can do is split the vector (actually any non-associative container) in two groups, one corresponding to the indices to be erased and one containing the rest.

template<typename Cont, typename It>
auto ToggleIndices(Cont &cont, It beg, It end) -> decltype(std::end(cont))
{
    int helpIndx(0);
    return std::stable_partition(std::begin(cont), std::end(cont), 
        [&](typename Cont::value_type const& val) -> bool {
            return std::find(beg, end, helpIndx++) != end;
    });
}

you can then delete from (or up to) the split point to erase (keep only) the elements corresponding to the indices

std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);

int ar[] = { 2, 0, 4 };
v.erase(ToggleIndices(v, std::begin(ar), std::end(ar)), v.end());

• If the 'keep only by index' operation is not needed you can use remove_if insted of stable_partition (O(n) vs O(nlogn) complexity)
• To work for C arrays as containers the lambda function should be [&](decltype(*(std::begin(cont))) const& val) -> bool { return std::find(beg, end, helpIndx++) != end; } but then the .erase() method is no longer an option

回答4:

If you want to ensure that every element is only moved once, you can simply iterate through each element, copy those that are to remain into a new, second container, do not copy the ones you wish to remove, and then delete the old container and replace it with the new one :)

回答5:

Erase-remove multiple elements at given indices

C++11 version using std::move (see commented-out line for C++98-version):

template <typename ForwardIt, typename SortedIndicesForwardIt>
inline ForwardIt remove_at(
    ForwardIt first,
    ForwardIt last,
    SortedIndicesForwardIt indices_first,
    SortedIndicesForwardIt indices_last)
{
    typedef typename std::vector<bool> flags;
    // flag elements to keep
    flags is_keep(
        static_cast<flags::size_type>(std::distance(first, last)), true);
    for(; indices_first != indices_last; ++indices_first)
        is_keep[static_cast<flags::size_type>(*indices_first)] = false;
    // move kept elements to beginning
    ForwardIt result = first;
    for(flags::const_iterator it = is_keep.begin(); first != last; ++first, ++it)
        if(*it) // keep element
            *result++ = std::move(*first); // *result++ = *first; //<= c++98
    return result;
}

Usage example:

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

std::sort(ii.begin(), ii.end()); // sort indices
vec.erase(remove_at(v.begin(), v.end(), ii.begin(), ii.end()), v.end());
//  ^     ^         
// erase-remove elements at indices

Notes:

• indices need to be sorted
• flags each element (kept or removed) using a temporary vector of bools
• Live example
• Github page: https://github.com/artem-ogre/remove_at