C++ function to insert to template map

Question

Continuing from my last question C++ template class map I have implemented the function to insert some values. This function inserts the same value for a range of keys. If the key exists in the map it should overwrite the old values. Is the function eventually correct and efficient? Could you suggest a better way to implement it?

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

I try:

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

If you can somehow use for_each, instead of "for" the program will look more c++ and readable. — rakesh, Dec 07 '11 at 13:05
I thought I just showed you how to overwrite a value without erasing? — Kerrek SB, Dec 07 '11 at 13:07
I know this is an old question, but I recently came across a very similar piece of code (so I'm guessing I know where did this code came from) with a few more restrictions regarding the `K` type. I wanted to ask here before posting a new question: **what happens with that `for(int j=keyBegin; j — Nacho, Apr 07 '16 at 15:45

Kerrek SB · Accepted Answer · 2011-12-07T13:30:39.433

5

To insert whether or not the key exists:

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;

This construction takes advantage of the fact that insert already performs a find(), and if the insertion fails, you can immediately use the resulting iterator to overwrite the mapped value.

There is a certain hidden cost here: The insertion always makes a copy of the element, whether or not it actually succeeds. To avoid even that, we can use a slightly more verbose approach using lower_bound() to search for the purported key and simultaneously provide the correct insertion position for the new element:

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

The two-argument version of insert() operates in constant time if the insertion hint (the iterator in the first argument) is the correct position for the insertion, which is precisely what lower_bound() provides.

edited Dec 07 '11 at 13:30

answered Dec 07 '11 at 13:09

Kerrek SB

464,522
92
875
1,084

Aren't you missing `typename` before map_type::iterator? – Armen Tsirunyan Dec 07 '11 at 13:11
@Armen: the `typename` disambiguator is only allowed inside templates and if the name is dependent on a template parameter. – R. Martinho Fernandes Dec 07 '11 at 13:14
@R.MartinhoFernandes: Yeah, well, aren't K and V template parameters to the function and isn't iterator a dependent name?! – Armen Tsirunyan Dec 07 '11 at 13:16
@ArmenTsirunyan: I'm not sure; this doesn't follow from the OP's context. I would have preferred `::key_type` and `::mapped_type` anyway, but I trust the OP is sufficiently versed with templates to make the modifications as needed. – Kerrek SB Dec 07 '11 at 13:17
At the line it->second = new_value; the program stops and pops that iterator is not dereferencable. Why? I have included the above procedure into a loop for all the keys in the given range. Shouldn't be so? – arjacsoh Dec 07 '11 at 13:29
@arjacsoh: Yeah, sorry, the logic was broken. I fixed it now. The conditional should have been the other way round! – Kerrek SB Dec 07 '11 at 13:30
1

Why not `my_map[key] = new_value;`? – UncleBens Dec 07 '11 at 15:41
@UncleBens: I think the lower-bound approach makes one less copy, though you're absolutely right that this would be simpler! – Kerrek SB Dec 07 '11 at 15:43
Just that it would require value_type to be DefaultConstructible, which would otherwise be avoidable... – UncleBens Dec 07 '11 at 16:31
@UncleBens: yes, that's true -- that may actually have been the OP's original motivation in an earlier question; I forget now... – Kerrek SB Dec 07 '11 at 16:33

C++ function to insert to template map

1 Answers1

Linked