18

This code has the Visual Studio error C3892. If I change std::set to std::vector - it works.

std::set<int> a;
a.erase(std::remove_if(a.begin(), a.end(), [](int item)
{
    return item == 10;
}), a.end());

What's wrong? Why can't I use std::remove_if with std::set?

herolover
  • 733
  • 3
  • 9
  • 18
  • possible duplicate of [Erase-remove idiom with std::set failing with constness-related error](http://stackoverflow.com/questions/3792600/erase-remove-idiom-with-stdset-failing-with-constness-related-error) – legends2k Apr 03 '15 at 13:40

3 Answers3

30

You cannot use std::remove_if() with sequences which have const parts. The sequence of std::set<T> elements are made up of T const objects. We actually discussed this question just yesterday at the standard C++ committee and there is some support to create algorithms dealing specifically with the erase()ing objects from containers. It would look something like this (see also N4009):

template <class T, class Comp, class Alloc, class Predicate>
void discard_if(std::set<T, Comp, Alloc>& c, Predicate pred) {
    for (auto it{c.begin()}, end{c.end()}; it != end; ) {
        if (pred(*it)) {
            it = c.erase(it);
        }
        else {
            ++it;
        }
    }
}

(it would probably actually delegate to an algorithm dispatching to the logic above as the same logic is the same for other node-based container).

For you specific use, you can use

a.erase(10);

but this only works if you want to remove a key while the algorithm above works with arbitrary predicates. On the other hand, a.erase(10) can take advantage of std::set<int>'s structure and will be O(log N) while the algorithm is O(N) (with N == s.size()).

compor
  • 2,239
  • 1
  • 19
  • 29
Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
10

Starting with C++20, you can use std::erase_if for containers with an erase() method, just as Kühl explained.

// C++20 example:
std::erase_if(setUserSelection, [](auto& pObject) {
                                     return !pObject->isSelectable();
                                });

Notice that this also includes std::vector, as it has an erase method. No more chaining a.erase(std::remove_if(... :)

Anonymous
  • 4,617
  • 9
  • 48
  • 61
Ben
  • 101
  • 1
  • 3
8

std::remove_if re-orders elements, so it cannot be used with std::set. But you can use std::set::erase:

std::set<int> a;
a.erase(10);
juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • OK, thank you. But. Is it a problem? Let it re-order. Because of the complexity? – herolover Jun 17 '14 at 12:06
  • @herolover `std::set` is ordered, and the ordering is needed for its logarithmic look-up (it is a binary search tree). So it is related to complexity. – juanchopanza Jun 17 '14 at 12:08
  • 1
    @herolover `std::set` elements order is pre-determined by the comparator function, you cannot change the order, the container woudn't work – Erbureth Jun 17 '14 at 12:09