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?
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.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.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?
źródło
list
Prawdopodobnie 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 wstawienielist
jest wolne. Rzeczywista wstawka będzie szybsza niż wektor.Odpowiedzi:
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::list
moż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ę
Tab
obiektó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.
źródło
std::vector
ze wskaźników będzie bardziej wydajne niż wszystkie połączone obiekty węzłów listy.std::vector<std::unique_ptr<T>>
może być dobrą alternatywą.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.
Około 1:08 otrzymuje pytanie dotyczące tego problemu.
źródło
Jedynym miejscem, w którym zazwyczaj używam list, jest wymazanie elementów i nie unieważnianie iteratorów.
std::vector
unieważnia wszystkie iteratory przy wstawianiu i usuwaniu.std::list
gwarantuje, że iteratory do istniejących elementów są nadal aktualne po wstawieniu lub usunięciu.źródło
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.
źródło
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
head
wskaź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
head
wskaźnik, który wskazujenullptr
. Kiedy rodzi się nowa cząstka, po prostu umieszczamy ją w komórce siatki, w której rezyduje, ustawiająchead
wskaź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
vectors
dla 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::list
reprezentuje 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 wstd::allocator
formie.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
std::forward_list
.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 :
(na marginesie
std::deque
to bardzo niedoceniana struktura danych).Z wygodnego punktu widzenia
std::list
gwarantuje, że iteratory nigdy nie zostaną unieważnione podczas wstawiania i usuwania innych elementów. To często kluczowy aspekt.źródło
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 .
źródło
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. Mamystd::vector<>
na to.źródło
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.
źródło
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_back
s 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.
źródło