wektor vs. lista w STL

238

Zauważyłem to w Effective STL

wektor to typ sekwencji, który powinien być domyślnie używany.

Co to znaczy Wydaje się, że zignorowanie wydajności vectormoże zrobić wszystko.

Czy ktoś mógłby mi zaproponować scenariusz, w którym vectornie jest to wykonalna opcja, ale listnależy ją zastosować?

skydoor
źródło
6
Chociaż nie jest to pytanie, o które warto zapytać, warto zauważyć, że domyślna wartość wektora oznacza również, że możesz łatwo wchodzić w interakcje ze starszym kodem, bibliotekami C lub bibliotekami bez szablonów, ponieważ wektor jest cienkim opakowaniem wokół „tradycyjnej” dynamicznej tablicy wskaźnika i rozmiar.
18
Bjarne Strostrup faktycznie wykonał test, w którym wygenerował losowe liczby, a następnie dodał je odpowiednio do listy i wektora. Wstawienia zostały wykonane tak, aby lista / wektor były zawsze uporządkowane. Mimo że zazwyczaj jest to „domena listy”, wektor przewyższał listę o DUŻĄ marżę. Powodem jest powolny dostęp do pamięci, a buforowanie działa lepiej dla danych sekwencyjnych. Wszystko to jest dostępne w jego przemówieniu z „GoingNative 2012”
omijającego
1
Jeśli chcesz zobaczyć keynote Bjarne Stroustrup że @evading wspomniano, znalazłem go tutaj: youtu.be/OB-bdWKwXsU?t=2672
brain56

Odpowiedzi:

98

Sytuacje, w których chcesz wstawić wiele elementów w dowolne miejsce poza końcem sekwencji.

Sprawdź gwarancje złożoności dla każdego rodzaju pojemnika:

Jakie są gwarancje złożoności standardowych pojemników?

Martin York
źródło
2
Wstawianie elementów na końcu również się liczy, ponieważ może to prowadzić do alokacji pamięci i kosztów kopiowania elementów. A także wstawianie elenetów na początku wektora jest listpush_front
prawie
9
Nie, wstawianie elementów na końcu wektora jest amortyzowane przez stały czas. Przydziały pamięci zdarzają się tylko sporadycznie i można wstępnie przydzielić wektor, aby temu zapobiec. Oczywiście, jeśli MUSISZ zagwarantować spójne wstawianie stałego czasu, myślę, że nadal jest to problem.
Brian
16
@Notinlist - Czy dla Ciebie to „obok niemożliwego”? v.insert (v.begin (), i)
Manuel
5
@Notinlist - Zgadzam się z tobą, po prostu nie chciałem, aby OP myślał, że interfejs nie istnieje, na wypadek gdyby ktoś chciał zastrzelić się w (wydajnościowej) stopie.
Manuel
16
Bjarne Strostrup faktycznie wykonał test, w którym wygenerował losowe liczby, a następnie dodał je odpowiednio do listy i wektora. Wstawienia zostały wykonane tak, aby lista / wektor były zawsze uporządkowane. Mimo że zazwyczaj jest to „domena listy”, wektor przewyższał listę o DUŻĄ marżę. Powodem jest powolny dostęp do pamięci, a buforowanie działa lepiej dla danych sekwencyjnych. Wszystko to jest dostępne w jego przemówieniu z „GoingNative 2012”
omijającego
409

wektor:

  • Ciągła pamięć.
  • Wstępnie przydziela miejsce dla przyszłych elementów, więc wymagana jest dodatkowa przestrzeń ponad to, co jest konieczne dla samych elementów.
  • Każdy element wymaga tylko miejsca dla samego typu elementu (bez dodatkowych wskaźników).
  • Może ponownie przydzielić pamięć dla całego wektora za każdym razem, gdy dodasz element.
  • Wstawki na końcu są stałym, zamortyzowanym czasem, ale w innych miejscach są kosztowne O (n).
  • Wymazy na końcu wektora to stały czas, ale dla reszty to O (n).
  • Możesz losowo uzyskać dostęp do jego elementów.
  • Iteratory są unieważniane, jeśli dodasz lub usuniesz elementy z wektora lub z niego.
  • Możesz łatwo dostać się do podstawowej tablicy, jeśli potrzebujesz tablicy elementów.

lista:

  • Nieprzylegająca pamięć.
  • Brak wstępnie przydzielonej pamięci. Narzut pamięci dla samej listy jest stały.
  • Każdy element wymaga dodatkowej przestrzeni dla węzła, który zawiera element, w tym wskaźników do następnego i poprzednich elementów na liście.
  • Nigdy nie trzeba ponownie alokować pamięci dla całej listy tylko dlatego, że dodajesz element.
  • Wstawienia i skasowania są tanie, bez względu na to, gdzie występują na liście.
  • Tanie łączenie list ze splicowaniem jest tanie.
  • Nie możesz losowo uzyskać dostępu do elementów, więc dotarcie do określonego elementu na liście może być kosztowne.
  • Iteratory pozostają ważne nawet po dodaniu lub usunięciu elementów z listy.
  • Jeśli potrzebujesz tablicy elementów, musisz utworzyć nowy i dodać je wszystkie, ponieważ nie ma żadnej tablicy.

Zasadniczo używaj wektora, gdy nie obchodzi Cię, jakiego typu kontenera sekwencyjnego używasz, ale jeśli wykonujesz wiele operacji wstawiania lub wymazywania do iz dowolnego miejsca w kontenerze innym niż koniec, będziesz chciał użyć listy. Lub jeśli potrzebujesz dostępu losowego, będziesz potrzebować wektora, a nie listy. Poza tym istnieją oczywiście przypadki, w których będziesz potrzebować jednego lub drugiego na podstawie aplikacji, ale ogólnie są to dobre wytyczne.

Jonathan M. Davis
źródło
2
Ponadto przydzielanie z bezpłatnego sklepu nie jest bezpłatne. :) Dodanie nowych elementów do wektora powoduje przydzielenie O (log n) darmowego sklepu, ale możesz zadzwonić, reserve()aby zredukować to do O (1). Dodanie nowych pozycji do listy (tzn. Ich nie splatanie) powoduje przydzielenie O (n) bezpłatnych sklepów.
bk1e
7
Inną kwestią jest to, że listzwalnia pamięć, gdy usuwasz elementy, ale vectornie. A vectornie zmniejsza jego pojemności po zmniejszeniu jej rozmiaru, chyba że użyjesz swap()lewy.
bk1e
@ bk1e: Naprawdę chcę poznać twoją sztuczkę w rezerwie () i zamianie () :)
Dzung Nguyen
2
@ nXqd: jeśli chcesz dodać N elementów do wektora, wywołaj v.reserve (v.size () + N), aby wykonał tylko jeden wolny przydział magazynu. Sztuczka swap () jest tutaj: stackoverflow.com/questions/253157/how-to-downsize-stdvector
bk1e
1
@simplename Nie. To, co mówi, jest poprawne. wektor przydziela dodatkową przestrzeń poza przestrzeń dla elementów znajdujących się obecnie w wektorze; ta dodatkowa pojemność jest następnie wykorzystywana do wyhodowania wektora, tak że jego wzrost jest amortyzowany przez O (1).
Jonathan M. Davis,
35

Jeśli nie musisz często wstawiać elementów, wektor będzie bardziej wydajny. Ma znacznie lepszą lokalizację pamięci podręcznej procesora niż lista. Innymi słowy, dostęp do jednego elementu bardzo prawdopodobne jest, że następny element jest obecny w pamięci podręcznej i można go odzyskać bez konieczności odczytywania wolnej pamięci RAM.

Hans Passant
źródło
32

W większości odpowiedzi tutaj brakuje jednego ważnego szczegółu: po co?

Co chcesz przechowywać w pojemniku?

Jeśli jest to zbiór ints, to std::liststraci w każdym scenariuszu, bez względu na to, czy możesz dokonać realokacji, usuwasz tylko z przodu itp. Listy przewijają się wolniej, każde wstawienie kosztuje interakcję z alokatorem. Bardzo trudno byłoby przygotować przykład, w którym list<int>bije się vector<int>. I nawet wtedy deque<int>może być lepiej lub bliżej, nie ograniczając się do korzystania z list, które będą miały większy narzut pamięci.

Jeśli jednak masz do czynienia z dużymi, brzydkimi plamami danych - i nielicznymi z nich - nie chcesz ogólnie przydzielać podczas wstawiania, a kopiowanie z powodu realokacji byłoby katastrofą - być może lepiej byłoby list<UglyBlob>niż vector<UglyBlob>.

Jeśli jednak przełączysz się na, vector<UglyBlob*>a nawet vector<shared_ptr<UglyBlob> >ponownie, lista pozostanie w tyle.

Wzorzec dostępu, liczba elementów docelowych itp. Nadal wpływa na porównanie, ale moim zdaniem - rozmiar elementów - koszt kopiowania itp.

Tomasz Gandor
źródło
1
Jeszcze jedno odbicie, które miałem podczas czytania „Effective STL” Meyersa: osobliwą właściwością list<T>jest możliwość splicew O (1) . Jeśli potrzebujesz łączenia w czasie, lista może być również strukturą wyboru;)
Tomasz Gandor
+1 - To nawet nie musi być UglyBlob- nawet obiekty z zaledwie kilkoma członami łańcucha mogą być zbyt drogie do skopiowania, więc przeniesienia będą kosztować. Ponadto: nie zaniedbuj przestrzeni nad głową, która vectormoże spowodować wykładniczy wzrost obiektów trzymających kilkadziesiąt bajtów (jeśli nie możesz reservez góry).
Martin Ba
Jeśli chodzi o vector<smart_ptr<Large>>vs. list<Large>- powiedziałbym, że jeśli potrzebujesz losowego dostępu do elementów, vectorma to sens. Jeśli nie potrzebujesz dostępu losowego, listwydaje się to prostsze i powinno działać równie dobrze.
Martin Ba
19

Jedną specjalną funkcją std :: list jest łączenie (łączenie lub przenoszenie części lub całej listy na inną listę).

A może kopiowanie treści jest bardzo drogie. W takim przypadku tańsze może być na przykład sortowanie kolekcji za pomocą listy.

Należy również pamiętać, że jeśli kolekcja jest niewielka (a jej kopiowanie nie jest szczególnie drogie), wektor może nadal przewyższać listę, nawet jeśli wstawisz i usuniesz gdziekolwiek. Lista alokuje każdy węzeł indywidualnie, a to może być znacznie bardziej kosztowne niż przenoszenie kilku prostych obiektów.

Nie sądzę, że istnieją bardzo trudne zasady. Zależy to od tego, co najczęściej chcesz zrobić z kontenerem, a także od tego, jak duże spodziewasz się kontenera i typu zawartego. Wektor zazwyczaj przebija listę, ponieważ alokuje swoją zawartość jako pojedynczy ciągły blok (jest to zasadniczo tablica alokowana dynamicznie, aw większości przypadków tablica jest najbardziej wydajnym sposobem przechowywania wielu rzeczy).

Wujek Ben
źródło
1
+1. Łączenie jest przeoczone, ale niestety nie jest to czas stały, jak pożądany. : ((((Nie może być, jeśli lista :: size jest stała).
Jestem całkiem pewien, że list :: size jest (może być) liniowy z tego właśnie powodu.
UncleBens,
1
@Roger: list::sizeniekoniecznie jest stały czas. Zobacz stackoverflow.com/questions/228908/is-listsize-really-on i gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
Potatoswatter
@Potatoswatter: To, że standard jest niejasny i że w związku z tym nie można polegać na „zgodnych” implementacjach, stanowi jeszcze większy problem. Dosłownie musisz unikać stdlib, aby uzyskać przenośną i niezawodną gwarancję.
@Roger: tak, niestety. Mój obecny projekt silnie opiera się na operacjach łączenia, a ta struktura jest prawie prosta C. Jeszcze bardziej niestety sekwencja N3000 splicemiędzy różnymi listami jest określona jako złożoność liniowa i sizejest szczególnie stała. Tak więc, aby pomieścić nowicjuszy, którzy iterują sizelub cokolwiek, cała klasa algorytmów jest niedostępna dla STL lub jakiegokolwiek „zgodnego” okresu kontenerów.
Potatoswatter
13

Cóż, uczniowie mojej klasy wydają się całkiem niezdolni do wyjaśnienia mi, kiedy bardziej efektywne jest stosowanie wektorów, ale wyglądają na całkiem zadowolonych, gdy doradzają mi korzystanie z list.

Tak to rozumiem

Listy : Każdy element zawiera adres do następnego lub poprzedniego elementu, więc dzięki tej funkcji możesz losowo losować elementy, nawet jeśli nie zostaną posortowane, kolejność się nie zmieni: jest wydajna, jeśli pamięć jest podzielona. Ale ma też jeszcze jedną bardzo dużą zaletę: możesz łatwo wstawiać / usuwać elementy, ponieważ jedyne, co musisz zrobić, to zmienić niektóre wskaźniki. Wada: Aby odczytać losowy pojedynczy element, musisz przeskakiwać z jednego elementu na drugi, aż znajdziesz właściwy adres.

Wektory : Podczas korzystania z wektorów pamięć jest znacznie bardziej zorganizowana jak zwykłe tablice: każdy n-ty element jest przechowywany tuż po (n-1) i przed (n + 1) element. Dlaczego to jest lepsze niż lista? Ponieważ umożliwia szybki losowy dostęp. Oto jak: jeśli znasz rozmiar elementu w wektorze i jeśli są one ciągłe w pamięci, możesz łatwo przewidzieć, gdzie jest n-ty element; nie musisz przeglądać wszystkich pozycji na liście, aby przeczytać ten, który chcesz, z wektorem, bezpośrednio go czytasz, z listą, której nie możesz. Z drugiej strony, zmodyfikuj tablicę wektorową lub zmień wartość o wiele wolniej.

Listy są bardziej odpowiednie do śledzenia obiektów, które można dodawać / usuwać w pamięci. Wektory są bardziej odpowiednie, gdy chcesz uzyskać dostęp do elementu z dużej liczby pojedynczych elementów.

Nie wiem, w jaki sposób listy są zoptymalizowane, ale musisz wiedzieć, że jeśli chcesz szybkiego dostępu do odczytu, powinieneś używać wektorów, ponieważ jak dobre listy połączeń STL nie będą tak szybkie w dostępie do odczytu niż wektor.

żart
źródło
„modyfikacja tablicy wektorowej lub zmiana wartości jest znacznie wolniejsza” - jak czytamy, wydaje się to przeczyć temu, co powiedziałeś przedtem o predyspozycji wektora do dobrej wydajności ze względu na jego niski i ciągły charakter. Pan myśli, że realokacjivector spowodowane przez zmianę jego rozmiaru może być wolny? następnie zgodził się, ale w przypadkach, w których reserve()można go użyć, pozwala to uniknąć tych problemów.
underscore_d
10

Zasadniczo wektor to tablica z automatycznym zarządzaniem pamięcią. Dane są ciągłe w pamięci. Próba wstawienia danych w środku jest kosztowną operacją.

Na liście dane są przechowywane w niepowiązanych lokalizacjach pamięci. Wstawianie w środku nie wymaga kopiowania niektórych danych, aby zrobić miejsce dla nowego.

Aby dokładniej odpowiedzieć na twoje pytanie, zacytuję tę stronę

wektory są na ogół najbardziej wydajne w czasie w celu uzyskania dostępu do elementów oraz dodania lub usunięcia elementów z końca sekwencji. W przypadku operacji polegających na wstawianiu lub usuwaniu elementów w pozycjach innych niż końcowe, działają one gorzej niż deques i listy oraz mają mniej spójne iteratory i odwołania niż listy.

f4.
źródło
9

Za każdym razem, gdy nie można unieważnić iteratorów.

bezpośrednio
źródło
2
Ale nigdy nie przeskakuj do tego wniosku o iteratorach, nie pytając, czy wystarczające byłyby stałe odniesienia do klasy deque.
Potatoswatter
8

Gdy masz dużo wstawiania lub usuwania w środku sekwencji. np. menedżer pamięci.

ARAK
źródło
więc różnica między nimi polega tylko na wydajności, a nie na kwestii funkcjonalnej.
skydoor
Oba modelują oczywiście sekwencję elementów. Istnieje niewielka różnica w użyciu, o czym wspomniał @dirkgently, ale musisz spojrzeć na złożoność swoich „często wykonywanych” operacji, aby zdecydować, którą sekwencję wybrać (odpowiedź @Martin).
AraK
@skydoor - Istnieje kilka różnic funkcjonalnych. Na przykład tylko wektor obsługuje dostęp losowy (tzn. Może być indeksowany).
Manuel
2
@skydoor: wydajność przekłada się na wydajność. Niska wydajność może zepsuć funkcjonalność. W końcu wydajność jest zaletą C ++.
Potatoswatter
4

Zachowanie ważności iteratorów jest jednym z powodów korzystania z listy. Innym jest, gdy nie chcesz, aby wektor zmieniał położenie podczas pchania przedmiotów. Można to zarządzać za pomocą inteligentnego korzystania z zastrzeżone (), ale w niektórych przypadkach może być łatwiejsze lub bardziej wykonalne po prostu użycie listy.

John Dibling
źródło
4

Jeśli chcesz przenosić obiekty między kontenerami, możesz użyć list::splice.

Na przykład algorytm podziału grafu może mieć stałą liczbę obiektów rekurencyjnie podzieloną między rosnącą liczbę kontenerów. Obiekty powinny być inicjowane raz i zawsze pozostają w tych samych miejscach w pamięci. Znacznie szybciej jest zmienić ich kolejność, łącząc je ponownie, a następnie przenosząc.

Edycja: gdy biblioteki przygotowują się do implementacji C ++ 0x, ogólnym przypadkiem łączenia podsekwencji do listy staje się liniowa złożoność wraz z długością sekwencji. Jest tak, ponieważ splice(teraz) musi iterować sekwencję, aby policzyć w niej liczbę elementów. (Ponieważ lista musi rejestrować swój rozmiar.) Po prostu liczenie i ponowne łączenie listy jest jeszcze szybsze niż jakakolwiek alternatywa, a splatanie całej listy lub pojedynczego elementu to szczególne przypadki o stałej złożoności. Ale jeśli masz długie sekwencje do spięcia, być może będziesz musiał przekopać się w poszukiwaniu lepszego, staromodnego, niezgodnego pojemnika.

Potatoswatter
źródło
2

Jedyną twardą zasadą, w której listnależy zastosować, jest to, że musisz rozdzielić wskaźniki do elementów kontenera.

W przeciwieństwie do tego vector, wiesz, że pamięć elementów nie zostanie ponownie przydzielona. Jeśli tak, to możesz mieć wskaźniki na nieużywaną pamięć, co w najlepszym razie jest dużym nie-nie, aw najgorszym przypadku SEGFAULT.

(Technicznie vectorstanowi *_ptrrównież pracy, ale w takim przypadku są emulacji listtak to tylko semantyka).

Inne miękkie zasady dotyczą możliwych problemów z wydajnością wstawiania elementów do środka kontenera, w związku z czym listlepiej byłoby.

iPherian
źródło
2

Uprość -
Pod koniec dnia, kiedy jesteś zdezorientowany, wybierając kontenery w C ++, użyj tego schematu (Powiedz dzięki): - wprowadź opis obrazu tutaj

Vector
1. wektor jest oparty na zakaźną pamięci
2. wektora jest droga dla małego zbioru danych
3. wektor wykonać najszybciej podczas przechodzenia na zestaw danych
skreślenia 4. wektora wstawiania jest powolny na ogromny zbiór danych, ale szybko do bardzo mały

Lista -
1. lista oparta jest na pamięci sterty
2. lista jest bardzo przydatna w przypadku bardzo dużego zestawu danych
3. lista jest stosunkowo powolna w przypadku przemierzania małego zestawu danych, ale szybka w przypadku dużego zestawu danych
4. usuwanie listy jest szybkie ogromny zestaw danych, ale powolny na mniejszych

xyz xyz
źródło
1

Listy są tylko opakowaniem dla podwójnie LinkedList w stl, oferując w ten sposób funkcję, której można oczekiwać od d-linklist, a mianowicie wstawianie i usuwanie O (1). Podczas gdy wektory są zakaźną sekwencją danych, która działa jak tablica dynamiczna. PS - łatwiejsze do przejścia.

Ritankar Paul
źródło
0

W przypadku wektora i listy główne różnice, które mnie wyróżniają, są następujące:

wektor

  • Wektor przechowuje swoje elementy w ciągłej pamięci. Dlatego możliwy jest losowy dostęp wewnątrz wektora, co oznacza, że ​​dostęp do elementu wektora jest bardzo szybki, ponieważ możemy po prostu pomnożyć adres bazowy z indeksem elementu, aby uzyskać dostęp do tego elementu. W rzeczywistości zajmuje to tylko O ​​(1) lub stały czas.

  • Ponieważ wektor zasadniczo otacza tablicę, za każdym razem, gdy wstawia się element do wektora (tablica dynamiczna), musi on zmienić rozmiar, znajdując nowy ciągły blok pamięci, aby pomieścić nowe elementy, co jest czasochłonne.

  • Nie zużywa dodatkowej pamięci do przechowywania jakichkolwiek wskaźników do innych elementów w nim zawartych.

lista

  • Lista przechowuje swoje elementy w nieciągłej pamięci. Dlatego losowy dostęp nie jest możliwy w obrębie listy, co oznacza, że ​​aby uzyskać dostęp do jego elementów, musimy użyć wskaźników i przejść przez listę, która jest wolniejsza w stosunku do wektora. Zajmuje to czas O (n) lub liniowy, który jest wolniejszy niż O (1).

  • Ponieważ lista korzysta z nieciągłej pamięci, czas potrzebny na wstawienie elementu do listy jest o wiele bardziej wydajny niż w przypadku jej wektorowego odpowiednika, ponieważ unika się ponownego przydziału pamięci.

  • Zużywa dodatkową pamięć do przechowywania wskaźników do elementu przed i po określonym elemencie.

Pamiętając o tych różnicach, zwykle bierzemy pod uwagę pamięć , częsty losowy dostęp i wstawianie, aby zdecydować o zwycięstwie wektora względem listy w danym scenariuszu.

Ardent Coder
źródło
0

Lista jest listą podwójnie połączoną, więc łatwo jest wstawić i usunąć element. Musimy tylko zmienić kilka wskaźników, podczas gdy w wektorze, jeśli chcemy wstawić element na środku, to każdy element po nim musi przesunąć się o jeden indeks. Również jeśli rozmiar wektora jest pełny, musi on najpierw zwiększyć swój rozmiar. Jest to więc droga operacja. Dlatego tam, gdzie wymagane jest częstsze wykonywanie operacji wstawiania i usuwania, w takim przypadku należy stosować listę przypadków.

Siddesh Pawar
źródło