Lista de C ++ con búsqueda rápida

Question

Estoy trabajando con a std::list.

Los elementos aparecen en "orden de inserción" en la lista, no según el valor de un elemento.

Al seleccionar std::find()un elemento, se debe buscar en toda la lista.

Para acelerar la "búsqueda" de O (n) a O (log (n)), podría implementar un mapa hash para almacenar las std::listposiciones de los elementos, o podría usar boost Multi Indexes,https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Pregunta: Hoy en día, con C ++ 17, ¿existe una forma estándar / común o de mejores prácticas de implementar un contenedor que tiene todas las propiedades de una lista MÁS rápido find(y, por ejemplo remove)? ¿O ya existe un tipo de contenedor de este tipo? ¿C ++ 20 quizás?

Editar / Nb: El orden de los elementos en la lista es relevante y, por lo tanto, no se puede usar un std :: map directamente.

Answer 1

Dado que los iteradores de a std::listsiguen siendo válidos en las inserciones y eliminaciones (a excepción del elemento que eliminó, por supuesto), puede mantener una estructura de datos de segundo tipo std::map <my_key, my_list_iterator>(o a std::unordered_mapsi es más adecuado).

Luego, cada vez que agregue o elimine una entrada de la lista, haga lo mismo con la suya std::map / unordered_mapy listo. Por supuesto, puede buscar eso con O (log (n)) (o O (1)) complejidad.

Answer 2

Guía muy breve y comprensible (basada en un solo ejemplo) sobre cómo implementar un contenedor con las capacidades deseadas usando Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

Para mí, es más práctico, más fácil de entender, que el estilo más formal. https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupque cubre todos los usos posibles (aunque también utiliza ejemplos).

Answer 3

Una implementación parcial y MUY primitiva (prototipo) de la presente respuesta https://stackoverflow.com/a/64539693/11608725 (por Paul Sanders):

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

manifestación: https://godbolt.org/z/jdnvdM

Entre muchas otras cosas, a este prototipo le faltan métodos de iterador para implementar un contenedor personalizado, información sobre esto aquí: ¿Cómo implementar un iterador de estilo STL y evitar errores comunes? .

(Editar: Ted Lyngmo en su comentario a continuación proporciona una mejor versión aquí: https://godbolt.org/z/6xfbq7).

Realmente sería genial si este tipo de contenedor se proporcionara fuera de la caja. Así como otros contenedores que se modelan / derivan de otros más fundamentales, pero agregan ventajas de rendimiento específicas que reflejan situaciones de uso específicas. Si alguien sabe de alguna biblioteca que proporcione ese tipo de contenedores especializados, dígaselo ;-)