Witam,
Czy znacie efektywne sposoby implementacji operacji na zbiorach (szczególnie interesuje mnie zawieranie zbiorów) w c++?
0
0
efektywność jest względna. zależy do czego się używa, stosuje się inne algorytmy
0
Mam dwa wektory przechowujące obiekty własnej klasy i chodzi mi o sprawdzenie czy jeden zawiera się w drugim. Wpadłam na pomysł umieszczenia wszystkich elementów wektora, w którym ma się zawierać pierwszy wektor w mapie - kluczem był by element wektora, a wartość wynosiła by true. Następnie sprawdzaniu czy kolejne elementy drugiego wektora maja wartość true w mapie. Czy istnieją jakieś efektywniejsze metody?
0
Tak, jest kontener std::set, a jeszcze wydajniejszy był by hash_set
0
Jeżeli koniecznie musisz samemu to implementować to najpierw należy zadać pytanie:
Czy istnieje relacja porządku między elementami tych zbiorów. Tu dużo daje do optymalizacji. Wtedy implementujesz taki zbiór za pomocą jakiegoś drzewa zrównoważonego (np. RBT).
Zawieranie można sprawdzić tak: //A jest nadzbiorem B
Szukasz w A takiego poddrzewo (nazwijmy je A1), którego korzeń jest równy korzeniowi B. //Jeżeli nie ma to B nie zawiera się w A
Teraz sprawdzasz czy lewe poddrzewo B zawiera się w lewym poddrzewie A1 (analogicznie z prawym).
itd...
Jeżeli porządku nie ma to chyba żadnej optymalizacji się tutaj nie wymyśli.