С++ map find(), возможно, insert(): как оптимизировать операции?

Я использую структуру данных карты STL, и в настоящий момент мой код сначала вызывает find(): если ключ ранее не был на карте, он вызывает insert(), иначе он ничего не делает.

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

Мне было интересно, есть ли лучший способ, чем это, потому что, насколько я могу судить, в этом случае, когда я хочу вставить ключ, которого еще нет, я выполняю 2 поиска в структурах данных карты: один для find(), один в insert() (что соответствует оператору []).

Спасибо заранее за любое предложение.

Ответ 1

Обычно, если вы находите и, возможно, вставку, то вы хотите сохранить (и получить) старое значение, если оно уже существует. Если вы просто хотите перезаписать любое старое значение, map[foo_obj]="some value" сделает это.

Здесь вы можете получить старое значение или вставить новый, если он не существует, с одним поиском карты:

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]

Это достаточно распространенная идиома, что вы можете использовать вспомогательную функцию:

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");

Если у вас есть дорогостоящее вычисление для v, которое вы хотите пропустить, если оно уже существует (например, memoization), вы можете также обобщить это:

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

где, например,

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());

Если отображаемый тип не является конструктивным по умолчанию, тогда сделайте F значением по умолчанию или добавьте еще один аргумент в get_else_compute.

Ответ 2

Существует два основных подхода. Первый заключается в использовании функции insert, которая принимает тип значения и которая возвращает итератор и bool, которые указывают, произошла ли вставка, и возвращает итератор либо существующему элементу с тем же ключом, либо вновь вставленным элементом.

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") );

Преимущество этого в том, что это просто. Основным недостатком является то, что вы всегда создаете новое значение для второго параметра независимо от того, требуется ли вставка. В случае строки это, вероятно, не имеет значения. Если ваша стоимость стоит дорого, это может быть более расточительным, чем необходимо.

Для этого нужно использовать версию вставки "hint".

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

Вставка будет гарантированно находиться в амортизированном постоянном времени, только если элемент вставлен сразу после поставленного итератора, следовательно --, если это возможно.

Edit

Если эта потребность в -- кажется нечетной, то это так. В стандарте есть открытый дефект (233), который подчеркивает эту проблему, хотя описание проблемы, поскольку оно относится к map, более ясное в дублированном выпуске 246.

Ответ 3

В вашем примере вы хотите вставить, когда он не найден. Если построение по умолчанию и установка значения после этого не дорого, я бы предложил более простую версию с 1 поиском:

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

Если ваш пример говорит о том, что вы на самом деле хотите, подумайте о том, чтобы добавить это значение как str Foo::s, вместо этого у вас уже есть объект, поэтому поиска не потребуется, просто проверьте, имеет ли значение по умолчанию для этого элемента. И сохраните объекты в std::set. Даже расширение class FooWithValue2 может быть дешевле, чем при использовании map.

Но Если соединение данных с помощью такой карты действительно необходимо или если вы хотите обновить только в том случае, если она существует, то у Джонатана есть ответ.