c++ - sirve - sobrecarga de operadores relacionales

¿Por qué no hay un operador[] para una lista std::?

Question

¿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?

Answer 1

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 2

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<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 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;

Answer 3

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

• Es una lista de doble enlace, por lo que debe mover a lo más size () / 2 coloca su iterador para obtener su índice, y los costos para mantener internamente pocos iteradores fijos 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á mucho más útil, si tienes un "acceso aleatorio" cerca del acceso vinculado, hay una variedad de ejemplos cuando necesitas ambos accesos, dependiendo de en qué punto de tiempo de ejecución .

Answer 4

Creo que encontré la respuesta en otro mensaje 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.