Преимущества использования lower_bound для поиска карты перед вставкой. Эквивалент для ptr_map?

Question

Преимущества использования 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? Или это не будет применимо?

1

boost-ptr-container c++map optimization

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Есть два наиболее эффективных способа сделать это.

Первый эффективный способ — просто позвонить insert (как и в случае с STL). Это возвращает pair<iterator,bool> поэтому, если он уже существует, он не вставляется.

Второй способ, который вы используете, когда вам нужно создать объект, если ключ не существует, это использовать operator[] который возвращает вам ссылку на то, что там. Если элемент отсутствует, он вставляет для вас значение, созданное по умолчанию.

Обратите внимание на разницу здесь: для обычной карты STL на указатели, operator[] вернет вам указатель и вставит нулевой. за boost::ptr_map он не будет вставлять нулевой указатель, он будет вставлять указатель на созданный по умолчанию объект.

Если ваша коллекция может фактически содержать объекты, созданные по умолчанию, и у вас еще нет объекта, который вы хотите вставить, я не могу найти эффективный способ сделать это за один раз. Возможно, не используйте эту коллекцию в этом случае, или убедитесь, что ваши объекты немного изменены, чтобы у вас был какой-то флаг, показывающий, что он «построен по умолчанию», то есть, что-то вроде нулевого состояния.

1