Há algum tempo, portei alguns contêineres de biblioteca padrão C++ para um ambiente onde a biblioteca padrão não estava disponível. Embora iteradores para contêineres contíguos e baseados em nós fossem fáceis, fiquei sem saber como implementar um iterador unordered_mapsem armazenar uma referência ao mapa ou ao enditerador.
O problema principal era operator++, que tem que pular baldes vazios sem ao mesmo tempo estourar o buffer subjacente:
AB_C_
^ ++
^ non-empty, done
AB_C_
^ ++
^ empty, move over
^ non-empty, done
AB_C_
^ ++
^ empty, move over
^overrun, how can it know to stop?
Isso pressupõe que você pode determinar se um bucket está vazio apenas por um ponteiro para ele, o que pode não ser o caso se unordered_mapusar um bitset separado para otimizar o espaço (fazendo com que o bucket { bool, Key, Value }desperdice alignof(Key) - 1bits).
Acabei desistindo e criei o iterador { bucket*, unordered_map& }, para que ele operator++possa chamar bucket* unordered_map::get_next_occupied_bucket(bucket*), já que o mapa sabe quais baldes estão vazios e quantos deles existem. Tive problemas semelhantes ao tentar implementar filter_view, mas também não encontrei uma boa solução para isso.
Como os fornecedores de bibliotecas padrão (e outros implementadores) tendem a superar esse problema? O exemplo acima usa endereçamento aberto, mas me parece que o encadeamento incorrerá no mesmo problema, já que o contêiner superior ainda é um array com alguns elementos ausentes.
O principal motivo pelo qual não quero armazenar referências é que isso parece pouco elegante e ingênuo, a exemplo de implementar std::vector::iteratorcomo { vector&, size_t index }, sugerindo que deveria existir uma solução melhor.
Você perguntou como isso
std::unordered_map::iteratorpoderia ser implementado sem referenciar o mapa subjacente. No entanto,std::unordered_mapnão utiliza endereçamento aberto — é baseado em encadeamento separado.Na sua pergunta, você forneceu um diagrama baseado no endereçamento aberto e então perguntou como o encadeamento separado
std::unordered_maplida com esse problema.Para entender melhor como
std::unordered_mapé implementado, recomendo ler atentamente o seguinte artigo mais algumas vezes:Dentro do STL: O unordered_map, unordered_set, unordered_multimap e unordered_multiset
Considerando que seu diagrama usa endereçamento aberto, presumo que o unordered_map que você está implementando também seja baseado em endereçamento aberto. Infelizmente, não estou familiarizado com a implementação de iteradores para unordered_map baseado em endereçamento aberto.
Já que você escolheu usar endereçamento aberto, imagino que não esteja seguindo rigorosamente a garantia do padrão, que
std::unordered_map::iteratornunca deve ser invalidada ao inserir ou refazer.Dito isso, deixe-me compartilhar como implementei meu próprio unordered_set.
O contêiner que criei é um hash_set baseado em encadeamento separado, com buffer único.
Todos os elementos são armazenados em um único conjunto
std::vector, que efetivamente representa várias listas encadeadas.Cada nó no vetor contém o índice do próximo nó na cadeia, ou
-1se for o fim da cadeia.Cada bucket armazena o índice do primeiro nó em sua cadeia correspondente, ou
-1se o bucket estiver vazio.Quando procuro um elemento, calculo seu hash para encontrar o intervalo apropriado e, então, sigo a cadeia usando os índices armazenados.
Ao iterar, não me importo com a ordem ou o intervalo — simplesmente itero de vector.begin() para vector.end().
Ao remover um elemento, movo o último elemento do vetor para a posição do elemento removido para manter a continuidade.
Você pode encontrar minha
single_buffer_hash_setimplementação aqui: https://github.com/JamilHsu/single_buffer_hash_setAviso:
Este é um conjunto, não um mapa, pois ainda não implementei a versão do mapa.
Não sou programador profissional, então não posso garantir que esteja livre de bugs.
A maioria dos comentários está em chinês, mas como a estrutura é simples, você pode inserir o código-fonte inteiro no ChatGPT e pedir que ele explique como funciona.