c ++ map find()可能insert():如何优化操作？

Question

我正在使用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次查找:一次用于查找( ),insert()中的一个 (对应于operator []).

提前感谢任何建议.

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

如果映射类型不是默认可构造的,则make 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") );

这样做的好处是它很简单.主要缺点是无论是否需要插入,总是为第二个参数构造一个新值.在字符串的情况下,这可能无关紧要.如果构建价值昂贵,这可能比必要的更浪费.

一种方法是使用插入的'提示'版本.

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中对适用的问题的描述更清楚.