const arguments in std::remove_if

Question

I'm going to remove elements from a list of pairs. When I'm using a pair like

std::pair<const int, bool>

I get the following compilation error:

In file included from /usr/local/include/c++/6.1.0/utility:70:0,

from /usr/local/include/c++/6.1.0/algorithm:60,

from main.cpp:1:

/usr/local/include/c++/6.1.0/bits/stl_pair.h: In instantiation of 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::pair<_T1, _T2>&&) [with _T1 = const int; _T2 = bool]':

/usr/local/include/c++/6.1.0/bits/stl_algo.h:868:16: required from '_ForwardIterator std::__remove_if(_ForwardIterator, _ForwardIterator, _Predicate) [with _ForwardIterator = std::_List_iterator > _Predicate = __gnu_cxx::__ops::_Iter_pred&)> >]'

/usr/local/include/c++/6.1.0/bits/stl_algo.h:936:30: required from '_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_List_iterator > _Predicate = main()::&)>]'

main.cpp:17:32: required from here

/usr/local/include/c++/6.1.0/bits/stl_pair.h:319:8: error: assignment of read-only member 'std::pair::first'

first = std::forward(__p.first);

This is the sample code:

int main()
{
    int id = 2;

    std::list< std::pair <const int, bool> >  l;
    l.push_back(std::make_pair(3,true));
    l.push_back(std::make_pair(2,false));
    l.push_back(std::make_pair(1,true));

    l.erase(std::remove_if(l.begin(), l.end(), 
        [id](std::pair<const int, bool>& e) -> bool {
        return e.first == id; }));

    for (auto i: l) {
        std::cout << i.first << " " << i.second << std::endl;
    }
}

I know that (please correct me If I am wrong):

1. I will have exactly the same problem as long as there is constness in any element of the list, for example, a list <const int> will also return a compilation error.

2. If I remove the const in the first element of the pair the code will work.

3. The more elegant and efficient way to do it is by using the remove_if list method, like this:

   l.remove_if([id](std::pair<const int, bool>& e) -> bool {
       return e.first == id; });
   

but my question is, what are exactly the inner workings of std::remove_if that impose the elements of the container not being const?

Answer 1

The general std::remove_if shuffles item values around to put the logically erased values at the end of the sequence (it's typically used in combination with member function erase to actually remove the logically erased values). It can't do that shuffling when an item isn't copyable or movable. Instead use std::list::remove_if.

Answer 2

If you look at the type and iterator requirements of std::remove_if, you can see that the implementation must be similar to the following (from the link above):

template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if(first, last, p);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!p(*i))
                *first++ = std::move(*i);
    return first;
}

I.e., the algorithm assumes only that the iterators have forward capabilities, and elements are moveable, and it moves elements around. Of course, moves can't be done on const objects.