C ++ функция для вставки в шаблон карты

Question

Продолжая мой последний вопрос Карта классов шаблонов C ++ Я реализовал функцию для вставки некоторых значений.Эта функция вставляет одно и то же значение для диапазона клавиш.Если ключ существует на карте, он должен перезаписать старые значения.Является ли функция в конечном итоге правильной и эффективной?Не могли бы вы предложить лучший способ его реализации?

void insert_ToMap( K const& keyBegin, K const& keyEnd, const V& value) 
{
  if(!(keyBegin < keyEnd))
    return;

  const_iterator it;

  for(int j=keyBegin; j<keyEnd; j++)
  {
    it = my_map.find(j);

    if(it==my_map.end())
    {
      my_map.insert(pair<K,V>(j,value));
    }
    else
    { 
      my_map.erase(it);
      my_map.insert(pair<K,V>(j, value));
    }
  }
}

Я пытаюсь:

int main()
{
  template_map<int,int> Map1 (10);

  Map1.insert_ToMap(3,6,20);
  Map1.insert_ToMap(4,14,30);
  Map1.insert_ToMap(34,37,12);

  for (auto i = Map1.begin(); i != Map1.end(); i++)
  {
    cout<< i->first<<"   "<<i->second<<std::endl; 
  }
}

Answer 1

Чтобы вставить, существует ли ключ:

typedef std:::map<K, V> map_type;

std::pair<typename map_type::iterator, bool> p
         = my_map.insert(std::pair<K const &, V const &>(key, new_value));

if (!p.second) p.first->second = new_value;

Эта конструкция использует тот факт, что insert уже выполняет find(), и если вставка завершается неудачно, вы можете немедленно использовать полученный итератор для перезаписи сопоставленного значения.

Здесь есть определенная скрытая стоимость: вставка всегда делает копию элемента, независимо от того, успешно ли он выполняется. Чтобы избежать даже этого, мы можем использовать несколько более подробный подход, используя lower_bound() для поиска предполагаемого ключа и одновременно обеспечить правильную позицию вставки для нового элемента:

typename map_type::iterator it = my_map.lower_bound(key);

if (it == my_map.end() || it->first != key)
{
  my_map.insert(it, std::pair<K const &, V const &>(key, new_value));  // O(1) !
}
else
{
  it->second = new_value;
}

Версия с двумя аргументами insert() работает в постоянном времени, если подсказка вставки (итератор в первом аргументе) является правильной позицией для вставки, что в точности и обеспечивает lower_bound().