[C++] Usuwanie elementów z mapy o zadanej wartości

Problem nad, którym od dawna się zastanawiałem, a mianowicie jak najlepiej usunąć elementy o zadanej wartości z mapy. Miałem nadzieje na wykorzystanie, jakiegoś wbudowanego w standard mechanizmu/algorytmu, albo chociaż czegoś z biblioteki boost - niestety. Wyniki poszukiwań poniżej.

Na pierwszy ogień poszedł std::remove_if(), niestety problemem jest tu w jaki sposób mapy przechowują swoje elementy. std::map<K,V>::value_type jest parą std::pair<const K, V>. std::remove_if() przesuwa elementy do usunięcia w taki sposób, że zostają one nadpisane. Ponieważ nie można przypisywać do const, std::remove_if() nie nadaje się do zastosowania na mapach. Wykorzystałem go jednak w zwykłej metodzie nib::erase_if() [linia 21], gdyż świetnie nadaje się dla zwykłych kontenerów. Wątek na stackoveflow, który traktuje o tym problemie:

http://stackoverflow.com/questions/9515357/map-lambda-remove-if/9515446#9515446

Z tego co udało mi się wyszukać innym, częstym rozwiązaniem jest skorzystanie z std::remove_copy_if(). Tym razem wszystkie elementy, które nie spełniają naszego kryterium są kopiowane do nowej mapy. Jeżeli mapa jest sporych rozmiarów, a elementów do usunięcia jest stosunkowo dużo, to minusem rozwiązaniem będzie niepotrzebne chwilowe zwiększenie zapotrzebowanie na pamięć. Działanie tego algorytmu zostało zawarte w metodzie nib_test::erase_if() [linia 47].

Ostatnie i najbardziej preferowane rozwiązanie - nib::erase_if [linia 27], to napisanie własnego algorytmu, który podejmie się tego zadania. Szkoda, że nie udało się niczego takiego zaadoptować (albo jeszcze nie znalazłem) w bibliotece standardowej albo w innych popularnych bibliotekach (np. boost).
Po odnalezieniu elementów o zadanej wartości zostaną one usunięty za pomocą metody std::map::erase(). Dobra wiadomość jest taka, że std::map::erase(), unieważnia jedynie referencje i iteratory do usuwanego elementu, pozostałe referencje i iteratory w mapie są nadal ważne:

http://en.cppreference.com/w/cpp/container/map/erase

Dwa wątki traktujące o tym rozwiązaniu:

http://stackoverflow.com/questions/180516/how-to-filter-items-from-a-stdmap/180616#180616

http://stackoverflow.com/questions/263945/what-happens-if-you-call-erase-on-a-map-element-while-iterating-from-begin-to/263958#263958

Jak informuje autor, jednego z rozwiązań, w przypadku skorzystania z zapisu "erase(it++)", standard gwarantuje, że wszystkie wyrażenia argumentów, będą wykonane przed wywołaniem funkcji. Prosta inkrementacja zostanie wykonany przed wywołaniem funkcji std::map::erase(), a do niej zostanie przekazana wartość jeszcze niezainkrementowana.

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

template <typename Key, typename Value>
std::ostream& operator<<(std::ostream& out, const std::pair<Key, Value>& p) {
    return out << "[" << p.first << "]" << "=" << p.second;
}

template <typename Container>
void print_container(const Container& container) {
    for(const auto& v : container)
        std::cout << v << std::endl;
}

namespace nib
{

template <typename Container, typename Predicate>
void erase_if(Container& container, const Predicate& predicate) {
    container.erase(std::remove_if(begin(container), end(container), predicate),
                    end(container));
}

template <typename Key, typename Value, typename Predicate>
void erase_if(std::map<Key, Value>& dict, const Predicate& predicate) {
    auto it = begin(dict);
    while(it != end(dict)) {
        if (predicate(*it)) {
            // Standard zapewnia, ze it++ zostanie obliczone, zanim samo "it"
            // zostanie przekazane do funkcji
            dict.erase(it++);
        }
        else {
            ++it;
        }
    }
}

} // namespace nib

namespace nib_test
{

template <typename Key, typename Value, typename Predicate>
void erase_if(std::map<Key, Value>& dict, const Predicate& predicate) {
    typedef typename std::remove_reference<decltype(dict)>::type Map;
    Map tmp;
    std::remove_copy_if(begin(dict), end(dict),
                        std::inserter(tmp, begin(tmp)),
                        predicate);
    dict = tmp;
}

} // namespace nib_test

int main() {
    std::vector<int> vec { 1, 2, 1, 4, 1, 5 };
    auto val_to_erase = [] (int& v) { return v == 1; };
    nib::erase_if(vec, val_to_erase);
    print_container(vec);

    typedef std::map<int, std::string> Dict;
    Dict dict { {1, "a"}, {2, "b"}, {3, "c"}, {7, "b"} };

    auto val_to_erase_in_map = [] (typename Dict::value_type& v) { return v.second == "b"; };
    nib::erase_if(dict, val_to_erase_in_map);
//  nib_test::erase_if(dict, val_to_erase_in_map);
    print_container(dict);

    return 0;
}

Wyniki:

2
4
5
[1]=a
[3]=c

Aby się upewnić co do kosumpcji pamięci przez oba rozwiązania, przeprowadziłem prostą weryfikacją za pomocą valgrinda.

int main() {
    typedef std::map<int, std::string> Dict;
    Dict dict { {1, "a"}, {2, "b"}, {3, "c"}, {7, "b"} };

    for(int i = 0; i < 10000; ++i)
        dict.insert(std::make_pair(5000 + i, "x"));
//      dict.emplace(5000 + i, "x"); - Nie dziala w GCC 4.7!!!

    auto val_to_erase_in_map = [] (typename Dict::value_type& v) { return v.second == "b"; };
//  nib::erase_if(dict, val_to_erase_in_map);
    nib_test::erase_if(dict, val_to_erase_in_map);
    print_container(dict);

    return 0;
}

Wersja nib::erase_if(), odnotowała peak na poziomie 558272 bajtów, natomiast dla nib_test::erase_if() (korzystająca z std::remove_copy_if()) peak ten wynosił 874376 bajty.