¿Cuál es la forma más efectiva de obtener el índice de un iterador de un std :: vector?

439

Estoy iterando sobre un vector y necesito el índice al que apunta el iterador actualmente. AFAIK esto se puede hacer de dos maneras:

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

¿Cuáles son los pros y los contras de estos métodos?

cairol
fuente

Respuestas:

558

Preferiría it - vec.begin()precisamente por la razón opuesta dada por Naveen: para que no compile si cambia el vector en una lista. Si hace esto durante cada iteración, podría terminar fácilmente 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 bucles.

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

TíoBens
fuente
3
Convenido. Diría que el signo menos es mejor, pero sería mejor mantener un segundo contador de bucles que usar std :: distance, precisamente porque esta función podría ser lenta.
Steven Sudit
28
¿cuál es el diablos it?
Steinfeld
32
@Steinfeld es un iterador. std::container_type::iterator it;
Matt Munson
2
Agregar un segundo contador de bucles es una solución tan obvia que me da vergüenza no haberlo pensado.
Mordred
3
@Swapnil porque std::listno ofrece acceso directo a los elementos por su posición, por lo que si no puede hacerlo list[5], no debería poder hacerlo list.begin() + 5.
José Tomás Tocino
135

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 usar en std::listlugar de std::vectorlo que no proporciona un iterador de acceso aleatorio, su código aún se compilará. Dado que std :: distance recoge el método óptimo dependiendo de los rasgos del iterador, tampoco tendrá ninguna degradación del rendimiento.

Naveen
fuente
50
Cuando usa un contenedor sin iteradores de acceso aleatorio, es mejor no calcular tales distancias porque es ineficiente
Eli Bendersky,
66
@Eli: Estoy de acuerdo con eso, pero en un caso muy especial si es realmente necesario, entonces ese código funcionará.
Naveen
99
Creo que el código debería cambiarse de todos modos si el contenedor cambia; tener una variable std :: list llamada veces una mala noticia. Si el código se reescribiera para que fuera genérico, tomando el tipo de contenedor como parámetro de plantilla, es cuando podemos (y debemos) hablar sobre el manejo de iteradores de acceso no aleatorio ;-)
Steve Jessop
1
Y especialización para ciertos contenedores.
ScaryAardvark
19
@SteveJessop: Tener un vector llamado también veces una muy mala noticia.
River Tam
74

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()toma tiempo constante, pero 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 de los dos es "mejor". Use el que hace lo que necesita.

jalf
fuente
1
He caído mal de esto en el pasado. Usando std :: distance en dos iteradores std :: map y esperando que sea O (N).
ScaryAardvark
66
@ScaryAardvark: ¿No te refieres a esperar que sea O (1)?
jalf
12

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í.

Eli Bendersky
fuente
19
Es más claro usar la resta para encontrar la distancia que usar, literalmente, la palabra distance?
Travis Gockel
44
@Travis, para mí lo es. Es una cuestión de gustos y costumbres. Decimos it++y no algo así std::increment(it), ¿no? ¿No sería eso también menos claro?
Eli Bendersky
3
El ++operador se define como parte de las secuencias STL como cómo incrementamos el iterador. std::distancecalcula el número de elementos entre el primer y el último elemento. El hecho de que el -operador funcione es simplemente una coincidencia.
Travis Gockel
3
@MSalters: y, sin embargo, usamos ++ :-)
Eli Bendersky
10

Si ya está restringido / codificado su algoritmo para usar solo std::vector::iteratory std::vector::iterator, 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 sustracción 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 desee 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 std::vector)

  • Si lo usa distance, su algoritmo admitirá una clase mucho más amplia de iteradores: iteradores de entrada.

Por supuesto, el cálculo distancepara iteradores de acceso no aleatorio es, en general, una operación ineficiente (mientras que, nuevamente, para los iteradores de acceso aleatorio es tan eficiente como la resta). Depende de usted decidir si su algoritmo tiene sentido para los 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 debería apegarse mejor 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 el rango utilizable, entonces debe usar distancey documentar el hecho de que el algoritmo funciona mejor con los iteradores de acceso aleatorio.

Hormiga
fuente
4

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

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

Stéphane
fuente
3

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

También creo que es mucho más común; sin embargo, no tengo números para probarlo. Argumento maestro: it - vec.begin()es más corto en 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 gustos, esto también puede ser un argumento válido.

Alexander Gessler
fuente
0

Aquí hay un ejemplo para encontrar "todas" las ocurrencias de 10 junto con el índice. Pensé que esto sería de alguna ayuda.

void _find_all_test()
{
    vector<int> ints;
    int val;
    while(cin >> val) ints.push_back(val);

    vector<int>::iterator it;
    it = ints.begin();
    int count = ints.size();
    do
    {
        it = find(it,ints.end(), 10);//assuming 10 as search element
        cout << *it << " found at index " << count -(ints.end() - it) << endl;
    }while(++it != ints.end()); 
}
Srikanth Batthula
fuente