Sign up ×

I'm using an stl::map to store some key with a value. For my app, I need to to change the value of a key only if the current value is bigger then the previous one. To do this, I call find() to search if the key is already in the map and so to change its value, otherwise I call insert() to store the new key. Is there a way to do this kind of thing in an efficient way? Or to call only insert() with a custom constraint on the value?

share|improve this question
Show some code so that I understand what you are trying to do. –  Hindol Oct 7 '12 at 8:34
So, basically you want to do something like myMap[key] = std::max(myMap[key], new_value)? –  Zeta Oct 7 '12 at 8:40
@Zeta Yes, but only if the key is already stored in the map –  user1633717 Oct 7 '12 at 8:54

3 Answers 3

As per below, one of the insert overloads on the std::map returns a pair containing an iterator to the node and a bool. The bool tells you whether the insert was successful, or there was a dupe. If false, just update the value manually using the iterator.

#include <iostream>
#include <string>
#include <map>

int main()
  typedef std::map<std::string, int> TestMap;
  TestMap test;
  test.insert(std::make_pair("one", 1));

  std::pair<TestMap::iterator, bool> result =
      test.insert(std::make_pair("one", 2));

  if (!result.second)
    // was a duplicate, so let's manually set the value on the existing
    // map entry

    result.first->second = 2;

  std::cout <<"one") << std::endl; // outputs 2
share|improve this answer
Thanks, I think this is the best strategy! I only have to add a check of the previous value before to change it but it's exactly what I want. –  user1633717 Oct 7 '12 at 8:49
Excelent answer +1 –  Viniyo Shouta Oct 7 '12 at 9:07

If the map should be updated if the new value T newval is greater or equal to the previous T oldval and you use only values which are greater or equal to T() it's really simple:

myMap[key] = std::max(myMap[key],newval);

std::map::operator[] will return a reference to an element in the map, which will either be an already existing one or a new default constructed element (myMap[key] == T()).

Note that this solution uses std::map::insert behind the scene, but is a little bit easier to read if you only use non-negative values.

share|improve this answer
Thanks, it seems a good a strategy, maybe from the efficiency point of view is similar to the Troy's one. –  user1633717 Oct 7 '12 at 8:59
@user1633717: The complexity / efficiency of both solutions should be the same. The if is hidden in std::max, and the insert is hidden in the call of myMap[key]. insert has a complexity of O(log N), and the important thing is the missing find call, which would also be O(log N). –  Zeta Oct 7 '12 at 9:01
Yes, I quite agree with you, thanks again!!! –  user1633717 Oct 7 '12 at 9:05
Well, you have to search for key twice, so it's not that efficient. –  JohnB Oct 8 '12 at 16:16
@JohnB: Doesn't the compiler optimize the call of operator[]? Otherwise you could just use value_type & myelement = myMap[key]; myelement = std::max(myelement,newval); –  Zeta Oct 8 '12 at 16:20

Call lower_bound to search for the element. It will give you the next greater key if it does not exist. If the key does not exist, go back one step with the iterator, and then you can call insert with parameter position being provided, which reduces time to search for the correct position to insert (to almost zero probably, as you provide the correct position and map is ordered)

share|improve this answer
Thanks for your comment! I think the strategy of Troy is better, because I have to call only one time the insert(). –  user1633717 Oct 7 '12 at 8:50
Yes it is, definitely. –  JohnB Oct 7 '12 at 8:51
I really do not see the reason for a downvote. –  JohnB Oct 8 '12 at 16:17

Your Answer


