¿Por qué no hay un operador [] para una lista estándar?

Question

¿Alguien puede explicar por qué el operador [] no está implementado para una lista std ::? He buscado un poco pero no he encontrado una respuesta. No sería muy difícil de implementar o me estoy perdiendo algo?

Answer 1

Recuperar un elemento por índice es una operación O (n) para la lista vinculada, que es lo que std::list es. Por lo tanto, se decidió que sería proporcionar operator[] engañosa, ya que las personas se verían tentados a utilizar activamente, y luego se vería código como:

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

que es O (n^2) - muy desagradable. Por lo tanto, el estándar ISO C++ menciona específicamente que todas las secuencias STL que admiten operator[] deben hacerlo en tiempo constante amortizado (23.1.1 [lib.sequence.reqmts]/12), que se puede alcanzar para vector y deque, pero no list.

Para los casos en que realmente necesita ese tipo de cosas, puede utilizar std::advance algoritmo:

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

Answer 2

No sería demasiado difícil (para el implementador) pero sería demasiado difícil en tiempo de ejecución, ya que el rendimiento será terrible en la mayoría de los casos. Obligar al usuario a ir a través de cada enlace hará que sea más obvio lo que está sucediendo ahí que 'myList [102452]' lo haría.

Answer 3

Creo que he encontrado la respuesta en otro SO publicar Extending std::list

"su operador [] es O (N) time "- este es exactamente el motivo por el cual no está incluido en estándar del estándar <>. - Michael Burr 14 de diciembre a las 17:29

Aún así, ¿es esa la única razón?

EDITAR: Parece que, como las personas lo mencionaron, es más una cuestión de consistencia con respecto al rendimiento que estrictamente al rendimiento.

Answer 4

En realidad, no hay absolutamente ninguna razón para no proporcionar el operador [] o, al menos, método al (int), debido a las dos razones:

• Es lista doblemente enlazada, por lo que necesita para moverse en la mayoría del tamaño()/2 coloca su iterador para obtener su índice, y los costos para mantener internamente pocos iteradores fijos más son muy bajos. Y al final, la biblioteca de Qt proporciona el operador [] y el at, y no veo el costo de rendimiento al usarlo.
• obligar a las personas a no usar es un hábito de programación muy malo, porque una lista será un contenedor muy útil, si tiene un "acceso aleatorio" cerca del acceso vinculado, hay una variedad de ejemplos cuando necesita ambos accesos, dependiendo de qué punto de tiempo de ejecución.