c ++ сопоставляет find() с возможной insert():как оптимизировать операции?

Question

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

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 поиска в структурах данных карты:один для найти(), один в вставить() (что соответствует оператор[] ).

Заранее благодарю за любое предложение.

Answer 1

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

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

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, которое вы хотите пропустить, если оно уже существует (например, памятка), вы также можете обобщить это:

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.

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

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

Способ обойти это - использовать "подсказочную" версию insert.

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

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

Редактировать

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

Answer 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 . Даже расширение класса FooWithValue2 может оказаться дешевле, чем использование map .

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