Benefits of using lower_bound to search a map before insertion. Equivalent for ptr_map?

Question

While looking for an efficient approach to insert to a map only if the key does not exist, I came across this approach:

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));
}

That works well for std::map. However, boost::ptr_map does not provide a similar form of insert() i.e. one that accepts an iterator position.

So I'm wondering:

1. What's the benefit of that approach compared to doing a straight-forward insert? i.e.

   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
   }
   

2. If there's indeed a good reason to use the lower_bound approach, is it there an equivalent strategy for boost::ptr_map? Or would it not be applicable?

Answer 1

there are two most efficient ways to do this.

The first efficient way is just to call insert (as is also the case in STL). This returns pair<iterator,bool> so if it already exists it doesn't insert.

The second way, which you use when you have to create an object if the key doesn't exist, is to use operator[] which returns you a reference to what is there. If the item is not there, it inserts for you with a default-created value.

Note the difference here: for a regular STL map to pointers, operator[] will return you a pointer, and will insert a null one. for boost::ptr_map it will not insert a null pointer, it will insert a pointer to a default-constructed object.

If your collection may actually contain default-constructed objects, and you don't yet have the object you want to insert, I cannot find an efficient way to do it in one go. Perhaps don't use this collection in this case, or ensure that your objects are modified slightly so you have some kind of flag to show it is "default constructed" i.e. a sort of null state.