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

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

27 голосов
/ 11 сентября 2009

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

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

Ответы [ 3 ]

33 голосов
/ 11 сентября 2009

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

12 голосов
/ 11 сентября 2009

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

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 .

0 голосов
/ 28 мая 2017

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

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

...