Удаление указателей из контейнера и их уничтожение

Предположим что ваш последовательный контейнер хранит указатели и вам нужно удалить и уничтожить обьекты удовлетворяющие некоторому критерию. Если указатели не являются умными, то идиому remove + erase использовать не получится поскольку обьекты будут только удалены, но не будут уничтожены. Удаление поштучно является неплохой идеей для std::list, но это будет накладно для std::vector и std::deque, поскольку контейнеру придется многократно перемещать оставшиеся элементы так, чтоб на месте удаленный элементов не оставалось дыр, т.е. в совокупности понадобится O( N² ) перемещений.
Ниже описано решение проблемы с использованием std::stable_partition в паре с erase. Идея в том, чтобы сначала переместить всех кандидатов на удаление в конец коллекции (оптимизация под вектор), а затем вызвать erase для всех их.
Алгоритмическая сложность: N сравнений + N перестановок в случае, если std::stable_partition сможет использовать внутренний буффер или N log N перестановок в противном случае.
Сначала обьявим функтор для уничтожения элементов в контейнере

template< class TPointer >
struct DeletePointer
{

void operator () ( TPointer item ) { delete item; }

};

Затем переходим к определению самой функции, удаляющей и уничтожающей элементы контейнера

template< class Collection, class Predicate >
void delete_erase_if( Collection& c, Predicate pred ) {

typename Collection::iterator removeBegin = std::stable_partition( c.begin(), c.end(), std::not1 ( pred ) );
std::for_each( removeBegin, c.end(), DeletePointer< typename Collection::value_type > () );
c.erase( removeBegin, c.end() );

}

Поскольку stable_partition переставлят все элементы, удовлетворяющие предекату, в начало, а нам нужно переставлять их в конец, то нам приходится как-то инвертировать предикат. Для этого в теле функции используется std::not1 из модуля <functional>.
Если ваш модуль подключает библиотеку QtCore то вы можете избавиться от функтора DeletePointer заменив вторую строчку в теле delete_erase_if на вызов qDeleteAll.
К минусам приведенной выше реализации относится то, что функция не принимает указатели на функции в качестве предиката. Для того, чтобы обойти данное ограничение, нужно просто обернуть указатель на функцию-предикат в std::ptr_fun.