c++ 将 find() 映射到可能的 insert():如何优化操作?

2022-01-07 00:00:00 c++ map stl

我正在使用 STL 地图数据结构,目前我的代码首先调用 find():如果键之前不在地图中,它会调用 insert()它,否则它什么都不做.

I'm using the STL map data structure, and at the moment my code first invokes find(): if the key was not previously in the map, it calls insert() it, otherwise it does nothing.

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() 中的一个(对应于 operator[] ).

I was wondering if there is a better way than this, because as far as I can tell, in this case when I want to insert a key that is not present yet, I perform 2 lookups in the map data structures: one for find(), one in the insert() (which corresponds to the operator[] ).

预先感谢您的任何建议.

Thanks in advance for any suggestion.

推荐答案

通常,如果您执行查找和插入操作,那么您希望保留(并检索)已存在的旧值.如果您只想覆盖任何旧值,map[foo_obj]="some value" 会这样做.

Normally if you do a find and maybe an insert, then you want to keep (and retrieve) the old value if it already existed. If you just want to overwrite any old value, map[foo_obj]="some value" will do that.

以下是获取旧值的方法,如果不存在则插入一个新值,通过一次地图查找:

Here's how you get the old value, or insert a new one if it didn't exist, with one map lookup:

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]

这是一个足够常见的习惯用法,您可能想要使用辅助函数:

This is a common enough idiom that you may want to use a helper function:

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 计算,如果它已经存在,你想跳过它(例如记忆),你也可以概括:

If you have an expensive computation for v you want to skip if it already exists (e.g. memoization), you can generalize that too:

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 添加另一个参数.

If the mapped type isn't default constructible, then make F provide a default value, or add another argument to get_else_compute.

相关文章