erase-remove idiom: did I just delete something?

Question

I am using the erase-remove idiom:

template <typename T>
bool garbageCollectVector(std::vector<T>& v) {
    // Use the erase-remove idiom in combination with a lambda expression
    v.erase(
        std::remove_if(v.begin(), v.end(),
            [this](const T& elem) -> bool {
                return this->shouldRemove(elem);
            }
        ),
        v.end());
    return /* what to return? */;
}

and want to return whether the method actually removed any element or not. What is the cleanest way to do that?

Answer 1

Alternatively to the size check, you may split your implementation:

template <typename T>
bool garbageCollectVector(std::vector<T>& v) {
    // Use the erase-remove idiom in combination with a lambda expression
    auto it = std::remove_if(v.begin(), v.end(),
                             [this](const T& elem) -> bool {
                                return this->shouldRemove(elem);
                             });
    if (it == v.end()) {
        return false;
    } else {
        v.erase(it, v.end());
        return true;
    }
}

Answer 2

How about:

template <typename T>
bool garbageCollectVector(std::vector<T>& v) {
    auto prevSize = v.size();
    // Use the erase-remove idiom in combination with a lambda expression
    v.erase(
        std::remove_if(v.begin(), v.end(),
            [this](const T& elem) -> bool {
                return this->shouldRemove(elem);
            }
        ),
        v.end());
    return !(prevSize == v.size());
}

Answer 3

template<class C, class F>
bool erase_remove_if(C&c,F&&f){
  using std::begin; using std::end;
  auto it=std::remove_if(begin(c),end(c),std::forward<F>(f));
  if (it==end(c)) return false;
  c.erase(it, end(c));
  return true;
}

this puts the idiom into a function.

template <typename T>
bool garbageCollectVector(std::vector<T>& v) {
  // Use the erase-remove idiom in combination with a lambda expression
  return erase_remove_if(v,
    [this](const T& elem) -> bool {
      return this->shouldRemove(elem);
    }
  );
}

which keeps per-line complexity sane.

You can tweak which (a tracking bool or iterator check) is faster and change the erase_remove_if everywhere if you discover a performance impact.

Answer 4

Others have suggested better alternatives, but let me add this for completeness. It uses a flag to check whether the predicate ever returned true.

template <typename T>
bool garbageCollectVector(std::vector<T>& v) {
    // Use the erase-remove idiom in combination with a lambda expression
    bool removed = false;
    v.erase(
        std::remove_if(v.begin(), v.end(),
            [this,&removed](const T& elem) -> bool {
                bool to_remove = this->shouldRemove(elem);
                removed = removed || to_remove;
                return to_remove;
            }
        ),
        v.end());
    return removed;
}

Answer 5

I'd just check the size of the vector. Something like:

auto size_before = v.size();
// v.erase( ... )
return v.size() != size_before;