std :: map insert ou std :: map find?

Supondo um mapa onde você deseja preservar as entradas existentes. 20% do tempo, a entrada que você está inserindo são novos dados. Há uma vantagem em fazer std :: map :: find then std :: map :: insert usando esse iterador retornado? Ou é mais rápido tentar a inserção e agir com base no fato de o iterador indicar ou não que o registro foi ou não inserido?

A resposta é que você não faz nada. Em vez disso, você deseja fazer algo sugerido pelo Item 24 do STL Efetivo de 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
}

A resposta a esta pergunta também depende de quão caro é 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 como um int, o procedimento acima será mais eficiente do que um find seguido por uma inserção (na ausência de otimizações do compilador). Conforme afirmado acima, isso ocorre porque a pesquisa no mapa ocorre apenas uma vez.

No entanto, a chamada para inserir requer que você já tenha o novo "valor" construído:

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;
  }
}

Para chamar de 'inserir', estamos pagando uma ligação cara para construir nosso tipo de valor - e pelo que você disse na pergunta, você não usará este novo valor 20% das vezes. No caso acima, se alterar o tipo de valor do mapa não for uma opção, é mais eficiente executar primeiro o 'localizar' para verificar se precisamos construir o elemento.

Como alternativa, o tipo de valor do mapa pode ser alterado para armazenar identificadores para os dados usando seu tipo de ponteiro inteligente favorito. A chamada para inserir usa um ponteiro nulo (muito barato de construir) e somente se necessário o novo tipo de dados é construído.

Quase não haverá diferença de velocidade entre os 2, find retornará um iterador, insert faz o mesmo e pesquisará no mapa de qualquer maneira para determinar se a entrada já existe.

Então ... é uma questão de 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.

Eu acho que se você fizer um localizar e inserir, o custo extra seria quando você não encontrar a chave e executar a inserção depois. É como olhar os livros em ordem alfabética e não encontrar o livro, depois olhar os livros novamente para ver onde inseri-lo. Tudo se resume a como você manipulará as chaves e se elas estão mudando constantemente. Agora há alguma flexibilidade em que se você não encontrar, você pode registrar, exceção, fazer o que quiser ...

Estou perdido na melhor resposta.

Find retorna map.end () se não encontrar nada, o 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 que

map.insert

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

Se você está preocupado com a eficiência, pode verificar o hash_map <> .

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

Eu não pareço ter pontos suficientes para deixar um comentário, mas a resposta marcada parece ser prolixa para mim - quando você considera que a inserção retorna o iterador de qualquer maneira, por que ir procurando lower_bound, quando você pode apenas usar o iterador retornado. Estranho.

Quaisquer respostas sobre eficiência dependerão da implementação exata de seu STL. A única maneira de saber com certeza é compará-lo de duas maneiras. Eu acho que a diferença provavelmente não será significativa, então decida com base no estilo de sua preferência.

map [tecla] - deixe stl resolver isso. Isso é comunicar sua intenção de maneira mais eficaz.

Sim, é justo.

Se você fizer um find e, em seguida, um insert, você está executando 2 x O (log N) quando errar, pois o find apenas permite que você saiba se você não precisa inserir onde o insert deve ir (lower_bound pode ajudá-lo nisso) . Apenas uma inserção direta e, em seguida, examinar o resultado é o caminho que eu faria.