C++ get index of element of array por valor

Question

Hasta ahora, he estado almacenando la matriz en un vector y luego recorriendo el vector para encontrar el elemento correspondiente y luego devolver el índice.

¿Hay alguna manera más rápida de hacerlo en C++? La estructura STL que uso para almacenar la matriz realmente no me importa (no tiene que ser un vector). Mi matriz también es única (sin elementos repetitivos) y ordenada (por ejemplo, una lista de fechas en el tiempo).

Answer 1

Como los elementos están ordenados, puede usar una búsqueda binaria para encontrar el elemento coincidente. La biblioteca estándar de C++ tiene un algoritmo std::lower_bound que se puede usar para este propósito. Yo recomendaría envolviéndolo en su propio algoritmo de búsqueda binaria, para mayor claridad y simplicidad:

/// Performs a binary search for an element 
/// 
/// The range `[first, last)` must be ordered via `comparer`. If `value` is 
/// found in the range, an iterator to the first element comparing equal to 
/// `value` will be returned; if `value` is not found in the range, `last` is 
/// returned. 
template <typename RandomAccessIterator, typename Value, typename Comparer> 
auto binary_search(RandomAccessIterator const first, 
        RandomAccessIterator const last, 
        Value    const& value, 
        Comparer     comparer) -> RandomAccessIterator 
{ 
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer)); 
    if (it == last || comparer(*it, value) || comparer(value, *it)) 
     return last; 

    return it; 
} 

(La ++ Biblioteca C estándar tiene un std::binary_search, pero devuelve un bool: true si el rango contiene el elemento, false lo contrario. No es útil si desea un iterador para el elemento.)

Una vez que tiene un iterador para el elemento, puede usar el algoritmo std::distance para calcular el índice del elemento en el rango.

Ambos algoritmos funcionan igual de bien que cualquier secuencia de acceso aleatorio, incluidos std::vector y arrays ordinarios.

Answer 2

Si desea asociar un valor con un índice y encontrar el índice rápidamente, puede usar std::map o std::unordered_map. También puede combinarlos con otras estructuras de datos (por ejemplo, std::list o std::vector) dependiendo de las otras operaciones que desee realizar en los datos.

Por ejemplo, al crear el vector también creamos una tabla de búsqueda:

vector<int> test(test_size); 
unordered_map<int, size_t> lookup; 
int value = 0; 
for(size_t index = 0; index < test_size; ++index) 
{ 
    test[index] = value; 
    lookup[value] = index; 
    value += rand()%100+1; 
} 

ahora para buscar el índice simplemente:

size_t index = lookup[find_value]; 

El uso de una estructura de datos basada en la tabla hash (por ejemplo, the unordered_map) es una compensación de espacio/tiempo bastante clásica y puede superar la realización de una búsqueda binaria para este tipo de operación de búsqueda "inversa" cuando necesite hacer muchas búsquedas. La otra ventaja es que también funciona cuando el vector no está ordenado.

Para la diversión :-) He hecho una referencia rápida en comparación VS2012RC código binario de búsqueda de James con una búsqueda lineal y con el uso de unordered_map para la búsqueda, todo en un vector:

A ~ 50000 elementos unordered_set significativamente (x3-4) supera la búsqueda binaria que exhibe el comportamiento esperado O (log N), el resultado algo sorprendente es que unordered_map pierde su comportamiento O (1) más allá de 10000 elementos, presumiblemente debido a colisiones hash, tal vez una implementación problema.

EDITAR: max_load_factor() para el mapa desordenado es 1 por lo que no debería haber colisiones. La diferencia en el rendimiento entre la búsqueda binaria y la tabla hash para vectores muy grandes parece estar relacionada con el almacenamiento en caché y varía según el patrón de búsqueda en el punto de referencia.

Choosing between std::map and std::unordered_map habla de la diferencia entre los mapas ordenados y desordenados.