Taka randomowa rozkmina mnie naszła a nie mogę znaleźć odpowiedzi nigdzie na stacku i w ogóle we internetach.
Mianowicie chodzi mi o pojedynek std::vector vs std::list.
Vector ma ciągły obszar pamięci, więc on sobie po prostu alokuje kolejne tablice i przepisuje w trakcie działania. Dramat przy dodawaniu dużej liczby elementów, ale przy odczycie będzie spoko.
Lista to totalny pamięciowy burdel dodający elementy pojedynczo i gdzie popadnie, gdzie tylko jest miejsce. Nie możemy jej przeglądać dowolnie, bo obszar jest nieciągły. Wynika z tego, że każdy kolejny element listy powinien posiadać wskaźnik na element następny i element poprzedni, bo możemy przecież iterować od przodu i od tyłu. Ale to oznacza dodanie do każdej wartości przechowywanej dwóch wartości long long int, które mają aż 64 bity. Czy to nie oznacza, że lista może przy przechowywaniu tej samej ilości danych zajmować nawet kilka razy tyle pamięci co vector przez przechowywanie samych wskaźników na kolejne elementy?
@Khaine: Jeżeli lista jest typów prymitywnych to nie ma dużej korzyści, ale zazwyczaj są to listy jakichś obiektów. Wtedy w odpowiednim użyciu potężne narzędzie.
@Khaine: Może. Taka już specyfika listy. Do zalet pamięci ciągłej (vector) dodaj jeszcze cache-friendly. Lista to koszmar dla pamięci podręcznej CPU co dodatkowo spowalnia iterowanie po jej elementach w stosunku do vectora.
@SirSajko: Mi tylko chodzi o to, czy mam rację, że lista przechowująca np. chary z punktu widzenia pamięci jest jedną z najgłupszych rzeczy jakie można zrobić. To, że obiekty mogą być bardzo duże i przy nich te dodatkowe wskaźniki są pomijalnie małe to wiadomo sprawa.
@Khaine: jeśli chodzi o szybkość kodu, to bardzo dużo zależy od lokalności danych obecnie (dla x86 i nowych ARM-ów przynajmniej). Wydaje się więc, że std::vector będzie zawsze lepszą opcją, ale nie jest tak w praktyce. Często nie można sobie pozwolić na alokację dużego kawałku ciągłej pamięci, albo na trzymanie go z dala innych danych. Dlatego powstają klasy takie jak SmallVector.
Taka ciekawostka: backend kompilatora vistual c++ korzysta praktycznie wszędzie z linked
@Khaine: Lista jest do innych zastosowań i vector do innych. Czas się tego nauczyć, by wiedzieć po co jest i kiedy bardziej opłaci się używać jednego, a kiedy drugiego typu danych. I tyle. Są jeszcze inne typy do jeszcze innych celów, odkryjesz zapewne niedługo mapę, a może też listę tablic.... Czas się nauczyć, że w zależności od potrzeb używa się rożnych typów danych.
@Kaczus2B: Bardzo pomocny i duzo wnoszacy komentarz. A wiesz, ze widelec jest do innych zastosowan, a lyzka do innych. Czas sie tego nauczyc, by wiedziec po co jest i kiedy bardziej oplaci sie uzywac jednego, a kiedy drugiego?
@Khaine: Jezeli wiesz jak duzo chcesz dodac elementow to zawsze sie rezerwuje pamiec dla vektora i nie ma problemu z realokacja pamieci. Z reszta dramatu bez wstepnej rezerwacji (alokacji) pamieci tez nie ma.
moja profesjonalna opinia kulinarna jest taka że kuchnia azjatycka jest najlepsza na świecie nie ma o czym dyskutować kuchnia włoska jest taka se ale i tak lepsza od polskiej bo polska kuchnia jest najgorsza
Taka randomowa rozkmina mnie naszła a nie mogę znaleźć odpowiedzi nigdzie na stacku i w ogóle we internetach.
Mianowicie chodzi mi o pojedynek std::vector vs std::list.
Vector ma ciągły obszar pamięci, więc on sobie po prostu alokuje kolejne tablice i przepisuje w trakcie działania. Dramat przy dodawaniu dużej liczby elementów, ale przy odczycie będzie spoko.
Lista to totalny pamięciowy burdel dodający elementy pojedynczo i gdzie popadnie, gdzie tylko jest miejsce. Nie możemy jej przeglądać dowolnie, bo obszar jest nieciągły. Wynika z tego, że każdy kolejny element listy powinien posiadać wskaźnik na element następny i element poprzedni, bo możemy przecież iterować od przodu i od tyłu. Ale to oznacza dodanie do każdej wartości przechowywanej dwóch wartości long long int, które mają aż 64 bity. Czy to nie oznacza, że lista może przy przechowywaniu tej samej ilości danych zajmować nawet kilka razy tyle pamięci co vector przez przechowywanie samych wskaźników na kolejne elementy?
gdzie Listnodebase to
Czyli dwa pointery i dane.
std::vectorbędzie zawsze lepszą opcją, ale nie jest tak w praktyce. Często nie można sobie pozwolić na alokację dużego kawałku ciągłej pamięci, albo na trzymanie go z dala innych danych. Dlatego powstają klasy takie jak SmallVector.Taka ciekawostka: backend kompilatora vistual c++ korzysta praktycznie wszędzie z linked