Kiedy należy zastosować wektor / listę?

17

Rozumiem, kiedy używać list, ale nie rozumiem, kiedy lepiej jest używać wektorów niż list w grach wideo: kiedy lepiej mieć szybki losowy dostęp?

(I rozumiem, dlaczego szybciej wstawiać / usuwać listy, ponieważ po prostu usuwa / dodaje wskaźniki, ale wciąż musi znaleźć odpowiedni element ...)

c++ algorithm data-structure żart
źródło
Ponownie dodano do tego znacznik wektorowy - jeśli lista jest poprawnym znacznikiem, to wektor też.
Kylotan,
Prawdopodobnie wektor został usunięty, ponieważ oznacza matematyczny wektor, a nie std :: vector.
1
co powiesz na nix oba i włóż container.
deft_code
@Kylotan: Tak jak powiedział Joe. To pytanie zdecydowanie dotyczyło wektorów, ale nie należało do znacznika wektorowego.
doppelgreener
1
Czy więc usuwamy niejednoznaczny tag? Dla mnie to brzmi jak zła decyzja - lepiej, żeby twoje wyszukiwanie zawierało za dużo informacji, niż za mało. Pomijanie niepożądanych wyników jest łatwiejsze niż burza mózgów, aby znaleźć synonimy.
Kylotan

Odpowiedzi:

29

Moją ogólną zasadą i jestem pewien, że będzie debata na ten temat, to nigdy nie używać list (chyba że trzeba bardzo, bardzo często usuwać rzeczy ze środkowej części dużych list).

Szybkość, którą zyskasz dzięki przechowywaniu wszystkich elementów w kontenerze w ciągłej pamięci (a zatem bardziej przyjaznej dla pamięci podręcznej), jest warta zrównoważenia dodatkowych kosztów dodawania / usuwania / zmiany rozmiaru wektora.

Edycja: Aby wyjaśnić nieco więcej, oczywiście powinno być oczywiste, że każde pytanie „które jest szybsze” powinno być testowane na dowolnej platformie z dowolnymi zestawami danych odpowiadającymi konkretnym potrzebom. Jeśli potrzebuję tylko zbioru elementów, używam po prostu wektora (lub deque, co jest prawie to samo), chyba że istnieje dobry powód, aby tego nie robić .

Tetrad
źródło
1
Myślę, że to w dużej mierze zależy od twoich potrzeb, jeśli nigdy nie musisz uzyskiwać dostępu do określonego elementu i po prostu musisz przeczytać je wszystkie oraz często dodajesz i usuwasz elementy, lista jest lepszym rozwiązaniem.
Frédérick Imbeault
11
@ Frédérick: To standardowa mądrość C ++, ale prawie zawsze jest błędna. Wektory, szczególnie gdy mamy do czynienia z wektorami wskaźników (którymi prawie zawsze jesteś w grach), są niezwykle szybkie, aby usunąć rzeczy ze środka - jest to czas liniowy, ale jest to bardzo niewielki narzut na element. To również znacznie szybciej iteracyjne sekwencyjnie w wektorze.
1
Nie jestem pewien, do jakiej struktury dokładnie się dąży - tego rodzaju optymalizacja wymaga konkretnych przykładów, aby powiedzieć coś definitywnie. Na przykład moją pierwszą reakcją na twój przypadek użycia byłby nieuporządkowany zestaw, który umożliwia równie szybkie wstawianie, usuwanie i wyszukiwanie; z mojego doświadczenia, zestawy są świetne dla obiektów w edytorach. Ponieważ jednak redaktorzy mają dużo mniej rygorystycznych wymagań dotyczących wydajności w czasie rzeczywistym - np. Jest w porządku, jeśli odpowiedź na naciśnięcie przycisku „Usuń” zajmuje 1/20 sekundy lub 1/2 sekundy 10% czasu - ten poziom optymalizacji również rzadko ich dotyczy.
1
@ Frédérick Imbeault Modified nie stanowi większego problemu, to problem powoduje dodanie \ usunięcie. Z punktu dodawania \ usunięty punkt na koniec wektora jest kopiowany, aby wektor był ciągły. Jeśli kolejność elementów nie ma znaczenia, możesz zamienić usunięty element na ostatni element, a następnie wstaw go w celu usunięcia i dodaj na końcu w celu dodania.
stonemetal
4
Na pewno pobranie adresu elementu w wektorze i przechowywanie go nie jest bezpieczne. Ale ogólnie rzecz biorąc, prawie nigdy tego nie robisz, zamiast tego wolisz mieć wektor wskaźników elementów i kopiujesz wskaźnik (lub coś podobnego).
Tetrad
8

Użyj listy, gdy unieważnienie iteratora spowodowane modyfikacją środka struktury danych spowoduje problem lub musisz posortować swoje elementy, aby sztuczka swap i pop dla szybkiego usuwania środkowego zbioru nie działała i masz dużą liczba usuniętych środkowych kolekcji.

Możesz także rozważyć użycie Deque. Ma podobną charakterystykę wydajności do wektora, ale nie potrzebuje wektora ciągłej pamięci i jest nieco bardziej elastyczny.

kamieniste
źródło
+1 za bycie jedyną osobą, która wspomniała o deques - zyskujesz ciągłą pamięć i szybkość wyszukiwania wektorów, z szybkim wstawianiem / usuwaniem na obu końcach.
5

Twój wybór powinien odzwierciedlać twoje potrzeby. Wszystkie elementy wektorów mają ciągłą pamięć, a listy mają wskaźniki do następnych / poprzednich elementów, więc każdy ma swoje zalety / wady:

Listy:

  • Każdy element wymaga 2 liczb całkowitych, aby wskazać poprzedni i następny element, więc najczęściej jest to 8 bajtów więcej na każdy element na liście
  • Wstaw jest liniowy w czasie: O (n)
  • Usuń to ciągła operacja: O (1)
  • Dostęp do elementu x jest liniowy w czasie: O (n)

Wektory:

  • Wymaga mniej pamięci (bez wskaźników do innych elementów, to prosty algorytm matematyczny)
  • Usuwanie jest liniowe w czasie: O (n)
  • Dostęp do elementu x jest stały: O (1) (To dlatego, że elementy są ciągłe w pamięci, więc jest to prosty wektor operacji matematycznychPtr + (x * bytesOfTheType))
  • Wstawianie może odbywać się w czasie liniowym, ale najczęściej jest to stała operacja: O (1) (To dlatego, że wektor w tablicy, ale zawsze rezerwuje 2 razy większą pojemność, gdy tablica jest pełna, więc kopiowanie tablicy nie jest częste)

Lista jest więc lepsza, gdy program wymaga częstego dodawania i usuwania elementów, ale nigdy nie uzyskuje dostępu (lub rzadko dostępu) do określonego elementu bez potrzeby wcześniejszych. Wektor powinien być używany dla lepszego czasu dostępu, ale brakuje mu skuteczności, gdy trzeba usunąć lub dodać elementy.

Sprawdź ten post na stackoverflow, to przedstawia naprawdę ładny wykres z podstawowymi pytaniami o twoich potrzebach, który prowadzi cię do konkretnego kontenera w zależności od twoich odpowiedzi:

/programming/366432/extending-stdlist

Frédérick Imbeault
źródło
3
Ten wykres naprawdę musi zaczynać się od węzła „Czy przechowujesz wskaźniki i mniej niż tysiąc? Nie -> wektor”.
Tak, może masz rację, nie uważałem, że przechowywany typ powinien również zostać przeanalizowany.
Frédérick Imbeault
2

Zazwyczaj listy są używane w strukturach takich jak kolejki, w których istnieje wiele operacji dołączania i usuwania. Przykład: ciągle zmieniająca się lista encji, które powinny zostać zaktualizowane. Sama lista zawiera tylko elementy na ekranie, dlatego często się zmienia.

Wektory (lub tablice) lepiej nadają się do kolekcji, która niewiele się zmienia i gdzie potrzebujesz szybkiego dostępu do poszczególnych elementów w kolekcji. Przykład: Mapa kafelków, w której należy wyszukać kafelki o danym indeksie.

Opinia Tetrads może być prawdziwa, ale zależy to od używanego języka programowania. Widzę, że otagowałeś swoje pytanie c++, ale próbowałem udzielić odpowiedzi, która nie jest specyficzna dla języka.

grzmot
źródło
Cóż, mógłbym również umieścić w nim C, ale nie ma takich kontenerów w C, ale o tym warto pomyśleć: czy jest jakaś biblioteka podobna do STL dla C?
Jokoon
W przeszłości używałem glib ( library.gnome.org/devel/glib ), który implementuje wiele standardowych struktur danych dla C. Nienawidziłem tego, ponieważ zwykle jest zbyt gadatliwy i desperacko chce być C ++, ale jest dojrzały i stabilny.
0

W grach konsolowych nigdy nie używamy std :: list, ponieważ:

  1. dokonuje alokacji pamięci za każdym razem, gdy dodajesz nowy element. przydziały pamięci są wolne.
  2. jest pełen wskazówek. wskaźniki są złe. wskaźnik to brak pamięci podręcznej. chybienie w pamięci podręcznej jest złe.

nawet std :: vector traci popularność na konsolach, ponieważ:

  1. często dbasz tylko na przykład o położenie wszystkich obiektów. na przykład chcesz zderzyć ze sobą obiekty, w którym to przypadku nie obchodzi ich kolor. więc chcesz, aby wszystkie pozycje były przylegające do pamięci i aby kolory były gdzieś daleko, aby uniknąć zanieczyszczenia pamięci podręcznej. ale std :: vector wymaga zapisania wszystkiego dla każdego obiektu w ciągłym kawałku pamięci (np. pozycja, a następnie kolor.), więc jeśli wykonujesz pracę, która odczytuje tylko pozycje, musisz również odczytać wszystkie kolory w pamięci podręcznej, nawet jeśli ich nie użyjesz. to jest marnotrawstwo.
bmcnett
źródło
5
@bmcnett "[] .. ale std :: vector wymaga, abyś przechował wszystko dla każdego obiektu w ciągłym kawałku pamięci" - to nie jest kwestia kontenera, to kwestia układu danych, możesz mieć całą pozycję w ciągłym fragmencie pamięci ze std :: vector:struct point{float x, y, z, w}; std::vector<point> positions;
Maik Semder
moja szkoła pokocha to :)
Jokoon,
2
-1, ponieważ ta odpowiedź nie dodaje niczego do listy vs. dyskusja wektorowa już tutaj, a jej twierdzenie o wektorze zanieczyszczającym pamięć podręczną jest błędne, jak mówi Maik.
źle zrozumiałeś moje roszczenie. nigdy nie powiedziałem, że wśród wszystkich kontenerów std :: vector jest szczególnie winny zanieczyszczenia pamięci podręcznej. wszystkie pojemniki, a nawet tablice, są w równym stopniu winne tego. std :: vector spada z łaski, ponieważ same obiekty C ++ wypadają z łaski. C ++ wymaga, aby dane każdego obiektu były ciągłe w pamięci. można obejść ten problem, unikając obiektów C ++, na przykład używając std :: vector <pozycja>, jak wspomniano powyżej.
bmcnett,
3
Z wyjątkiem tego, że pointjest to obiekt C ++ (taki jaki jest std::vector, tak prosty jak float). Znam rozróżnienie, które próbujesz narysować, ale źle sobie z nim tłumaczysz.