std :: map inserção ou std :: mapa?

Question

Assumindo um mapa onde você quiser preservar as entradas existentes. 20% do tempo, a entrada que está a inserir novos dados. Existe uma vantagem de fazer std :: map :: find então std :: map :: insert usando que voltou iterador? Ou é mais rápido para tentar a inserção e, em seguida, agir com base em se ou não o iterador indica que o registro foi ou não foi inserido?

Answer 1

A resposta é que você faz não. Em vez disso você quer fazer algo sugerido pelo ponto 24 da Effective STL por Scott Meyers :

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Answer 2

A resposta a esta questão depende também de como é caro para criar o tipo de valor que você está armazenando no mapa:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Para um tipo de valor, tal como um inteiro, a vontade acima mais eficiente do que um encontrar seguido por uma inserção (na ausência de optimizações do compilador). Como dito acima, isso é porque a pesquisa através do mapa só ocorre uma vez.

No entanto, a chamada para inserção requer que você já tem o novo "valor" construída:

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

De forma a chamada 'inserção' estamos a pagar a chamada caros para construir o nosso tipo de valor - e pelo que você disse na pergunta que você não vai usar esse novo valor de 20% do tempo. No caso acima, se mudar o tipo de valor mapa não é uma opção, então é mais eficiente para o primeiro executar a 'encontrar' para verificar se precisamos para construir o elemento.

Como alternativa, o tipo de valor do mapa pode ser alterado para armazenar alças para os dados usando o seu tipo de ponteiro inteligente favorito. A chamada para inserção usa um ponteiro nulo (muito barato para construção) e apenas se necessário é o novo tipo de dados construída.

Answer 3

Haverá mal qualquer diferença de velocidade entre o 2, encontrar retornará um iterador, inserção faz o mesmo e irá procurar o mapa de qualquer maneira para determinar se a entrada já existe.

Então .. o seu resume a preferência pessoal. Eu sempre tento inserir e atualizar, se necessário, mas algumas pessoas não gostam de lidar com o par que é retornado.

Answer 4

Eu acho que se você fizer uma descoberta, em seguida, inserção, o custo extra seria quando você não encontrar a chave e realizar a inserção depois. É uma espécie de como olhar através de livros em ordem alfabética e não encontrar o livro, em seguida, olhando através dos livros novamente para ver onde inseri-lo. Tudo se resume a como você vai ser lidar com as chaves e se eles estão mudando constantemente. Agora há uma certa flexibilidade no que se você não encontrá-lo, você pode entrar, exceção, fazer o que quiser ...

Answer 5

Eu estou perdido na resposta superior.

Encontre retornos map.end () se não encontrar nada que significa que se você está adicionando coisas novas, então

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

é duas vezes mais lento como

map.insert

para qualquer elemento não estiver no mapa, uma vez que terá que procurar duas vezes. Uma vez para ver se ele está lá, novamente para encontrar o lugar para colocar a coisa nova.

Answer 6

Se você está preocupado com eficiência, você pode querer verificar para fora hash_map <> .

Normalmente mapear <> é implementado como uma árvore binária. Dependendo de suas necessidades, um hash_map pode ser mais eficiente.

Answer 7

Eu não parecem ter pontos suficientes para deixar um comentário, mas a resposta assinalada parece ser prolixo para mim - quando você considera que inserem retorna o iterador de qualquer maneira, por que ir à procura lower_bound, quando você pode simplesmente usar o iterador retornado. Strange.

Answer 8

Qualquer respostas sobre a eficiência vai depender da implementação exata do seu STL. A única maneira de saber ao certo se a referência as duas coisas. Eu acho que a diferença é pouco provável que seja significativa, assim o decidir com base no estilo que preferir.

Answer 9

mapa [chave] - vamos stl classificar. Isso é comunicar a sua intenção de forma mais eficaz.

Sim, bastante justo.

Se você fizer uma descoberta e, em seguida, uma inserção que você está executando 2 x O (log N) quando você começa um perder como a descoberta só permite que você saiba se você precisa inserir não em que a inserção deve ir (poderia ajudar lower_bound você aí). Apenas uma inserção em linha reta e, em seguida, examinar o resultado é a maneira que eu iria.