wektor vs. lista w STL

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ć?

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?

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.

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.

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.

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

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.

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.

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

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

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.

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.

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.

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

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.

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.

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.