Warum gibt es keinen Operator[] für eine std::list?

Question

Kann jemand erklären, warum der Operator[] nicht für eine std::list implementiert ist? Ich habe ein bisschen herumgesucht, aber keine Antwort gefunden. Es wäre nicht zu schwer zu implementieren oder übersehe ich etwas?

Answer 1

Das Abrufen eines Elements nach Index ist eine O(n)-Operation für eine verknüpfte Liste, was bedeutet, dass std::list ist. Es wurde also beschlossen, dass die Bereitstellung operator[] wäre trügerisch, da die Leute versucht wären, es aktiv zu nutzen, und dann würde man Code wie diesen sehen:

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

was O(n^2) ist - sehr unangenehm. Der ISO C++-Standard sieht daher ausdrücklich vor, dass alle STL-Sequenzen, die operator[] sollte dies in amortisierter konstanter Zeit (23.1.1[lib.sequence.reqmts]/12) geschehen, was für vector y deque , aber nicht list .

Für Fälle, in denen Sie so etwas tatsächlich brauchen, können Sie std::advance Algorithmus:

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

Answer 2

Es wäre nicht zu schwer (für den Implementierer), aber es wäre zu schwer zur Laufzeit, da die Leistung in den meisten Fällen schrecklich sein wird. Wenn der Benutzer gezwungen wird, jeden Link durchzugehen, wird es offensichtlicher, was dort vor sich geht, als wenn "myList[102452]" angezeigt wird.

Answer 3

Ich glaube, ich habe die Antwort in einem anderen SO-Beitrag gefunden Erweitern von std::list

"Ihr Operator[] benötigt O(N)-Zeit" - dies ist genau der Grund, warum er nicht in std::list<> des Standards nicht enthalten. - Michael Grat 14. Dez um 17:29

Doch ist das der einzige Grund?

EDIT : Wie bereits erwähnt, scheint es eher eine Frage der Konsistenz in Bezug auf die Leistung als der reinen Leistung zu sein.

Answer 4

Eigentlich gibt es absolut keinen Grund, nicht operator[] oder zumindest die Methode at(int) anzubieten, und zwar aus zwei Gründen:

• Es handelt sich um eine doppelt verknüpfte Liste, so dass Sie höchstens size()/2 Stellen Ihres Iterators verschieben müssen, um Ihren Index zu erhalten, und die Kosten für die interne Speicherung einiger weiterer fester Iteratoren sind sehr gering. Und am Ende, die Qt-Bibliothek bietet den Operator[] und die at, und ich sehe nicht Leistung Kosten mit ihm.
• zwingen die Menschen etwas nicht zu verwenden, ist eine sehr schlechte Programmierung Gewohnheit, weil eine Liste wird viel nutzbar Container, wenn Sie eine "Random Access" in der Nähe der verknüpften Zugriff haben, gibt es eine Vielzahl von Beispielen, wenn Sie beide Zugriff benötigen, je nachdem, zu welchem Zeitpunkt der Laufzeit Punkt.