erase_if

Условное удаление по значению из всяких там map и иже с ними. А так же, бонусом, наиболее оптимальный вариант условного удаления для вектора.

/// [1]
template<typename Container, typename Predicate>
inline size_t erase_if(Container &c, typename Container::iterator b, typename Container::iterator e, Predicate p) 
{
    size_t erased = 0;
    for (auto it = b; it != e;) 
    {
        if (p(*it))
        {
            c.erase(it++);
            ++erased;
        }
        else
            ++it;
    }
    return erased;
}

/// [2]
template<typename Container, typename Predicate>
inline size_t erase_if(Container &c, Predicate p) 
{
    return erase_if(c,  std::begin(c), std::end(c), p);
}

Первая форма - для диапазона, вторая форма - для всего контейнера (имхо, наиболее частый случай).

Использовать:

std::map<int, int> m = {
  {1, 100},
  {2, 200},
  {3, 300}
};

/// [1] форма
erase_if(m, std::begin(m), std::end(m), [](const std::pair<int,int> &p){
  return (p.second == 200);
});

/// [2] форма
erase_if(m, [](const std::pair<int,int> &p){
  return (p.first == 1); // так тоже можно, только зачем? :)
});

Для C++98/2003 адаптируется в два хода: первая форма без изменений, вторая - заменить std::begin()/end() на соответствующие методы контейнера.

Дополнительно можно переопределить для std::list, что бы звался его remove_if.

erase_if для вектора

Идея взята отсюда: http://misc-sonofagun.blogspot.ru/2012/12/blog-post_25.html. Скопирую только информацию о сложности:

Алгоритмическая сложность: N сравнений + N перестановок в случае, если std::stable_partition сможет использовать внутренний буффер или N log N перестановок в противном случае.

/// [3]
template<typename T, typename Predicate>
inline size_t erase_if(std::vector<T> &c, typename std::vector<T>::iterator b, typename std::vector<T>::iterator e, Predicate p) {
    size_t erased = 0;
    
    auto remove_begin = std::stable_partition(b, e, [&](const T& v){
        return !p(v);
    });
    erased = std::distance(remove_begin, e);
    c.erase(remove_begin, e);
    
    return erased;
}

/// [4]
template<typename T, typename Predicate>
inline size_t erase_if(std::vector<T> &c, Predicate p) {
    return erase_if(c, c.begin(), c.end(), p);
}

Отмечу, что наиболее эффективная версия будет [4] либо версия [3], когда конец диапазона равен std::end( c ), иначе все действия будут происходить внутри этого диапазона и значения от e до std::end( c ) придётся сдвигать (т.е. копировать).

Так же этот алгоритм нужно применять для дека (std::deque).

Hatred's Log Place

DON'T PANIC!

erase_if

erase_if для вектора