在插入之前使用lower_bound搜索地图的好处。等同于ptr_map？

在寻找一种有效的方法插入到地图只有在键不存在，我碰到this approach：在插入之前使用lower_bound搜索地图的好处。等同于ptr_map？

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

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first))) { 
    // key exists. Value accessible from lb->second 
} else { 
    // Do insert. Use lb as a hint to insert so it can avoid another lookup 
    mymap.insert(lb, MapType::value_type(k, v)); 
}

，对于std::map效果很好。但是，boost::ptr_map未提供类似形式的insert()，即接受迭代器位置的表单。

所以我想知道：

那是什么方法的好处相比，做一个直接的插入？即

std::pair<MapType::iterator, bool> ret; 
ret = mymap.insert(MapType::value_type(k, v)); 
if (!ret.second) { 
    // key exists. insertion not done. do something else 
}

如果确实有一个很好的理由来使用lower_bound方法，是那里boost::ptr_map等效的策略？或者它不适用？

来源

2012-11-12 Shawn Chin

有两种最有效的方法可以做到这一点。

第一有效的方法是只是调用insert（也如在STL的情况下）。这将返回pair<iterator,bool>，所以如果它已经存在，它不会插入。

如果密钥不存在，您必须创建对象时使用的第二种方法是使用operator[]，它会返回给您一个参考。如果该项目不存在，它会为您插入一个默认创建的值。

注意这里的区别是：一个普通的STL地图为指针，operator[]将返回一个指针，而将插入一个空的。对于boost::ptr_map它不会插入空指针，它会插入指向默认构造对象的指针。

如果你的集合可能实际上包含缺省构造的对象，而你还没有要插入的对象，我无法找到一个有效的方式做到这一点一气呵成。也许在这种情况下不要使用这个集合，或者确保你的对象被稍微修改，以便你有某种标志来显示它是“默认构造的”，即一种空状态。

来源

2012-11-12 15:58:22 CashCow

有趣的是，它显示我最初在提问前4分钟回答了这个问题。 – CashCow

非常感谢。你的第一个建议确实是我在使用这个例子中引用的方法之前所使用的。在我试图比较这两种方法的时候，它使用'ptr_map'来取消。我原来的问题写得不好，有点误导。现在更新。抱歉。 –

“最高效”这个词是有争议的 - 它取决于一个用例。有可能创建一个插入对象的代价非常高，因此首先需要检查，这是'lower_bound'可以发挥作用的地方。 – 2012-11-12 17:17:00

在插入之前使用lower_bound搜索地图的好处。等同于ptr_map？

回答

相关问题