Lista, a indeksy C++

Question

Cześć mam zaimplementowaną swoją listę , no i ogólnie nie da się odwoływać do poszczególnych jej elementów przez indeksy jak w zwykłej tablicy , a chciałbym móc tak robić(np. jak w vektorze się da). np. lista[4].dane.
Macie może artykuł do tego jak to zrobić ewentualnie podrzucić mi pomysł, jeśli dobrze myślę to trzeba przeciążyć operator [] , dzięki za odpowiedź z góry.

Answer 1

Jak chcesz mieć dostęp do danych o średniej złożoności czasowej O(1) to zaimplementuj vector a nie baw się w listę. Lista zapewnia złożoność czasową O(N) w średnim przypadku. Morał jest taki, że lista to właśnie taka struktura danych, że aby dobrać się do elementu i musisz przejść po całej liście od początku aż do elementu i. Idea tej struktury nie pozwala aby odnosić się do niej za pomocą indeksu po w takim razie po co by ktoś się bawił w implementacje i listy i vectora w języku C++ skoro i tak to byłoby de facto to samo.
Poczytaj coś o podstawowych strukturach danych w internecie a na pewno wszystko lepiej Ci to wyjaśni.
Pozdrawiam.

Answer 2

Kontener list jest listą podwójnie związaną. Przechodzenie po liście w obu kierunkach umożliwia to, że każdy element oprócz pierwszego i ostatniego jest związany z sąsiadującymi z nim elementami. Jest zasadnicza różnica między list a vector - w kontenerze list możesz wstawić element w dowolnym miejscu i wielkość kontenera powiększy się automatycznie. Podobnie w drugą stronę z usuwaniem elementów listy. Zaś w kontenerze vector możesz wstawiać i usuwać tylko ostatni element, odpowiednio za pomocą metod push_back() oraz pop_back().

Podsumowując: kontenery te mają inne właściwości - vector umożliwia dostęp swobodny do elementów, zaś list umożliwia wstawianie i usuwanie elementów w dowolne miejsca. Należy dostosować typ kontenera do tego, co się chce zrobić w programie.