Dlaczego nie ma operatora [] dla std :: list?

Question

Czy ktoś może wyjaśnić, dlaczego nie jest operator [] wdrożony dla std :: list? Szukałem trochę, ale nie znalazłem odpowiedzi. Nie byłoby to zbyt trudne do wdrożenia lub czegoś brakuje?

Answer 1

Odzyskiwanie element wskaźnikiem jest O (n) działanie na listę, na której znajduje się co std::list IS. Więc zdecydowano, że zapewnienie operator[] byłoby zwodnicze, ponieważ ludzie będą kuszeni, aby aktywnie wykorzystywać ją, a potem by zobaczyć kod jak:

std::list<int> xs; 
for (int i = 0; i < xs.size(); ++i) { 
    int x = xs[i]; 
    ... 
} 

który wynosi O (n^2) - bardzo nieprzyjemny. Tak więc standard ISO C++ wspomina, że ​​wszystkie sekwencje STL, które obsługują operator[], powinny robić to w zamortyzowanym stałym czasie (23.1.1 [lib.sequence.reqmts]/12), co jest możliwe dla vector i deque, ale nie list.

W przypadkach, w których rzeczywiście potrzebują tego rodzaju rzeczy, można użyć std::advance algorytmu:

int iter = xs.begin(); 
std::advance(iter, i); 
int x = *iter; 

Answer 2

To nie byłoby zbyt trudne (dla realizatora), ale byłoby to zbyt trudne w czasie wykonywania, ponieważ wydajność będzie straszny w większości przypadków. Zmuszenie użytkownika do przejścia przez każdy link sprawi, że będzie bardziej oczywiste, co się tam dzieje, niż "myList [102452]".

Answer 3

Myślę, że znalazłem odpowiedź w innym SO zakładać Extending std::list

„swojego operatora [] to czas O (N) "- to właśnie dlatego jest niewpisane w standardzie std :: list <>. - Michael Burr 14 grudnia o 17:29

Ale czy to jedyny powód?

EDIT: Wydaje się jednak, jak ludzie wspomniano jest to bardziej kwestia spójności w zakresie wydajności następnie ściśle wydajności.

Answer 4

Faktycznie, nie ma absolutnie żadnego powodu, aby nie dostarczyć operator [] lub przynajmniej sposób na (int), ponieważ z dwóch powodów:

• Jest podwójna lista powiązane, więc trzeba się poruszać z prędkością większość size()/2 umieszcza twój iterator w celu uzyskania indeksu, a koszty wewnętrznego utrzymywania kilku kolejnych stałych iteratorów są bardzo niskie. I na koniec biblioteka Qt dostarcza operatorowi [] i at, i nie widzę kosztów wydajności z niego korzystających.
• zmuszanie ludzi coś nie do wykorzystania jest bardzo złe programowanie nawyk, bo lista będzie znacznie użyteczny pojemnik, jeśli masz „swobodnego dostępu” w pobliżu połączonego dostępu, istnieje przykłady odmiany, gdy trzeba mieć dostęp, w zależności na który punkt kontrolny.