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

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?

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.

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”.

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.

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.

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.

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.

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 .

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.

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.

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.