Вопрос:

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

c++ stl map

15842 просмотра

3 ответа

1349 Репутация автора

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

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

Автор: puccio Источник Размещён: 11.09.2009 07:23

Ответы (3)


35 плюса

8432 Репутация автора

Решение

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

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.

Автор: Jonathan Graehl Размещён: 11.09.2009 07:27

12 плюса

558784 Репутация автора

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

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

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

Обходным путем является использование «вставки» версии вставки.

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

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

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

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

Автор: CB Bailey Размещён: 11.09.2009 07:49

1 плюс

304 Репутация автора

В вашем примере вы хотите вставить, когда он не найден. Если построение по умолчанию и установка значения после этого не дорого, я бы предложил более простую версию с 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.

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

Автор: slyy2048 Размещён: 27.05.2017 11:06
32x32