std :: map insert或std :: map find？

Question

假设您要保留现有条目的地图.20%的情况下,您插入的条目是新数据.使用返回的迭代器执行std :: map :: find然后std :: map :: insert是否有优势？或者是否更快尝试插入然后根据迭代器是否指示记录是否插入来执行操作？

Answer 1

答案是你不做.相反,你想要做的事通过的24项建议的有效STL由斯科特·迈尔斯:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Answer 2

这个问题的答案还取决于创建您在地图中存储的值类型的成本:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

对于诸如int之类的值类型,上面将比查找后跟插入(在没有编译器优化的情况下)更有效.如上所述,这是因为仅通过地图搜索一次.

但是,对insert的调用要求您已经构造了新的"value":

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

为了调用'insert',我们支付昂贵的电话来构建我们的价值类型 - 而且从你在问题中所说的,你不会在20%的时间内使用这个新值.在上面的情况下,如果更改map值类型不是一个选项,那么首先执行'find'检查是否需要构造元素会更有效.

或者,可以使用您喜欢的智能指针类型更改地图的值类型以存储数据的句柄.对insert的调用使用空指针(构造起来非常便宜),并且只有在必要时才构造新的数据类型.

Answer 3

2之间的速度几乎没有任何差异,find将返回迭代器,insert也是如此,并且无论如何都将搜索地图以确定该条目是否已存在.

所以..它取决于个人喜好.我总是尝试插入,然后在必要时更新,但有些人不喜欢处理返回的对.

Answer 4

我想如果你做一个查找然后插入,额外的成本将是你没有找到密钥并执行插入后.这有点像按字母顺序浏览书籍而不是查找书籍,然后再次浏览书籍以查看插入的位置.它归结为你将如何处理密钥以及它们是否在不断变化.现在有一些灵活性,如果你没有找到它,你可以记录,例外,做你想做的任何事情......