8
\$\begingroup\$

From a sorted vector of indices (toRemove), I would like to remove from another vector (v) the elements at these indices. Note that I need to preserve the order of the remaining elements in v. toRemove can be modified at will however.

An easy way to do it would be to start with the last element of toRemove and remove them sequentially. However, that would require copying elements at the end of the vector several times which is slow when the vector is large.

Here is an alternative using the erase-remove idiom:

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

template <typename INT, typename T> // INT could be int, unsigned int, char, size_t, etc...
void removeIndicesFromVector(std::vector<T>& v, std::vector<INT>& rm )
{
  // For speed, I am assuming that 'rm' is sorted
  size_t rm_index = 0;
  v.erase(
    std::remove_if(std::begin(v), std::end(v), [&](T& elem)
    {
        if (rm.size() != rm_index && &elem - &v[0] == rm[rm_index])
        {
           rm_index++;
           return true;
        }
        return false;
    }),
    std::end(v)
  );
}

template <typename T>
void print(std::vector<T> v)
{
    for (size_t i = 0 ; i < v.size();i++)
    {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<std::string> v = {"Alice", "Smith", "is", "very", "clever", "and", "is", "very", "nice"};
    print(v);
    std::vector<int> toRemove = {1,6};
    removeIndicesFromVector(v,toRemove);
    print(v);

    return 0;
}

The code outputs as expected:

Alice Smith is very clever and is very nice 
Alice is very clever and very nice 

Is there a "better" alternative to my function removeIndicesFromVector?

By "better", I mean faster / better names / cleaner / more standard / one that is as fast but does not assume 'rm' is sorted. If it matters, note that the object that will need to be removed will rarely be any bigger than the std::strings considered here but the vector will be much longer.

\$\endgroup\$
  • 2
    \$\begingroup\$ Just to be clear, do we need to preserve the order of the remaining elements in v? \$\endgroup\$ – user673679 Nov 1 '18 at 11:49
  • \$\begingroup\$ @user673679 I am sorry I missed your comment. Yes, I need to preserve the order of the remaining elements in v. I've now edited this info into the post. \$\endgroup\$ – Remi.b Nov 6 '18 at 18:37
6
\$\begingroup\$

That's a worthwhile problem to solve, and a good solution.

Trivial fix: std::size_t is misspelt in a couple of places.

One easy change I'd make is that rm can be const std::vector<INT>&, since we won't be modifying it. That's helpful, as it allows the reference to bind to an rvalue if we want (test by passing std::move(toRemove)).


It might be worthwhile passing rm as an iterator pair; we can still have an overload that accepts std::vector or other container:

#include <algorithm>
#include <cassert>
#include <vector>

template <typename T, typename Iter>
void removeIndicesFromVector(std::vector<T>& v, Iter begin, Iter end)
    // requires std::is_convertible_v<std::iterator_traits<Iter>::value_type, std::size_t>
{
    assert(std::is_sorted(begin, end));
    auto rm_iter = begin;
    std::size_t current_index = 0;

    const auto pred = [&](const T&){
        // any more to remove?
        if (rm_iter == end) { return false; }
        // is this one specified?
        if (*rm_iter == current_index++) { return ++rm_iter, true; }
        return false;
    };

    v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
}

template <typename T, typename S>
    // requires std::is_convertible_v<S::value_type, std::size_t>
void removeIndicesFromVector(std::vector<T>& v, const S& rm)
{
    using std::begin;
    using std::end;
    assert(std::is_sorted(begin(rm), end(rm)));
    return removeIndicesFromVector(v, begin(rm), end(rm));
}

I've changed the algorithm here to simply count the elements seen, which must be valid because std::remove_if() accepts input iterators and is specified to invoke the predicate exactly std::distance(first, last) times.

The requires lines are commented out, as I didn't manage to get them working as I'd like - I'd appreciate a comment or edit to fix that.


If we feel generous, we might be willing to accept non-sorted input (with a speed penalty, of course):

#include <algorithm>
#include <vector>

template <typename T, typename Iter>
void removeIndicesFromVector(std::vector<T>& v, Iter begin, Iter end)
    // requires std::is_convertible_v<std::iterator_traits<Iter>::value_type, std::size_t>
{
    std::size_t current_index = 0;

    if (std::is_sorted(begin, end)) {

        // sorted version - advance through begin..end
        auto rm_iter = begin;
        const auto pred = [&](const T&) {
            // any more to remove?
            if (rm_iter != end && *rm_iter == current_index++) {
                return ++rm_iter, true;
            }
            return false;
        };
        v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

    } else {

        // unsorted version - search for each index in begin..end
        const auto pred = [&](const T&) {
            return std::find(begin, end, current_index++) != end;
        };
        v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
    }
}

template <typename T, typename S>
    // requires std::is_convertible_v<S::value_type, std::size_t>
void removeIndicesFromVector(std::vector<T>& v, const S& rm)
{
    using std::begin;
    using std::end;
    return removeIndicesFromVector(v, begin(rm), end(rm));
}

Test of unordered remove:

#include <array>
#include <iostream>
#include <string>

template <typename T>
void print(const std::vector<T>& v)
{
    for (auto const& e: v) {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector v{"Alice", "Smith", "is", "very", "clever",
                  "and", "is", "very", "nice"};
    print(v);
    removeIndicesFromVector(v, std::array{6u,1u});
    print(v);

    return 0;
}
\$\endgroup\$
6
\$\begingroup\$

We can do a bit better than remove_if. Since we already know which values need to be removed, there's no need to apply a predicate to every element.

To remove an element and preserve the order, we have to move all the elements beyond it to the left. The start of the range to be moved is one past the element to be removed. The end of the range is the next element to be removed. We repeat this until there are no more elements to be removed, at which point the end of the range becomes the end of the original vector. We do one final move, and return the end of the valid range.

#include <vector>
#include <algorithm>

template<class ForwardIt, class ForwardIndexIt>
ForwardIt remove_if_at_indices(ForwardIt first, ForwardIt last, ForwardIndexIt i_first, ForwardIndexIt i_last)
{
    if (first == last)
        return first;

    if (i_first == i_last)
        return last;

    auto dest = std::next(first, *i_first++);
    auto start = std::next(dest);

    while (i_first != i_last)
    {
        auto const end = std::next(first, *i_first++);
        dest = std::move(start, end, dest);
        start = std::next(end);
    }

    dest = std::move(start, last, dest);

    return dest;
}

template <typename T>
void remove_elements_at(std::vector<T>& v, std::vector<std::size_t> const& rm)
{
    v.erase(
        remove_if_at_indices(v.begin(), v.end(), rm.begin(), rm.end()), 
        v.end());
}

This seems to work out slightly faster than std::remove_if.

Testing / benchmarking code:

#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <cassert>

void test(bool condition, std::string const& message)
{
    if (!condition)
        std::cout << "FAIL: " << message << std::endl;
    else
        std::cout << "pass" << std::endl;
}

template <typename T>
void print(std::vector<T> const& v)
{
    for (size_t i = 0; i < v.size();i++)
    {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

int main()
{
    {
        std::vector<std::string> v = { "Alice", "Smith", "is", "very", "clever", "and", "is", "very", "nice" };
        print(v);
        std::vector<std::size_t> toRemove = { 1, 6 };
        remove_elements_at(v, toRemove);
        print(v);
    }

    {
        auto v = std::vector<int>{ };
        auto i = std::vector<std::size_t>{ };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin(), "empty vector and indices");
    }

    {
        auto v = std::vector<int>{ 0, 1, 2, };
        auto i = std::vector<std::size_t>{ };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin(), "empty indices");
    }

    {
        auto v = std::vector<int>{ 0, 1, 2, };
        auto i = std::vector<std::size_t>{ 0 };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin() + 2u, "remove front");
    }

    {
        auto v = std::vector<int>{ 0, 1, 2, };
        auto i = std::vector<std::size_t>{ 2 };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin() + 2u, "remove back");
    }

    {
        auto v = std::vector<int>{ 0, };
        auto i = std::vector<std::size_t>{ 0 };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin(), "remove only");
    }

    {
        auto v = std::vector<int>{ 0, 1, 2, 4 };
        auto i = std::vector<std::size_t>{ 1, 2 };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin() + 2u, "remove adjacent");
    }

    {
        auto v = std::vector<int>{ 0, 1, 2 };
        auto i = std::vector<std::size_t>{ 0, 1, 2 };
        test(remove_if_at_indices(v.begin(), v.end(), i.begin(), i.end()) == v.begin(), "remove all");
    }

    {
        auto v_size = std::size_t{ 10000 };
        auto i_size = std::size_t{ 2000 };
        assert(i_size <= v_size);

        auto v = std::vector<std::size_t>(v_size);
        std::iota(v.begin(), v.end(), std::size_t{ 0 });

        auto rng = std::mt19937_64();
        auto i = v;
        std::shuffle(i.begin(), i.end(), rng); // c++17 could use std::sample instead
        i.resize(i_size);
        std::sort(i.begin(), i.end());

        auto start = std::chrono::high_resolution_clock::now();

        remove_elements_at(v, i);

        auto end = std::chrono::high_resolution_clock::now();
        auto time = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);

        std::cout << i_size << " elements removed in " << time.count() << "ns" << std::endl;
    }

    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I would suggest that this be used only for contiguous and random access containers only. For forward and bidirectional containers, you'll want to track the index count to avoid excessive and unnecessary traversing. \$\endgroup\$ – Snowhawk Nov 1 '18 at 22:43
2
\$\begingroup\$

And what about this version, maybe a bit slower but so much cleaner

template <typename INT, typename T>
void removeIndicesFromVector(std::vector<T>& v, std::vector<INT>& rm )
{
    std::for_each(rm.crbegin(), rm.crend(), [&v](auto index) { v.erase(begin(v) + index); });
}

Plus surely (for this implementation and the others above), replace sur 2nd vector (with indices) by a std::set<std::size_t> or a std::unordered_set<std::size_t> because we don't want to try removing multiple time same index.

\$\endgroup\$
  • \$\begingroup\$ Could you be clearer about when this is an improvement, and why? Since the question explicitly states that, "An easy way to do it would be to start with the last element of toRemove and remove them sequentially", and discounts that as too inefficient, I think it's safe to say that this suggestion doesn't contribute very much at all. (The second part of the answer, ensuring that the list contains no duplicates, is more valuable; checking using std::is_sorted() is insufficient without also calling std::adjacent_find()). \$\endgroup\$ – Toby Speight Nov 5 '18 at 21:53
  • \$\begingroup\$ @TobySpeight It's a improvement, not in term of speed (as pointed out before my code) but in term of readability. But you intrigued me, so I benchmarked. While my way is more readable, with gcc-8.2 it's a lot slower (2.3x slower than your version and 2.7x slower than remi version). But, with clang-6.0, my version become 1.3x faster than remi version and 1.4 than your. Finally, not so bad, for a "slower but more fluent" implementation, eh! (check quick-bench) \$\endgroup\$ – Calak Nov 5 '18 at 23:03
  • \$\begingroup\$ @TobySpeight I added your second try (the unordered version) which is faster than your first on gcc and equivalent on clang. check updated benchmark \$\endgroup\$ – Calak Nov 5 '18 at 23:16
  • \$\begingroup\$ Thanks for the extra information; the question does mention larger vectors (though it is a bit vague - a "large" vector means different things to different people). Things certainly change when we remove 30% from 100000 entries, even when those entries are simply pointers. \$\endgroup\$ – Toby Speight Nov 6 '18 at 9:21
  • 1
    \$\begingroup\$ Agreed - there's rarely one-size-fits-all in software! \$\endgroup\$ – Toby Speight Nov 6 '18 at 10:11
2
\$\begingroup\$

Your implementation would be actually nearly optimal if it wasn't for a std::remove_if limitation: you can't break out of the loop even when you know for certain that the exclusion condition won't be fulfilled again. If performance is critical, you can re-write the algorithm from scratch and bake the optimization into it:

template <typename Iter, typename Index_iter>
Iter removeIndices(Iter first, Iter last, Index_iter ifirst, Index_iter ilast)
{
  if (ifirst == ilast) return last;
  auto count = *ifirst++;
  first = std::next(first, count); // no need to go through every element before
  std::size_t offset = 1;
  if (first == last) return last;
  while (std::next(first, offset) != last) {
    if (++count == *ifirst) {
      ++offset;
      if (++ifirst == ilast) break; // no need to go through every element after
    }
    *first = std::move(*std::next(first, offset));
    ++first;
  }
  return std::move(std::next(first, offset), last, first);
}

There is a non-negligible performance gain, as you can see here.

Edit: Here's another version with two improvements on the first one: std::move is applied on ranges directly defined by the indices, and contiguous indices don't trigger two range-moves:

template <typename Iter, typename Index_iter>
Iter removeIndicesStendhal(Iter first, Iter last, Index_iter ifirst, Index_iter ilast)
{
    if (ifirst == ilast || first == last) return last;

    auto out = std::next(first, *ifirst);
    auto in  = std::next(out);
    while (++ifirst != ilast) {
        if (*std::prev(ifirst) + 1 == *ifirst) {
            ++in; continue;
        }
        out = std::move(in, std::next(first, *ifirst), out);
        in  = std::next(first, *ifirst + 1);
    }
    return std::move(in, last, out);
}

The performance gain is still higher

\$\endgroup\$
  • \$\begingroup\$ Nice code, I would suggest a while rather than the if continue, as that is more expressive of the intend \$\endgroup\$ – miscco Nov 6 '18 at 20:46
1
\$\begingroup\$

Your code is well written, there are some things that i would like to point out.

  1. You should pass both ranges via iterators, so that it works on other random-access containers like std::array

  2. That way the missing const for indices would not hurt too much

  3. This is a personal preference, but I would almost always put define the lambda separately. In the end one of the major advantages that lambdas have are descriptive names. In the end it is a single line longer but much more readable.

  4. I think the algorithm itself is sub-optimal @papagada wrote an excellent version so i wont comment on it further

\$\endgroup\$
0
\$\begingroup\$

I think you can do away with removing and adjusting the vector for each element. Using a simple swap algorithm you can move the elements you don't want to the bottom of the vector and simply resize the vector to throw them away:

typedef std::vector<int>::iterator  iter;
template <typename INT, typename T> // INT could be int, unsigned int, char, size_t, etc...
void removeIndicesFromVector(std::vector<T>& v, std::vector<INT>& rm)
{
    if (!std::is_sorted(rm.begin(),rm.end()))
    {
        std::sort(rm.begin(), rm.end());
    }
    auto rmFirst = rm.front();
    auto rmLast = rm.back();
    //Check if the elements are in contiguous indices
    if ((rmLast - rmFirst + 1) == rm.size())
    {
        //If they are at the bottom already, resize.
        if (rmLast == v.size() - 1)
        {
            v.resize(rmFirst);
            return;
        }
        //Otherwise swap the range you want to keep in front of the range you don't want and resize.
        iter vBegin = v.begin();
        iter newEnd = std::swap_ranges(vBegin + (rmLast + 1), v.end(), vBegin + rmFirst);
        v.resize(newEnd - vBegin);
        return;
    }
    int swapIndex = rm[0];
    int rmIndex = 0;
    int limit = v.size();
    for (int i = rm[rmIndex]; i < limit; ++i)
    {
        if (i != rm[rmIndex])
        {
            std::swap<T>(v[i], v[swapIndex++]);
        }
                else
                {
                    ++rmIndex;
                }

    }
        v.resize(swapIndex);
}
\$\endgroup\$
  • \$\begingroup\$ I thought that's what erase-remove does internally \$\endgroup\$ – bruglesco Nov 3 '18 at 14:25
  • \$\begingroup\$ @bruglesco - Actually according to cppreference.com, there's one erase for each element being erased and one assignment for each element that's out of position. \$\endgroup\$ – tinstaafl Nov 3 '18 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.