c ++ mapa find () para possivelmente inserir (): como operações otimizar?

Question

Eu estou usando a estrutura de dados mapa STL, e neste momento o meu código primeiros invoca find () : se a chave não estava anteriormente no mapa, ele chama insert () , caso contrário, ele não faz nada.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

Eu queria saber se existe uma maneira melhor do que isso, porque tanto quanto eu posso dizer, neste caso, quando eu quero inserir uma chave que não está presente ainda, eu executo 2 pesquisas nas estruturas de dados de mapas: um para encontrar () , um no inserto () (o qual corresponde ao operador [] ).

Agradecemos antecipadamente por qualquer sugestão.

Answer 1

Normalmente, se você faz uma descoberta e talvez uma inserção, em seguida, que pretende manter (e recuperar) o valor antigo se ele já existia. Se você quiser apenas para substituir qualquer valor antigo, map[foo_obj]="some value" vai fazer isso.

Aqui está como você obter o valor de idade, ou inserir um novo se ele não existisse, com consulta um mapa:

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

Este é um idioma comum o suficiente para que você pode querer usar uma função auxiliar:

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

Se você tem um cálculo caro para v você quiser pular se ele já existe (por exemplo memoization), você pode generalizar isso também:

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

onde por exemplo.

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

Se o tipo de mapeada não é o padrão constructible, em seguida, fazer F fornecer um valor padrão, ou adicionar outro argumento para get_else_compute.

Answer 2

Existem duas abordagens principais. O primeiro é a utilização da função de inserção que leva um tipo de valor e que retorna uma iteração e um booleano que indicam se uma inserção ocorreu e retorna uma iteração, quer ao elemento existente com a mesma chave ou o elemento recentemente inserido.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

A vantagem disso é que ele é simples. A principal desvantagem é que você sempre construir um novo valor para o segundo parâmetro ou não uma inserção é necessária. No caso de uma corda isso provavelmente não importa. Se o seu valor é caro para construir este pode ser mais dispendioso do que o necessário.

A maneira redonda isso é usar a versão 'pitada' de inserção.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

O insertiong é garantida para ser em tempo constante amortizado apenas quando o elemento está inserido imediatamente após a iteração fornecido, por conseguinte, o --, se possível.

Editar

Se esta necessidade de -- parece estranho, então é. Há um defeito aberto (233), no padrão que hightlights esta questão, embora a descrição do problema, uma vez que se aplica a map é mais clara na edição duplicado 246 .

Answer 3

No seu exemplo, que deseja inserir quando não é encontrado. Se a construção padrão e definindo o valor depois que não é caro, eu sugiro versão mais simples com 1 pesquisa:

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn't in map), set value
                                // else existed already, do nothing

Se o seu exemplo diz o que você realmente quer, considere adicionar esse valor como str Foo::s em vez disso, você já tem o objeto, de modo que há pesquisas seriam necessárias, basta verificar se ele tem valor padrão para esse membro. E manter os objs na std::set. Mesmo estendendo class FooWithValue2 pode ser mais barato do que usar map.

Mas se juntar dados através do mapa como este é realmente necessário ou se você quiser atualizar apenas se existisse, em seguida, Jonathan tem a resposta.