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

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?

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

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.

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.

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

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.

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.

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.

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()); 
}