Преимущества использования 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? Или это не будет применимо?
Решение
Есть два наиболее эффективных способа сделать это.
Первый эффективный способ — просто позвонить insert (как и в случае с STL). Это возвращает pair<iterator,bool> поэтому, если он уже существует, он не вставляется.
Второй способ, который вы используете, когда вам нужно создать объект, если ключ не существует, это использовать operator[] который возвращает вам ссылку на то, что там. Если элемент отсутствует, он вставляет для вас значение, созданное по умолчанию.
Обратите внимание на разницу здесь: для обычной карты STL на указатели, operator[] вернет вам указатель и вставит нулевой. за boost::ptr_map он не будет вставлять нулевой указатель, он будет вставлять указатель на созданный по умолчанию объект.
Если ваша коллекция может фактически содержать объекты, созданные по умолчанию, и у вас еще нет объекта, который вы хотите вставить, я не могу найти эффективный способ сделать это за один раз. Возможно, не используйте эту коллекцию в этом случае, или убедитесь, что ваши объекты немного изменены, чтобы у вас был какой-то флаг, показывающий, что он «построен по умолчанию», то есть, что-то вроде нулевого состояния.
Другие решения
Других решений пока нет …