element unordered_map jest usuwany

Question

Wstawiam obiekt {string, MyStruct} do mapy unordered_map, a następnie iteruję przez unordered_map i wybieram usunięcie elementu. Jednak przed skasowaniem elementu mam assert, który pokazuje, że unordered_map jest pusta.

To moja wkładka:

my_umap.insert(std::make_pair(key.toString(), my_struct)); 

Struct zawiera człon zapis czasu, w którym został wstawiony. I następnie okresowo sprawdzać mapę i usunąć elementy, które zostały w unordered_map zbyt długo:

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){ 

    MyStruct& myStruct = it->second; 
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5)); 

    if(deleteEntry){ 
     const string& key = it->first; // Cannot access memory for 'key' 
     assert(my_umap.size() >= 1);  // This is failing 
     my_umap.erase(key); 
    } 
} 

Używam kod w gdb i assert kończy się niepowodzeniem. Kiedy zapytania wartość od key mówi

nie może uzyskać dostęp do pamięci

podczas kwerendy rozmiaru my_umap mówi wielkość wynosi zero.

W jaki sposób pętla for może wykryć element, jeśli rozmiar nieuporządkowanej_mapy wynosi zero? Nie ma innych wątków uzyskujących dostęp do tego kontenera. Myślałem, że unordered_map::insert() kopiuje obiekt do kontenera, więc oryginalny obiekt, który jest usuwany, nie powinien mieć znaczenia?

Answer 1

Po wywołaniu my_umap.erase(...), Twój iterator staje się nieważny:

cppreference.com mówi:

Odniesienia i iteratory do wymazanych elementów są unieważniane. Inne iteratory i odwołania nie są unieważniane.

Oznacza to, że po usunięciu elementu iteratory, które go wskazywały, nie są już ważne.

Masz kilka opcji:

1. Użyj iterator do skasowania i używać wartości zwracanej erase()

ponieważ C++ 11, kasowanie przez iterator zwróci iterator wskazujący do następnego elementu na mapie.Więc można to wykorzystać, aby zachować swoją ważność iterator:

auto it = my_umap.begin(); 

while (it != my_umap.end()) { 

    MyStruct& myStruct = it->second; 
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5)); 

    if(deleteEntry){ 
     assert(my_umap.size() >= 1); 
     it = my_umap.erase(it); // <-- Return value should be a valid iterator. 
    } 
    else{ 
     ++it; // Have to manually increment. 
    } 
} 

2. przechowywać iteratory w obiekcie listy i usunąć po iteracji.

Alternatywnie, można przechowywać usuwać kandydatów w obiekcie listy (np wektor i usuwać je po początkowej iteracji:

std::vector<MapType::iterator> deleteCandidates; 

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){ 

    MyStruct& myStruct = it->second; 
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5)); 

    if(deleteEntry) 
     deleteCandidates.push_back(it); 
} 

for (auto it : deleteCandidates) { 
    my_umap.erase(it); 
} 

---

Jeśli chodzi o twierdzenie, dlaczego nie udaje, jesteś prawdopodobnie napotkania niezdefiniowany Zachowanie przez uzyskanie dostępu do nieprawidłowego iteratora, powodując, że twoja pętla for jest przekonana, że ​​mapa nadal nie jest pusta (ponieważ: invalidIterator != my_umap.end()) .Tak,

Answer 2

erase() invalides usunięty iterator. Po zwiększeniu tej wartości w pętli for uzyskuje się niezdefiniowane zachowanie. assert() prawdopodobnie uruchamia się podczas drugiej iteracji twojej pętli, a nie twojej pierwszej.

Będziesz musiał zrestrukturyzować swoją pętlę jak:

for(auto it = my_umap.begin(); it != my_umap.end(); /* nothing */){ 

    MyStruct& myStruct = it->second; 
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5)); 

    if(deleteEntry) { 
     // either use the return 
     it = my_umap.erase(it); // NB: erase by it, not by key, why 
           // do an extra lookup?  

     // or post-increment 
     my_umap.erase(it++); 
    } 
    else { 
     ++it; 
    } 
} 

Osobiście wolę it = map.erase(it) do map.erase(it++) ale YMMV.

bym po prostu owinąć że w szablonie funkcji, dzięki czemu nie trzeba zachować przepisanie tego rodzaju rzeczy:

template <class Container, class F> 
void erase_if(Container& c, F&& f) { 
    for (auto it = c.begin(); it != c.end();) { 
     if (f(*it)) { 
      it = c.erase(it); 
     } 
     else { 
      ++it; 
     } 
    } 
} 

, a następnie:

erase_if(my_umap, [](const auto& pr){ 
    MyStruct& myStruct = pr.second; 
    return myStruct.ts.IsElapsed(std::chrono::seconds(5)); 
}); 

Answer 3

Problem polega na tym, że masz problem z iteratorami. w trakcie iteracji wymazujesz bieżący iterator, który powinien był doprowadzić do następnego.

Istnieje kilka sposobów rozwiązania tego problemu. Pierwsza to coś, co właśnie skopiowałem z C++:

int main() 
{ 
    std::map<int, std::string> c = { { 1, "one" }, { 2, "two" }, { 3,  "three" }, 
    { 4, "four" }, { 5, "five" }, { 6, "six" } }; 
    // erase all odd numbers from c 
    for (auto it = c.begin(); it != c.end();) 
     if (it->first % 2 == 1) 
      it = c.erase(it); 
     else 
      ++it; 
    for (auto& p : c) 
     std::cout << p.second << ' '; 

Zwróć uwagę na pętlę. To nie przyspiesza iteratora. Zamiast tego przypisuje iterator do tego, który został zwrócony z wymazanego elementu - erase zwraca następny iterator, lub, nie kasując, przesuwa go jawnie.

Druga opcja, aby przejść wokół tego problemu znajduje się w następującym zmienił zrobiłem pierwszego programu:

int main() 
{ 
    std::map<int, std::string> c = { { 1, "one" }, { 2, "two" }, { 3, "three" }, 
{ 4, "four" }, { 5, "five" }, { 6, "six" } }; 

    // collect all odd numbers from c into a vector 
    vector<int> to_delete; 
    for (auto pair : c) if (pair.first % 2 == 1) to_delete.push_back(pair.first); 

    // now delete them all 
    for (auto k : to_delete) c.erase(k); 

    for (auto& p : c) 
     std::cout << p.second << ' '; 
} 

Tym razem zebrać wszystkie klucze w wektorze, następnie zeskanować wektor i usunąć każdy klawisz z mapy. W ten sposób nie kasujesz mapy podczas iteracji mapy.

Answer 4

W rzeczywistości, erase_if(), który @ barry zasugerował, jest już częścią TS Library Fundamentals V2 (Uniform Container Erasure). Nie mogę teraz znaleźć, jeśli będzie to część C++ 17.

Oto referencyjny: http://en.cppreference.com/w/cpp/experimental/unordered_map/erase_if

Standardowa biblioteka dostarczana z Visual Studio 2015 realizuje go już.

Ze strony statusu libstdc++ (standardowa biblioteka dostarczona z gcc) możemy zobaczyć, że ona również ją implementuje, ale jest tylko w wersji rozwojowej, a nie w żadnej konkretnej wersji. (https://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.201z)

Należy zauważyć, że w przeciwieństwie do większości obecnych algorytmów, te funkcje żyją w nagłówku odpowiedniego kontenera (nie w nagłówku algorytmu) i odwołują się do samego kontenera (zamiast pary iteratorów). Zmiany te wynikają z tego, że funkcje te muszą wiedzieć o kontenerze, aby prawidłowo wykonać pętlę i użyć funkcji członka kontenera erase(). W rezultacie, jeśli chcesz zastosować tę operację wymazywania tylko w określonym zakresie w kontenerze, nadal musisz używać ręcznie pisanej pętli, jak opisano w innych odpowiedziach (może Ranges TS również to poprawia?).