jsxrdq
Last Updated: April 07, 2017
·
4.157K
· picanumber

C++ Erase elements from containers by indices

The problem


You have a C++ container (built in array, vector, list ... all but associative ones) and you want to remove some elements from it. OK so far, only the elemets to remove are reffered to by index . How can this be done ?
</p>

A solution


A quite elegant solution can be devised that generalizes not only upon the type of container to be handled but also upon the type of container that holds the indices to be removed, as show below.
</p>

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), 
        [&](decltype(*std::begin(cont)) const& val) -> bool {
            return std::find(beg, end, helpIndx++) == end;
        });
}

Example

</p>


from v erase all indices contained in ar
</p>

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

Discussion


1. Ofcourse algorithm has to be included.
</p>


2. stable partition was chosen to preserve relative order in the remaining elements. The faster std::partition can be used as well if order is of no concern. If we are not bothered to use the function to 'keep only' the indexed elements, then std::removeif can be used instead of std::stablepartition ( O(n) vs O(nlong(n))
</p>


3. If "ar" was holding the indices to be kept we could use our function as : v.erase(v.begin(), ToggleIndices(v, std::begin(ar), std::end(ar)));
</p>


4. A function object can be used instead of the lambda
</p>