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:
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: Dwa wątki traktujące o tym rozwiązaniu:
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]=cAby 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.
