¿Cómo obtengo el índice de un iterador de un std::vector?

6 minutos de lectura

avatar de usuario
El Cairo

Estoy iterando sobre un vector y necesito el índice al que apunta actualmente el iterador. ¿Cuáles son los pros y los contras de los siguientes métodos?

  • it - vec.begin()
  • std::distance(vec.begin(), it)

avatar de usuario
tíobens

Yo preferiría it - vec.begin() precisamente por la razón opuesta dada por Naveen: por lo que no lo haría compile si cambia el vector a una lista. Si hace esto durante cada iteración, fácilmente podría terminar convirtiendo un algoritmo O(n) en un algoritmo O(n^2).

Otra opción, si no salta en el contenedor durante la iteración, sería mantener el índice como un segundo contador de bucle.

Nota: it es un nombre común para un iterador de contenedor,std::container_type::iterator it;.

  • Acordado. Diría que el signo menos es mejor, pero sería mejor mantener un segundo contador de bucle que usar std::distance, precisamente porque esta función podría ser lenta.

    – Steven Sudit

    4 de febrero de 2010 a las 19:41

  • @Steinfeld es un iterador. std::container_type::iterator it;

    – Matt Munson

    6 de julio de 2014 a las 16:33

  • Agregar un segundo contador de bucle es una solución tan obvia que me da vergüenza no haberlo pensado.

    – Mordred

    19 de diciembre de 2017 a las 23:24

  • @UncleBeans ¿Por qué no podemos usar el operador – para List?

    – Swapnil

    22 de septiembre de 2018 a las 13:43

  • @Swapnil porque std::list no ofrece acceso directo a los elementos por su posición, por lo que si no puede hacerlo list[5]no deberías poder hacer list.begin() + 5.

    –José Tomás Tocino

    5 de noviembre de 2018 a las 10:50


Yo preferiría std::distance(vec.begin(), it) ya que me permitirá cambiar el contenedor sin ningún cambio de código. Por ejemplo, si decide utilizar std::list en vez de std::vector que no proporciona un iterador de acceso aleatorio, su código aún se compilará. Dado que std::distance elige el método óptimo según los rasgos del iterador, tampoco tendrá ninguna degradación del rendimiento.

  • Cuando usa un contenedor sin iteradores de acceso aleatorio, es mejor No a calcular tales distancias porque es ineficiente

    – Eli Bendersky

    28 de enero de 2010 a las 7:47

  • @Eli: Estoy de acuerdo con eso, pero en un caso muy especial, si realmente es necesario, ese código seguirá funcionando.

    – Naveen

    28 de enero de 2010 a las 9:38

  • Creo que el código debería cambiarse de todos modos si el contenedor cambia, teniendo una variable std::list nombrada vec son malas noticias Si el código se reescribiera para que fuera genérico, tomando el tipo de contenedor como un parámetro de plantilla, ahí es cuando podemos (y debemos) hablar sobre el manejo de iteradores de acceso no aleatorio 😉

    –Steve Jessop

    28 de enero de 2010 a las 12:50


  • Y especialización para determinados contenedores.

    – ScaryAardvark

    2 de febrero de 2010 a las 16:39

  • @SteveJessop: tener un vector llamado vec también es una muy mala noticia.

    – Río Tam

    25 de junio de 2014 a las 17:42

Como han demostrado UncleBens y Naveen, hay buenas razones para ambos. Cuál es “mejor” depende del comportamiento que desee: ¿Desea garantizar un comportamiento de tiempo constante o desea que vuelva al tiempo lineal cuando sea necesario?

it - vec.begin() lleva un tiempo constante, pero el operator - solo se define en iteradores de acceso aleatorio, por lo que el código no se compilará en absoluto con iteradores de lista, por ejemplo.

std::distance(vec.begin(), it) funciona para todos los tipos de iteradores, pero solo será una operación de tiempo constante si se usa en iteradores de acceso aleatorio.

Ninguno es “mejor”. Usa el que hace lo que necesitas.

  • He fallado en esto en el pasado. Usar std::distance en dos iteradores std::map y esperar que sea O(N).

    – ScaryAardvark

    2 de febrero de 2010 a las 16:38


  • @ScaryAardvark: ¿No te refieres a esperar que sea O(1)?

    – jalf

    2 de febrero de 2010 a las 17:07


Me gusta este: it - vec.begin(), porque para mí dice claramente “distancia desde el principio”. Con los iteradores estamos acostumbrados a pensar en términos de aritmética, por lo que el - signo es el indicador más claro aquí.

avatar de usuario
AnT apoya a Rusia

Si ya está restringido/codificado de forma rígida su algoritmo para usar un std::vector::iterator y std::vector::iterator solo que realmente no importa qué método terminará usando. Su algoritmo ya está concretado más allá del punto en el que elegir uno de los otros puede marcar la diferencia. Ambos hacen exactamente lo mismo. Es solo una cuestión de preferencia personal. Yo personalmente usaría la resta explícita.

Si, por otro lado, desea conservar un mayor grado de generalidad en su algoritmo, es decir, para permitir la posibilidad de que algún día en el futuro pueda aplicarse a algún otro tipo de iterador, entonces el mejor método depende de su intención. . Depende de cuán restrictivo quiera ser con respecto al tipo de iterador que se puede usar aquí.

  • Si usa la resta explícita, su algoritmo estará restringido a una clase bastante limitada de iteradores: iteradores de acceso aleatorio. (Esto es lo que obtienes ahora de std::vector)

  • Si utiliza distancesu algoritmo admitirá una clase mucho más amplia de iteradores: iteradores de entrada.

Por supuesto, calculando distance para los iteradores de acceso no aleatorio es, en general, una operación ineficiente (mientras que, de nuevo, para los de acceso aleatorio es tan eficiente como la resta). Depende de usted decidir si su algoritmo tiene sentido para iteradores de acceso no aleatorio, en términos de eficiencia. Si la pérdida de eficiencia resultante es devastadora hasta el punto de hacer que su algoritmo sea completamente inútil, entonces es mejor que se ciña a la resta, prohibiendo así los usos ineficientes y obligando al usuario a buscar soluciones alternativas para otros tipos de iteradores. Si la eficiencia con los iteradores de acceso no aleatorio todavía está en un rango utilizable, entonces debe usar distance y documentar el hecho de que el algoritmo funciona mejor con iteradores de acceso aleatorio.

avatar de usuario
Stéphane

De acuerdo a http://www.cplusplus.com/reference/std/iterator/distance/ya que vec.begin() es un acceso aleatorio iterador, el método de distancia utiliza el - operador.

Entonces, la respuesta es, desde el punto de vista del rendimiento, es lo mismo, pero tal vez usando distance() es más fácil de entender si alguien tuviera que leer y entender su código.

avatar de usuario
Alejandro Gessler

usaría el - variante para std::vector solo: está bastante claro lo que significa, y la simplicidad de la operación (que no es más que una resta de puntero) se expresa mediante la sintaxis (distance, por otro lado, suena como Pitágoras en la primera lectura, ¿no?). Como señala UncleBen, - también actúa como una afirmación estática en caso vector se cambia accidentalmente a list.

También creo que es mucho más común; sin embargo, no tengo números que lo demuestren. Argumento maestro: it - vec.begin() es más corto en el código fuente: menos trabajo de tipeo, menos espacio consumido. Como está claro que la respuesta correcta a su pregunta se reduce a una cuestión de gusto, esto puede además ser un argumento válido.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad