Należy użyć std :: set lub std :: unordered_set dla zestawu wskaźników?

Mam zestaw wskaźników. W pierwszym kroku wstawiam wskaźniki danych, aw drugim kroku powtarzam cały zestaw i robię coś z elementami. Kolejność nie jest ważna, po prostu muszę unikać duplikatów, co działa dobrze z porównaniem wskaźnika.Należy użyć std :: set lub std :: unordered_set dla zestawu wskaźników?

Moje pytanie brzmi, czy może być korzystne użycie zestawu nieuporządkowanego do tego samego celu. Czy wstawianie jest szybsze w przypadku nieuporządkowanego zestawu?

Źródło

2016-02-19 Fabian

"Kolejność nie jest ważna" - gdy już zdecydujesz, użyj 'unordered_set'. Jedynym obciążeniem zamówionych kontenerów jest .. zamówienie. –

Ile elementów mówimy? Czy wykonujesz intensywne obliczenia na każdym przedmiocie, czy raczej przypomina to podsumowanie/pomnożenie wszystkich elementów? – MikeMB

Ulepszone pojemniki mają jeszcze jedną ważną zaletę, ponieważ mogą zagwarantować, że czas dla każdej operacji to O (lg n), podczas gdy nieuporządkowane wymagają O (n) w najgorszym przypadku. Więc jeśli chcesz obiecać współudział, użyj std :: set. – James

Jak skomentował Ami Tavory, jeśli nie potrzebujesz zamówienia, zazwyczaj najlepiej jest wybierać nieuporządkowane pojemniki. Powodem jest to, że jeśli porządek w jakiś sposób poprawi wydajność, nieuporządkowane pojemniki będą nadal mogły z niego korzystać, a więc i tak uzyskać taką samą lub lepszą złożoność.

Wadą nieuporządkowanych kolekcji jest to, że zazwyczaj wymagają funkcji skrótu dla typu klucza. Jeśli jest to zbyt trudne lub kosztowne, to pojemniki, które nie używają skrótów, mogą być lepsze.

W standardowej biblioteki C++ jest średnia wstawiania złożoność dla std::set jest O (log (n)), podczas gdy dla std::unordered_set to O (1). Poza tym, prawdopodobnie występuje mniejszy brak pamięci podręcznej średnio podczas korzystania z std::unordered_set.

Pod koniec dnia jest to tylko teoria. Powinieneś spróbować czegoś, co brzmi wystarczająco dobrze i profilować go, aby zobaczyć, czy tak naprawdę jest.

Źródło

2016-02-19 12:32:36

W przypadku wskaźników, o które jest pytanie, w bibliotece standardowej istnieje specjalizacja '' std :: hash'', więc nie ma się czym martwić. –

Inną kwestią do rozważenia jest to, że zachowanie porównania niepowiązanych wskaźników (nie wskazując na tę samą tablicę lub do tego samego obiektu) jest niezdefiniowane. Tak więc, ściśle rzecz biorąc, nie jest bezpiecznie przechowywać wskaźniki w 'std :: set' –

Ponieważ wspomniałeś o złożoności: najgorszy przypadek wyszukiwania nie jest istotny dla pierwotnego pytania, ale O (N) dla unordered_set może być powodem do wyboru zamiast tego zamówić zestaw. Innym argumentem * za * domyślnie nieuporządkowane jest wyrażenie zamiaru: czytelnik widzi, że nie dbasz o porządek. – peterchen

Należy użyć std :: set lub std :: unordered_set dla zestawu wskaźników?

Odpowiedz

Powiązane problemy