Sprawdź, czy mapa w C++ zawiera wszystkie klucze z innej mapy

Question

Mam zamiar użyć dwóch map w C++, typu: std::map<char, Node>, gdzie Node jest klasą niestandardową. Załóżmy, że mam dwie mapy: m1 i m2 powyższego typu, chcę się dowiedzieć, czyzawiera wszystkie klucze obecne w m2. Innymi słowy, chcę sprawdzić, czy przecięcie zestawu kluczy o numerach m1 i m2 jest takie samo jak zestawu kluczy o numerze m2.

mogę iteracyjne nad wszystkie klucze w m2 i zrobić find() lub count() na m1, ale to wydaje się jak odpad i będzie prawdopodobnie powolny. Mówię to, ponieważ klucze są przechowywane jako drzewo wyszukiwania binarnego w porządku posortowanym w std::map, a więc każde z wyszukiwań/zliczeń zajmuje O (logn), a dla następnego klucza w m2, ta sama ścieżka w kluczach m1 będzie musiał przejść od samego początku.

Jestem nowy w STL, więc proszę wybaczyć moją niewiedzę na temat tego, co wydaje się czymś, co powinno być łatwe do wykonania. Ponadto niektóre proste przykładowe fragmenty kodu lub odsyłacze do fragmentów kodu będą bardzo pomocne w lepszym zrozumieniu. Nie mogę używać niestandardowych bibliotek, w tym doładowania.

Z góry dziękuję!

Answer 1

Ponieważ klucze są sortowane według map, można wykonywać iteracje za ich pośrednictwem w tym samym czasie i porównywać ze sobą klucze. Jeśli key(m1) < key(m2), inkrementuj iterator dla m1; jeśli key(m2) < key(m1) to m2 zawiera klucz spoza m1.

To jest O (n).