Lista C ++ com localização rápida

Question

Estou trabalhando com um std::list.

Os elementos aparecem na "ordem de inserção" na lista, não de acordo com o valor de um elemento.

Ao std::find()-ing um elemento, toda a lista deve ser pesquisada.

A fim de acelerar "encontrar" de O (n) para O (log (n)), eu poderia implementar um mapa de hash para armazenar as std::listposições dos elementos, ou poderia usar Índices Multi boost,https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Pergunta: Hoje, com o C ++ 17, existe uma maneira padrão / comum ou prática recomendada de implementar um contêiner que tem todas as propriedades de uma lista MAIS rápido find(e, por exemplo. remove)? Ou esse tipo de contêiner já existe? C ++ 20 talvez?

Edit / Nb: A ordem dos elementos na lista é relevante e, portanto, um std :: map não pode ser usado diretamente.

Answer 1

Uma vez que os iteradores para a std::listpermanecem válidos em inserções e exclusões (exceto para o elemento que você excluiu, é claro), você poderia manter uma estrutura de dados secundária do tipo std::map <my_key, my_list_iterator>(ou a std::unordered_mapse for mais adequado).

Então, sempre que você adicionar ou excluir uma entrada da lista, faça o mesmo com o seu std::map / unordered_mape pronto. Você pode, é claro, pesquisar isso com complexidade O (log (n)) (ou O (1)).

Answer 2

Guia muito curto e compreensível (baseado em um único exemplo) sobre como implementar um contêiner com os recursos desejados usando Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

É mais prático, para mim, mais fácil de entender, do que o estilo mais formal https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupque cobre todos os usos possíveis (embora também use exemplos).

Answer 3

Uma implementação parcial e MUITO primitiva (protótipo) da presente resposta 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);
}

demo: https://godbolt.org/z/jdnvdM

Entre muitas outras coisas, este protótipo está faltando métodos de iterador para implementar um contêiner personalizado, informações sobre isso aqui: Como implementar um iterador de estilo STL e evitar armadilhas comuns? .

(Editar: Ted Lyngmo em seu comentário abaixo fornece uma versão melhor aqui: https://godbolt.org/z/6xfbq7)

Seria realmente legal se esse tipo de recipiente fosse fornecido fora da caixa. Bem como outros contêineres que são modelados / derivados de outros mais fundamentais, mas adicionam vantagens de desempenho específicas que refletem situações de uso específicas. Se alguém souber de alguma biblioteca que ofereça esse tipo de contêineres especializados, diga ;-)