¿Alguien puede explicar por qué el operador [] no está implementado para una std :: list? He buscado un poco pero no he encontrado una respuesta. No sería muy difícil de implementar o me estoy perdiendo algo?
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 proporcionar operator[]
sería engañoso, ya que las personas estarían tentadas a usarlo activamente, y luego vería código como:
std::list 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 soportan operator[]
deberían hacerlo en tiempo constante amortizado (23.1.1 [lib.sequence.reqmts] / 12), lo cual es posible para vector
y deque
, pero no para list
.
Para casos en los que realmente necesite ese tipo de cosas, puede usar el algoritmo std::advance
:
int iter = xs.begin(); std::advance(iter, i); int x = *iter;
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.
Creo que encontré la respuesta en otra publicación SO Extendiendo std :: list
“su operador [] es O (N) tiempo” – esta es exactamente la razón por la cual no está incluido en la lista std :: list <> 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 a un rendimiento estricto.
En realidad, no hay absolutamente ninguna razón para no proporcionar operador [] o al menos método en (int), debido a las dos razones: