Dla prostej, połączonej listy, w której losowy dostęp do elementów listy nie jest wymagany, czy istnieją jakieś znaczące zalety (wydajność lub inne) korzystania z std::list zamiast z std::vector? Jeśli wymagane jest przejście w tył, czy bardziej efektywne byłoby użycie listy przed iteracją nad jej elementami?Względna wydajność std :: vector vs. std :: list vs. std :: slist?
Jak zwykle, najlepszą odpowiedzią na pytania dotyczące wydajności jest profile obydwie implementacje dla Twojego przypadku użycia i zobacz, które jest szybsze.
W ogóle, jeśli masz wstawki do danych strukturze (inne niż na koniec), a następnie vector może być wolniejsze, w przeciwnym razie w większości przypadków oczekuje się vector wykonać lepiej niż list choćby data locality issues oznacza to, że jeśli dwie elementy znajdujące się w zestawie danych sąsiadują z pamięcią, następny element będzie już w pamięci podręcznej procesora i nie będzie musiał stronicować pamięci w pamięci podręcznej.
Należy również pamiętać, że nadwyżka przestrzeni dla obiektu vector jest stała (3 wskaźniki), podczas gdy narzut przestrzeni dla modelu list jest opłacany dla każdego elementu, zmniejsza to również liczbę pełnych elementów (danych i narzutów), które mogą znajdować się w pamięci podręcznej w dowolnym momencie.
Należy pamiętać, że nawet wstawienia są szybsze w wektorze niż na liście połączonej, jeśli trzeba wyszukać lokalizację do wstawienia.Na przykład, biorąc kilka losowych liczb całkowitych i wstawiając je w porządku posortowanym do wektora lub listy połączonej - wektor będzie zawsze szybszy, niezależnie od liczby pozycji ogółem, z powodu braku pamięci podręcznej podczas wyszukiwania punktu wstawienia w połączona lista. – Collin
Prawie jedyne miejsce, w którym połączona lista jest szybsza, jest wtedy, gdy robisz dużo splicingu, ponieważ nie wymaga to dużej liczby pomyłek w pamięci podręcznej, a każde spięcie jest operacją o stałym czasie (która może przenosić dużą liczbę elementów z jednej listy połączonej do drugiej). – Collin
"Należy również pamiętać, że przestrzeń dla wektora jest stała" Tylko jeśli jesteś bardzo ostrożny. W przypadku zwykłego użycia, ma on liniowy nadmiar przestrzeni, taki sam jak "lista". Zobacz: amortyzowane liniowe push_back. –
Po prostu nie. Lista ma przewagę nad Vectorem, ale sekwencyjny dostęp nie jest jednym z nich - jeśli to wszystko, co robisz, to wektor jest lepszy.
Jednak ... wektor jest droższy w dodawaniu dodatkowych elementów niż lista, szczególnie jeśli wstawiasz w środku.
Zrozumieć, jak te kolekcje są zaimplementowane: wektor jest sekwencyjną tablicą danych, lista jest elementem, który zawiera dane i wskaźniki do następnych elementów. Gdy to zrozumiesz, zrozumiesz, dlaczego listy są dobre dla wstawek, a złe dla dostępu losowego.
(tak, odwrotna iteracja wektorem jest dokładnie taka sama jak w przypadku przodu iteracji - iterator tylko odejmuje od wielkości przesyłanych danych za każdym razem, lista musi jeszcze przejść do następnego elementu za pomocą wskaźnika)
Jest to oczywiste i w 99% przypadków poprawna odpowiedź. Jeśli potrzebujesz przejścia wstecz, uruchom pętlę for backwards. Tablice/Wektory zapewniają dostęp losowy, bardzo szybki dostęp sekwencyjny i równie szybki dostęp sekwencyjny z dowolnego losowego punktu startowego w wektorze. Listy upodobane mają tylko jeden forte ", który polega na usuwaniu członków lub wstawianiu członków w pewnym momencie na liście. Oni prawie wszystko wysysają. Powolny, powolny, powolny. Tworzenie tablicy/wektora jest tak proste, jak nowe malloc() i memmove(). Używając Vprime, Vgrow, możesz po prostu ponownie je przypisać i kopiować tam iz powrotem. – RocketRoy
Jeśli potrzebujesz przejścia wstecznego, slist najprawdopodobniej nie stanie się twoją strukturą.
Konwencjonalna (podwójnie) połączona lista zapewnia stały czas wstawiania i usuwania w dowolnym miejscu na liście; wektor daje tylko amortyzowane wstawianie i usuwanie czasu stałego na końcu listy. Dla wektora wstawiania i usuwania czas jest liniowy nigdzie poza końcem. To nie jest cała historia; są również stałe czynniki. Wektor jest prostszą strukturą danych, która ma zalety i wady w zależności od kontekstu.
Najlepszym sposobem zrozumienia tego jest zrozumienie, w jaki sposób są one realizowane. Połączona lista ma następny i poprzedni wskaźnik dla każdego elementu. Wektor ma tablicę elementów adresowanych przez indeks. Z tego widać, że obydwa potrafią efektywnie przechodzić do przodu i do tyłu, podczas gdy tylko wektor może zapewnić efektywny losowy dostęp. Można również zauważyć, że narzut pamięci związany z połączoną listą jest dla każdego elementu, podczas gdy dla wektora jest stały. Możesz również zobaczyć, dlaczego czas wstawiania różni się między tymi dwiema strukturami.
Ważne jest to, że listy mają dodatkowe wskaźniki na element, podczas gdy wektor ma tylko trzy wskaźniki dla całej struktury danych. – Motti
Tak, to prawda: Moja odpowiedź mówi: "Połączona lista ma następny poprzedni wskaźnik dla każdego elementu, wektor ma tablicę elementów adresowanych przez indeks." Najwyraźniej brakuje słowa "i" (!), A ja wyjaśnię dodatkowe wskazówki. – janm
Zobacz to pytanie Szczegółowe informacje na temat kosztów:
What are the complexity Guarantees of the standard containers
Jeśli masz slist a teraz chcą przemierzać je w odwrotnej kolejności, dlaczego nie zmienić typ do listy wszędzie?
Domyślna struktura danych do przemyślenia w C++ to Vector.
Rozważmy następujące punkty ...
1] przemierzania:
węzły Lista rozrzucone są wszędzie w pamięci, a tym samym prowadzi do przejścia lista cache strzela. Ale przemiatanie wektorów jest płynne.
2] wstawiania i usuwania:
Średnie 50% elementów musi być przesunięty, kiedy to zrobić do EVO ale buforuje są bardzo dobre w tym! Ale z listami musisz przemieszczenie do punktu wstawiania/usuwania ... tak znowu ... cache chybi! I zaskakująco wektory również wygrywają tę sprawę!
3] Przechowywanie:
Podczas korzystania z wykazów, są 2 wskaźniki per elementów (przód & tył) więc lista jest znacznie większy niż Vector! Wektory potrzebują tylko trochę więcej pamięci niż wymagają rzeczywiste elementy.
Powinieneś mieć powód, aby nie używać wektora.
Myślę, że masz na myśli brak pamięci podręcznej, ale jako twórca gier niezależnych, kod, który piszę, również miał trochę braków w gotówce. –
http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs Kindof samo, jak mówi Bjarne, ale z lepszymi liczbami i kodem źródłowym do testów. – gulgi
@gulgi, ten link zasługuje na osobną odpowiedź, a nie tylko komentarz. Byłoby miło mieć wykres i krótkie wyjaśnienia tutaj na Stackoverflow. –
niektórych rygorystycznych benchmarków na temat: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
Jak już zauważono w innych, przylegająca do przechowywania pamięci oznacza std: : wektor jest lepszy dla większości rzeczy. Nie ma praktycznie żadnego powodu, aby używać std :: list, z wyjątkiem małych ilości danych (gdzie wszystko może zmieścić się w pamięci podręcznej) i/lub gdzie częste są usuwanie i ponowne wstawianie. Gwarancja złożoności nie odnosi się do wydajności w świecie rzeczywistym ze względu na różnicę między pamięcią podręczną a pamięcią główną (200x) oraz na to, jak ciągły dostęp do pamięci wpływa na użycie pamięci podręcznej. Zobacz Chandler Carruth (google) mówić o problemie tutaj: https://www.youtube.com/watch?v=fHNmRkzxHWs
i dane Mike Acton w rozmowie projektowanie zorientowane tutaj: https://www.youtube.com/watch?v=rX0ItVEVjHc
(Late komentarza, tylko do zapisu): Link do wykładu Bjarne Stroustrup: "Dlaczego powinieneś unikać list połączonych", gdzie twierdzi, że wektory są zawsze lepsze niż listy. Powodem, dla którego podaje, jest to, że poszukiwania punktu wstawienia przeważnie dominują nad wysiłkiem, a przesunięcie elementów (w wektorach) jest nieznaczne * w porównaniu *. Również: chybienie pamięci podręcznej, ale zostało to już wspomniane w odpowiedzi poniżej. Wideo: http://www.youtube.com/watch?v=YQs6IC-vgmo –
Mimo że lista jest prawie zawsze wolniejsza od wektorowej (z wyjątkiem sytuacji, gdy wykonuje się wysoki poziom łączenia), to jeden raz absolutnie POTRZEBUJESZ listy: stabilna iteratory. Jeśli zachowasz kopie iteratorów, które zawsze będą wskazywały ten sam element (chyba że został usunięty), to nie jest to gwarancja, którą może dostarczyć wektor (np. Wywołanie funkcji push_back może unieważnić wszystkie iteratory). Korzystanie z pul pamięci może sprawić, że prędkość listy będzie o wiele bliższa wartości wektora. – coderforlife