vector vs. list w STL

Wektor:

• pamięć ciągła.
• wstępnie przydziela przestrzeń dla przyszłych elementów, więc wymagana jest dodatkowa przestrzeń poza to, co jest niezbędne 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, amortyzowanym czasem, ale wstawki gdzie indziej są kosztownym O (n).
• kasowanie na końcu wektora jest stały czas, ale dla reszty jest to O (n).
• możesz losowo uzyskać dostęp do jego elementów.
• Iteratory są unieważniane, jeśli dodasz lub usuniesz elementy do lub z wektora.
• możesz łatwo dostać się do tablicy bazowej, jeśli potrzebujesz tablicy elementów.

Lista:

• pamięć nieciągła.
• Brak wstępnie przydzielonej pamięci. Narzut pamięci dla samej listy jest stały.
• każdy element wymaga dodatkowych miejsce na węzeł, który przechowuje element, w tym wskaźniki do następnego i poprzedniego elementu na liście.
• Nigdy nie musi ponownie przydzielać pamięci dla całej listy tylko dlatego, że dodajesz element.
• wstawiania i Kasowania są tanie, bez względu na to, gdzie na liście występują.
• Tanie jest łączenie list z splicingiem.
• nie można 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 wtedy, gdy dodajesz lub usuwasz elementy z listy.
• Jeśli potrzebujesz tablicy elementów, musisz utworzyć nową i dodać je wszystkie do niej, ponieważ nie ma tablicy bazowej.

Ogólnie rzecz biorąc, używaj vector, gdy nie zależy ci na tym, jakiego typu kontenera sekwencyjnego używasz, ale jeśli robisz wiele wstawek lub usunięć w dowolnym miejscu kontenera poza końcem, będziesz chciał użyć list. Lub jeśli potrzebujesz dostępu losowego, to będziesz chciał vector, Nie lista. Poza tym istnieją oczywiście przypadki, w których będziesz potrzebować jednej lub drugiej w oparciu o Twoją aplikację, ale ogólnie Są to dobre wytyczne.

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

Większość odpowiedzi tutaj brakuje jednego ważnego szczegółu: po co?

Co chcesz trzymać w pojemniku?

Jeśli jest zbiorem int s, to std::list straci się w każdym scenariuszu, niezależnie od tego, czy można realokować, usuwać tylko z przodu itp. Listy są wolniejsze w przemieszczaniu, każde wstawianie kosztuje interakcję z alokatorem... Bardzo trudno byłoby przygotować przykład, gdzie list<int> bije vector<int>. I nawet wtedy deque<int> może być lepiej lub blisko, nie wystarczy skorzystać z list, które będą miały większy narzut pamięci.

Jednakże, jeśli masz do czynienia z dużymi, brzydkimi plamami danych - i kilkoma z nich - nie chcesz nadmiernie przydzielać danych podczas wstawiania, a kopiowanie z powodu realokacji byłoby katastrofą - wtedy może być lepiej z list<UglyBlob> niż vector<UglyBlob>.

Mimo to, jeśli przełączysz się na vector<UglyBlob*> lub nawet vector<shared_ptr<UglyBlob> >, ponownie-list pozostanie w tyle.

Tak więc, wzorzec dostępu, liczba elementów docelowych itp. nadal wpływa na porównanie, ale moim zdaniem - wielkość elementów - koszt kopiowania itp.

Jedną ze specjalnych możliwości std:: list jest splicing (łączenie lub przenoszenie części lub całej listy na inną listę).

A może jeśli Twoje treści są bardzo drogie w kopiowaniu. W takim przypadku tańsze może być np. posortowanie kolekcji z listą.

Zauważ również, że jeśli kolekcja jest mała (a zawartość nie jest szczególnie droga do skopiowania), wektor może nadal przewyższać listę, nawet jeśli wstawisz i usuniesz gdziekolwiek. Lista przydziela każdy węzeł indywidualnie, a to może być znacznie droższe niż przenoszenie kilku prostych obiektów.

Myślę, że nie ma zbyt trudnych zasad. Zależy to od tego, co chcesz zrobić z kontenerem, a także od tego, jak duży będzie kontener i jaki będzie zawierał Typ. Wektor zazwyczaj przewyższa listę, ponieważ przydziela jej zawartość jako pojedynczy przylegający blok (jest to w zasadzie dynamicznie przydzielana tablica, a w większości przypadków tablica jest najbardziej efektywnym sposobem przechowywania kilka rzeczy).

Cóż, uczniowie z mojej klasy nie są w stanie wyjaśnić mi, kiedy bardziej skuteczne jest używanie wektorów, ale wyglądają na szczęśliwych, gdy doradzają mi używanie list.

Tak to Rozumiem

Listy : Każdy element zawiera adres do następnego lub poprzedniego elementu, więc dzięki tej funkcji możesz losować elementy, nawet jeśli nie są posortowane, kolejność nie ulegnie zmianie: jest wydajna, jeśli pamięć jest fragmentowana. Ale ma również inną bardzo dużą zaletę: ty można ł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 do drugiego, aż znajdziesz poprawny adres.

Wektory : Przy użyciu wektorów pamięć jest znacznie bardziej zorganizowana jak zwykłe tablice: każda N-ta pozycja jest przechowywana tuż po (n-1)Tej pozycji i przed (n+1) Tej pozycji. Dlaczego to jest lepsze niż lista? Ponieważ umożliwia szybki losowy dostęp. Oto jak: jeśli znasz rozmiar element w wektorze, a jeśli są one przylegające do pamięci, można łatwo przewidzieć, gdzie n-ten element jest; nie musisz przeglądać wszystkich elementów listy, aby przeczytać ten, który chcesz, z vector, można bezpośrednio przeczytać go, z listy nie można. Z drugiej strony, modyfikacja tablicy wektorowej lub zmiana wartości jest znacznie wolniejsza.

Listy są bardziej odpowiednie do śledzenia obiektów, które mogą być dodawane/usuwane w pamięci. Wektory są bardziej odpowiednie, gdy chcemy uzyskać dostęp do elementu z dużego ilość pojedynczych sztuk.

Nie wiem, jak listy są zoptymalizowane, ale musisz wiedzieć, że jeśli chcesz mieć szybki dostęp do odczytu, powinieneś używać wektorów, ponieważ jak dobrze listy stl mocują, nie będzie tak szybko w dostępie do odczytu niż wektor.

Za każdym razem Iteratory nie mogą zostać unieważnione.

Zasadniczo wektor jest tablicą z automatycznym zarządzaniem pamięcią. Dane są sąsiadujące ze sobą 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 wiąże się z kopiowaniem niektórych danych, aby zrobić miejsce na nowe.

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

Wektory są na ogół najbardziej efektywne w czasie dostępu elementy oraz dodawanie lub usuwanie elementów z końca sekwencji. W przypadku operacji polegających na wstawianiu lub usuwaniu elementów w miejscach innych niż koniec, wykonują one gorsze działania niż deques i list oraz mają mniej spójnych iteratorów i odniesień niż listy.

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 użycia listy. Innym jest to, gdy nie chcesz, aby wektor ponownie rozdzielał się podczas przesuwania elementów. Może to być zarządzane przez inteligentne użycie reserve (), ale w niektórych przypadkach może być łatwiej lub bardziej wykonalne użycie listy.

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

Na przykład algorytm partycjonowania grafu może mieć stałą liczbę obiektów dzielonych rekurencyjnie między rosnącą liczbę kontenerów. Obiekty powinny być zainicjowane raz i zawsze pozostają w tych samych miejscach w pamięci. Znacznie szybciej jest zmienić ich kolejność przez ponowne połączenie niż przez ponowne przydzielenie.

Edit: ponieważ biblioteki przygotowują się do implementacji C++0x, ogólny przypadek splicingu a następstwo na liście staje się złożonością liniową wraz z długością ciągu. Dzieje się tak dlatego, że splice (now) musi iterację nad sekwencją, aby policzyć liczbę elementów w niej zawartych. (Ponieważ lista musi zapisać swój rozmiar.) Samo liczenie i ponowne łączenie listy jest nadal szybsze niż jakakolwiek alternatywa, a łączenie 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 splotu, być może będziesz musiał kopać w poszukiwaniu lepszego, staromodny, niezgodny z wymaganiami Pojemnik.

Jedyną twardą regułą, gdzie list musi być używana jest sytuacja, w której należy rozdzielać Wskaźniki na elementy kontenera.

W przeciwieństwie do vector, wiesz, że pamięć elementów nie zostanie ponownie przydzielona. Jeśli to możliwe, możesz mieć wskaźniki do nieużywanej pamięci, która w najlepszym przypadku jest wielkim Nie-Nie, a w najgorszym SEGFAULT.

(technicznie vector z *_ptr również by zadziałało, ale w takim przypadku emulujesz list więc to tylko semantyka.)

Inne miękkie zasady mają związek z możliwe problemy z wydajnością wstawiania elementów do środka kontenera, po czym list byłoby lepiej.