Jaki jest sens używania list nad wektorami w C ++?

32

Przeprowadziłem 3 różne eksperymenty z listami i wektorami C ++.

Te z wektorami okazały się bardziej wydajne, nawet przy dużej ilości wstawień w środku.

Stąd pytanie: w którym przypadku listy mają większy sens niż wektory?

Jeśli wektory wydają się w większości przypadków wydajniejsze i biorąc pod uwagę podobieństwo ich członków, to jakie korzyści pozostawiają listy?

  1. Wygeneruj N liczb całkowitych i umieść je w pojemniku, aby pojemnik pozostał posortowany. Wstawianie zostało wykonane naiwnie, poprzez czytanie elementów jeden po drugim i wstawianie nowego tuż przed pierwszym większym.
    Z listą czas płynie przez dach, gdy wzrasta wymiar, w porównaniu do wektorów.

  2. Wstaw N liczb całkowitych na końcu pojemnika.
    W przypadku list i wektorów czas wydłużył się o ten sam rząd wielkości, chociaż z wektorami był 3 razy szybszy.

  3. Wstaw N liczb całkowitych do pojemnika.
    Uruchom licznik czasu.
    Posortuj kontener za pomocą list.sort dla list i std :: sort dla wektorów. Zatrzymaj minutnik.
    Ponownie czas wzrasta o ten sam rząd wielkości, ale jest średnio 5 razy szybszy w przypadku wektorów.

Mogę nadal przeprowadzać testy i wymyślić kilka przykładów, w których listy okazałyby się lepsze.

Ale wspólne doświadczenie was czytających tę wiadomość może dostarczyć bardziej produktywnych odpowiedzi.

Być może natrafiłeś na sytuacje, w których listy były wygodniejsze w użyciu lub działały lepiej?

Marek Stanley
źródło
2
Powinieneś spojrzeć na Kiedy używać połączonej listy nad tablicą / listą tablic? jeśli jeszcze tego nie zrobiłeś
Karthik T
1
Oto kolejny dobry zasób na ten temat: stackoverflow.com/a/2209564/8360 również, większość wskazówek w C ++, które słyszałem, to domyślnie używać wektora, listy tylko, jeśli masz konkretny powód.
Zachary Yates
Dziękuję Ci. Nie zgadzam się jednak z większością wypowiedzi zawartych w ulubionej odpowiedzi. Większość tych z góry przyjętych pomysłów została unieważniona przez moje eksperymenty. Ta osoba nie przeprowadziła żadnego testu i nie zastosowała rozpowszechnionej teorii nauczanej w książkach lub w szkole.
Marek Stanley
1
listPrawdopodobnie nie lepiej jeśli usuwasz wiele elementów. Nie wierzę, vectorże kiedykolwiek zwróci pamięć do systemu, dopóki cały wektor nie zostanie usunięty. Pamiętaj też, że Twój test nr 1 nie polega wyłącznie na testowaniu czasu wstawiania. To test łączący wyszukiwanie i wstawianie. Znalezienie miejsca na wstawienie listjest wolne. Rzeczywista wstawka będzie szybsza niż wektor.
Gort the Robot
3
Jest to bardzo typowe, że to pytanie jest opisywane w kategoriach wydajności (czasu wykonywania), wydajności i tylko wydajności. Wydaje się, że jest to martwy punkt dla wielu programistów - skupiają się na tym aspekcie i zapominają, że istnieją dziesiątki innych aspektów, które często są o wiele, wiele ważniejsze.
Doc Brown

Odpowiedzi:

34

Krótka odpowiedź brzmi: przypadki wydają się być nieliczne i dalekie od siebie. Prawdopodobnie jest ich jednak kilka.

Jednym z nich byłoby przechowywanie niewielkiej liczby dużych obiektów - szczególnie takich, które są tak duże, że przydzielenie miejsca nawet dla kilku dodatkowych jest niepraktyczne. Zasadniczo nie ma sposobu, aby powstrzymać wektor lub deque przed przydzieleniem miejsca na dodatkowe obiekty - to sposób, w jaki są one definiowane (tj. Muszą przydzielić dodatkowe miejsce, aby spełnić wymagania dotyczące złożoności). Jeśli całkowicie nie możesz przydzielić tej dodatkowej przestrzeni, std::listmoże to być jedyny standardowy pojemnik, który spełnia twoje potrzeby.

Innym byłoby, gdy / jeśli będziesz przechowywać iterator przez dłuższy czas w „interesującym” punkcie listy, a kiedy robisz wstawianie i / lub usuwanie, (prawie) zawsze robisz to od miejsca, do którego masz już iterator, więc nie przechodzisz przez listę, aby przejść do punktu, w którym chcesz wstawić lub usunąć. Oczywiście to samo dotyczy sytuacji, gdy pracujesz z więcej niż jednym miejscem, ale nadal planujesz przechowywać iterator w każdym miejscu, z którym prawdopodobnie będziesz pracować, więc najbardziej manipulujesz miejscami, do których możesz dotrzeć bezpośrednio, i rzadko kiedy przechodzisz przez listę, aby uzyskać do tych miejsc.

Na przykład pierwszy, rozważ przeglądarkę internetową. Może przechowywać połączoną listę Tabobiektów, przy czym każdy obiekt karty reprezentuje otwartą kartę w przeglądarce. Każda karta może zawierać kilkadziesiąt megabajtów danych (więcej, zwłaszcza jeśli dotyczy to czegoś takiego jak wideo). Twoja typowa liczba otwartych kart może z łatwością być mniejsza niż tuzin, a 100 jest prawdopodobnie zbliżone do górnej granicy.

Na przykład drugi, rozważmy edytor tekstu, który przechowuje tekst jako połączoną listę rozdziałów, z których każdy może zawierać połączoną listę (powiedzmy) akapitów. Kiedy użytkownik edytuje, zwykle znajdzie określone miejsce, w którym będzie edytować, a następnie wykona sporo pracy w tym miejscu (w każdym razie wewnątrz tego akapitu). Tak, od czasu do czasu będą przechodzić od jednego akapitu do drugiego, ale w większości przypadków będzie to akapit w pobliżu miejsca, w którym już pracowali.

Raz na jakiś czas (takie jak wyszukiwanie globalne i zamiana) kończysz przeglądanie wszystkich elementów na wszystkich listach, ale jest to dość rzadkie, a nawet jeśli to zrobisz, prawdopodobnie wykonasz wystarczającą pracę w wyszukiwaniu elementu w lista, że ​​czas przejścia przez listę jest prawie nieistotny.

Zauważ, że w typowym przypadku może to również pasować do pierwszego kryterium - rozdział zawiera dość małą liczbę akapitów, z których każdy może być dość duży (przynajmniej w stosunku do wielkości wskaźników w węzeł itp.). Podobnie masz stosunkowo niewielką liczbę rozdziałów, z których każdy może mieć kilka kilobajtów.

To powiedziawszy, muszę przyznać, że oba te przykłady są prawdopodobnie nieco wymyślone i chociaż lista połączona może działać doskonale w obu przypadkach, prawdopodobnie nie zapewniłaby ogromnej korzyści w obu przypadkach. W obu przypadkach, na przykład, przydzielenie dodatkowej przestrzeni w wektorze dla niektórych (pustych) stron / kart lub niektórych pustych rozdziałów jest mało prawdopodobne.

Jerry Coffin
źródło
4
+1, ale: Pierwszy przypadek znika, gdy używasz wskaźników, których zawsze powinieneś używać w przypadku dużych obiektów. Listy połączone również nie są odpowiednie dla przykładu drugiego; tablice posiadają wszystkie operacje, gdy są one tak krótkie.
amara
2
Przypadek dużego obiektu w ogóle nie działa. Korzystanie std::vectorze wskaźników będzie bardziej wydajne niż wszystkie połączone obiekty węzłów listy.
Winston Ewert
Istnieje wiele zastosowań list połączonych - po prostu nie są one tak powszechne jak tablice dynamiczne. Pamięć podręczna LRU jest jednym z powszechnych zastosowań połączonej listy.
Charles Salvia
Również std::vector<std::unique_ptr<T>>może być dobrą alternatywą.
Deduplicator
24

Według samego Bjarne'a Stroustrupa wektory powinny zawsze być domyślną kolekcją sekwencji danych. Możesz wybrać listę, jeśli chcesz zoptymalizować wstawianie i usuwanie elementów, ale zwykle nie powinieneś. Kosztami tej listy jest powolne przechodzenie i zużycie pamięci.

Mówi o tym w tej prezentacji .

Około 0:44 mówi o wektorach vs. ogólnie o listach.

Zwartość ma znaczenie. Wektory są bardziej zwarte niż listy. A przewidywalne wzorce użytkowania mają ogromne znaczenie. W przypadku wektorów należy przesunąć wiele elementów, ale pamięci podręczne są w tym naprawdę bardzo dobre. ... Listy nie mają losowego dostępu. Ale kiedy przeglądasz listę, wciąż masz dostęp losowy. Jest tu węzeł, który trafia do tego węzła w pamięci. W rzeczywistości masz losowy dostęp do swojej pamięci i maksymalizujesz straty w pamięci podręcznej, co jest dokładnie przeciwieństwem tego, czego chcesz.

Około 1:08 otrzymuje pytanie dotyczące tego problemu.

Powinniśmy zobaczyć, że potrzebujemy sekwencji elementów. Domyślną sekwencją elementów w C ++ jest wektor. Teraz, ponieważ jest kompaktowy i wydajny. Wdrażanie, mapowanie do sprzętu ma znaczenie. Teraz, jeśli chcesz zoptymalizować wstawianie i usuwanie - mówisz: „No cóż, nie chcę domyślnej wersji sekwencji. Chcę specjalistyczny, który jest listą ”. A jeśli to zrobisz, powinieneś wiedzieć wystarczająco dużo, aby powiedzieć: „Akceptuję pewne koszty i pewne problemy, takie jak powolne podróże i większe zużycie pamięci”.

Pete
źródło
1
czy mógłbyś napisać w skrócie, co zostało powiedziane w prezentacji, do której linkujesz „około 0:44 i 1:08”?
komar
2
@gnat - z pewnością. Próbowałem zacytować rzeczy, które mają sens osobno, i które potrzebują kontekstu slajdów.
Pete
11

Jedynym miejscem, w którym zazwyczaj używam list, jest wymazanie elementów i nie unieważnianie iteratorów. std::vectorunieważnia wszystkie iteratory przy wstawianiu i usuwaniu. std::listgwarantuje, że iteratory do istniejących elementów są nadal aktualne po wstawieniu lub usunięciu.

UldisK
źródło
4

Oprócz innych już dostarczonych odpowiedzi, listy mają pewne cechy, które nie istnieją w wektorach (ponieważ byłyby niesamowicie drogie). Operacje łączenia i scalania są najważniejsze. Jeśli często masz kilka list, które należy dołączyć lub scalić, lista jest prawdopodobnie dobrym wyborem.

Ale jeśli nie musisz wykonywać tych operacji, prawdopodobnie nie.

David C.
źródło
3

Brak nieodłącznej pamięci podręcznej / przyjazności stron połączonych list sprawia, że ​​są one prawie całkowicie odrzucane przez wielu programistów C ++, z dobrym uzasadnieniem w tej domyślnej formie.

Listy połączone mogą być nadal wspaniałe

Jednak połączone listy mogą być wspaniałe, gdy są wspierane przez stały alokator, który przywraca im tę przestrzenną lokalizację, której z natury im brakuje.

Ich celem jest to, że możemy podzielić listę na dwie listy, na przykład, po prostu przechowując nowy wskaźnik i manipulując wskaźnikiem lub dwoma. Możemy przenosić węzły z jednej listy do drugiej w stałym czasie poprzez zwykłą manipulację wskaźnikiem, a pusta lista może po prostu kosztować pamięć pojedynczego headwskaźnika.

Prosty akcelerator siatki

Jako praktyczny przykład rozważ symulację wizualną 2D. Ma przewijany ekran z mapą obejmującą 400 x 400 (160 000 komórek siatki) wykorzystywaną do przyspieszania rzeczy, takich jak wykrywanie kolizji między milionami cząstek poruszających się po każdej ramce (unikamy tutaj drzewek czworokątnych, ponieważ faktycznie mają one gorsze wyniki z tym poziomem dane dynamiczne). Cała wiązka cząstek stale przemieszcza się w każdej klatce, co oznacza, że ​​nieustannie przechodzą z jednej komórki siatki do drugiej.

W takim przypadku, jeśli każda cząstka jest pojedynczo połączonym węzłem listy, każda komórka siatki może zacząć jako headwskaźnik, który wskazuje nullptr. Kiedy rodzi się nowa cząstka, po prostu umieszczamy ją w komórce siatki, w której rezyduje, ustawiając headwskaźnik tej komórki tak, aby wskazywał na ten węzeł cząstek. Kiedy cząstka przesuwa się z jednej komórki siatki do drugiej, po prostu manipulujemy wskaźnikami.

Może to być znacznie bardziej wydajne niż przechowywanie 160 000 vectorsdla każdej komórki siatki i ciągłe cofanie i kasowanie od środka, klatka po klatce.

std :: list

Dotyczy to ręcznie zwijanych, natrętnych, pojedynczo połączonych list wspieranych przez stały alokator. std::listreprezentuje podwójnie połączoną listę i może nie być tak zwarta, gdy jest pusta jak pojedynczy wskaźnik (różni się w zależności od implementacji dostawcy), a dodatkowo utrudnieniem jest wdrożenie niestandardowych alokatorów w std::allocatorformie.

Muszę przyznać, że nigdy nie używam list. Ale powiązane listy mogą być nadal wspaniałe! Jednak nie są cudowni z powodów, dla których ludzie często mają ochotę ich używać, i nie są tak wspaniali, chyba że są wspierani przez bardzo wydajny stały alokator, który łagodzi wiele obowiązkowych błędów stron i związanych z nimi braków w pamięci podręcznej.


źródło
1
Jest to standardowy pojedynczo-linked list od C ++ 11 std::forward_list.
sharyex,
2

Należy wziąć pod uwagę rozmiar elementów w kontenerze.

int wektor elementów jest bardzo szybki, ponieważ większość danych mieści się w pamięci podręcznej procesora (a do kopiowania danych prawdopodobnie można użyć instrukcji SIMD).

Jeśli rozmiar elementu jest większy, wynik testu 1 i 3 może się znacznie zmienić.

Z bardzo kompleksowego porównania wydajności :

To wyciąga proste wnioski na temat wykorzystania każdej struktury danych:

  • Crunching numerów: użyj std::vectorlubstd::deque
  • Wyszukiwanie liniowe: użyj std::vectorlubstd::deque
  • Losowe wstawianie / usuwanie:
    • Mały rozmiar danych: użyj std::vector
    • Duży rozmiar elementu: użyj std::list(chyba że jest przeznaczony głównie do wyszukiwania)
  • Nietrywialny typ danych: używaj, std::listchyba że potrzebujesz kontenera szczególnie do wyszukiwania. Ale w przypadku wielu modyfikacji kontenera będzie on bardzo wolny.
  • Push to front: użyj std::dequelubstd::list

(na marginesie std::dequeto bardzo niedoceniana struktura danych).

Z wygodnego punktu widzenia std::listgwarantuje, że iteratory nigdy nie zostaną unieważnione podczas wstawiania i usuwania innych elementów. To często kluczowy aspekt.

manlio
źródło
2

Moim zdaniem najważniejszym powodem używania list jest unieważnienie iteratora : jeśli dodasz / usuniesz elementy do wektora, wszystkie wskaźniki, referencje, iteratory, które trzymałeś dla poszczególnych elementów tego wektora, mogą zostać unieważnione i prowadzić do subtelnych błędów .. lub błędy segmentacji.

Nie jest tak w przypadku list.

Dokładne reguły dla wszystkich standardowych kontenerów podano w tym poście StackOverflow .

Jean-Michaël Celerier
źródło
0

Krótko mówiąc, nie ma dobrego powodu, aby używać std::list<>:

  • Jeśli potrzebujesz nieposortowanego pojemnika, std::vector<>reguły.
    (Usuń elementy, zastępując je ostatnim elementem wektora.)

  • Jeśli potrzebujesz posortowanego pojemnika, std::vector<shared_ptr<>>reguły.

  • Jeśli potrzebujesz rzadkiego indeksu, std::unordered_map<>reguły.

to jest to!

Uważam, że jest tylko jedna sytuacja, w której mam tendencję do korzystania z połączonej listy: Kiedy mam istniejące obiekty, które muszą być w jakiś sposób połączone, aby zaimplementować dodatkową logikę aplikacji. Jednak w takim przypadku nigdy nie używam std::list<>, raczej uciekam się do (inteligentnego) następnego wskaźnika wewnątrz obiektu, zwłaszcza, że ​​większość przypadków użycia powoduje utworzenie drzewa zamiast listy liniowej. W niektórych przypadkach powstała struktura jest połączoną listą, w innych jest to drzewo lub ukierunkowany wykres acykliczny. Głównym celem tych wskaźników jest zawsze budowanie logicznej struktury, a nie zarządzanie obiektami. Mamy std::vector<>na to.

cmaster
źródło
-1

Musisz pokazać, jak robiłeś wkładki w pierwszym teście. Twój drugi i trzeci test, wektor łatwo wygra.

Znaczące wykorzystanie list ma miejsce, gdy trzeba wspierać usuwanie elementów podczas iteracji. Po zmodyfikowaniu wektora wszystkie iteratory są (potencjalnie) nieprawidłowe. W przypadku listy tylko iterator usuniętego elementu jest nieprawidłowy. Wszystkie pozostałe iteratory pozostają ważne.

Typowa kolejność użycia pojemników to wektor, deque, a następnie lista. Wybór kontenera jest zwykle oparty na push_back wybierz wektor, pop_front wybierz deque, wstaw listę wyboru.

Bill Door
źródło
3
podczas usuwania elementów podczas iteracji zwykle lepiej jest użyć wektora i po prostu utworzyć nowy wektor dla wyników
amara
-1

Jednym z czynników, o którym myślę, jest to, że wraz ze wzrostem wektora wolna pamięć ulega fragmentacji, gdy wektor zwalnia swoją pamięć i przydziela w kółko większy blok. To nie będzie problem z listami.

Jest to oprócz tego, że duża liczba push_backs bez rezerw spowoduje również kopiowanie podczas każdej zmiany rozmiaru, co czyni go nieefektywnym. Podobnie wstawianie na środku powoduje ruch wszystkich elementów w prawo, a nawet gorzej.

Nie wiem jednak, czy jest to poważny problem, ale był to powód, dla którego podano mi w pracy (tworzenie gier mobilnych), aby unikać wektorów.

Karthik T.
źródło
1
nie, wektor zostanie skopiowany, a to jest drogie. Ale przeglądanie połączonej listy (aby dowiedzieć się, gdzie wstawić) jest również kosztowne. Kluczem jest rzeczywiście zmierzyć
Kate Gregory
@KateGregory Poza tym miałem na myśli, Pozwól, że odpowiednio zmodyfikuję
Karthik T
3
Racja, ale wierzcie lub nie (a większość ludzi nie wierzy) koszt, o którym nie wspomnieliście, przeglądając połączoną listę, aby znaleźć miejsce, w którym należy WKŁADAĆ te kopie (zwłaszcza jeśli elementy są małe (lub ruchome, ponieważ wtedy są ruchami)), a wektor jest często (lub nawet zwykle) szybszy. Uwierz lub nie.
Kate Gregory