25

I'm a little bit confused by std::map::insert's semantics. I mean, I'm not complaining - the standard is the standard and the API is the way it is. Still,

insert will

the insertion operation checks for each element inserted whether another element exists already in the container with the same key value, if so, the element is not inserted and its mapped value is not changed in any way.

And - only in its single-argument version pair<iterator,bool> insert ( const value_type& x ); will it even tell you if it even inserted the (new, possibly different) value to the key(s). As far as I understand, the iterator versions will silently ignore insertions if the key already exists.

For me, this is simply counter intuitive, I would have expected the value part to be overwritten and the old value part to be discarded on insert. Obviously, the designers of the STL thought differently -- anyone knows the (historical) rationale or can give a thorough explanation of how the existing semantics make (more) sense?

By example:

There are a few basic ways to implement insert in a single-key map such as std::map:

  • insert, replace if already exists
  • insert, ignore if already exists (this is the behavior of std::map)
  • insert, throw error if already exists
  • insert, UB if already exists

I'm now trying to understand why insert_or_ignore makes more sense than insert_or_replace (or insert_or_error)!

I looked into my copy of TC++PL (unfortunately I only have the German edition), and interestingly, Stroustrup writes in chapter 17.4.1.7 (list operations for map): (sorry rough translation from German)

(...) Normally, one doesn't care whether a key(sic!) is newly inserted or already existed before the call to insert() (...)

Which, it seems to me, would only hold true for set, and not for map, because for a map, it does make quite some difference if the provided value was inserted or the old one remains in the map. (It obviously doesn't matter for the key, as that one is equivalent.)

Note: I know about operator[] and I know about Item 24 of Effective STL and the there proposed efficientAddOrUpdate function. I'm just curious for a rationale into insert's semantics because I personally find them counter intuitive.

chappjc
  • 30,359
  • 6
  • 75
  • 132
Martin Ba
  • 37,187
  • 33
  • 183
  • 337
  • 5
    Well, you didn't ask it to modify an existing value, you asked it to insert a (new) value. I agree that reporting failure more consistently would have been a good thing though. You can still dereference the returned iterator and check whether the new value or an old one is present, or even use that iterator to update the existing value. – Ben Voigt May 14 '12 at 14:15
  • 3
    If you want to replace/create, use the `operator[]`. – BoBTFish May 14 '12 at 14:18
  • Here's some code to ["insert forcefully"](http://stackoverflow.com/a/8337563/596781) into a map. – Kerrek SB May 14 '12 at 14:29
  • @KerrekSB: why not *simply* use the idiomatic `operator[]` ? – Matthieu M. May 14 '12 at 14:48
  • @MatthieuM.: What if you need to make some extra decisions and/or logging based on whether the value already existed or not? – Kerrek SB May 14 '12 at 15:11
  • @Ben - see my edit ... as I understand, there is no way to "just" insert into a map without taking duplicates into account. You can only "insert_or_..." wrt. to duplicates, so I think the question is valid why the STL choose "..._ignore". – Martin Ba May 14 '12 at 15:21
  • @KerrekSB: then you cannot reuse `insert_forcefully` obviously, so you implement your custom behavior. – Matthieu M. May 14 '12 at 15:21
  • @KerrekSB: `insert` returns an iterator that can be used to update the value, if desired. – Ben Voigt May 14 '12 at 16:18
  • In C++ 11, `at` member function could be used if one wants that (third option in above example). – Phil1970 Sep 25 '18 at 00:14
  • C++17 adds https://en.cppreference.com/w/cpp/container/map/insert_or_assign :-) – Martin Ba Jul 21 '21 at 13:57

5 Answers5

7

The insert method is just not what you are looking for, it sounds like... The insert method is made to do just what the name implies... insert values. I agree that the ability to create a value if one isn't already present, and replace the one that is there otherwise is important in some situations, but in others you would just really rather not handle exceptions, return values, etc if you just want to do an insert only if the value isn't already present.

It sounds like the method you're looking for (as BoBTFish indicated above) is probably the [] operator. Just use it like so:

myMap["key"] = "value";

This will go through your map and find the key "key", and replace the corresponding value with "value". If the key isn't there, it will create it. Both methods are very useful in different situations, and I've found myself using both just depending on what I need.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
Kreg
  • 647
  • 1
  • 6
  • 17
  • 6
    I edited your post. First, do not sign (explicitly), it is frown upon (your user is still visible anyway); second, please check the markdown syntax to learn how to format inline code snippets and multiline code snippets. Thanks for your answer and welcome on SO :) – Matthieu M. May 14 '12 at 14:51
6

I don't know about an official rationale but I would note the duality with operator[].

It seems obvious that one would like the two flavors of insert:

  • purely additive
  • additive / destructive

If we see a map as a sparse representation of an array, then the presence of operator[] make sense. I do not know whether pre-existing dictionaries existed and dictated this syntax (maybe, why not).

Also, all STL containers have several overloads of insert, and this similarity of interfaces is what allow Generic Programming.

Therefore, we have at least two contenders for the API: operator[] and insert.

Now, in C++, if you read:

array[4] = 5;

it is naturaly that the content of the cell at index 4 has been destructively updated. As such, it is natural that map::operator[] should return a reference to allow this destructive update.

At this point, we now need a purely additive version as well, and we have this insert method lying around. Why not ?

Of course one could have given insert the same semantics as operator[] and then go ahead and implement a insert_or_ignore method on top. This would have been more work though.

Therefore, while I agree that it might be surprising, I think my reasoning is not too flawed and may be a likely explanation of the circumstances that lead us here :)

Regarding the alternatives you proposed:

  • insert, UB if already exists

Fortunately, it is not!

  • insert, throw error if already exists

Only Java (and derivatives) is exception-crazy. C++ was conceived in a time where exceptions were used for exceptional circumstances.

  • insert, replace if already exists
  • insert, ignore if already exists (this is the behavior of std::map)

We agree that the choice was between one of those. Note that even though map elected the second option, it does not completely ignore the fact that the item already existed, at least in the single item version since it warns you that the item was not inserted.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • +1, although I'm not sure we really *need* a purely additive function, as we always could invoke `find()` first. (with both `insert` either/or `op[]`) But maybe the duality was/is a good reason. – Martin Ba May 14 '12 at 15:24
  • @Martin: I agree that a `find` would have worked to create a purely additive function. It would have required some boiler-plate though. – Matthieu M. May 14 '12 at 15:27
  • Yeah, interestingly enough, similar boilerplate (or helper fn) you need now for an efficient insert_or_replace :-) – Martin Ba May 14 '12 at 17:19
  • @Martin: no you don't, you juste use `map[key] = value` and it inserts or replaces. – Matthieu M. May 14 '12 at 17:21
  • Only problem is that `map[key] = val` isn't efficient, because it first default constructs the element if it doesn't exists. Often not a big deal, but nagging nonetheless. – Martin Ba May 14 '12 at 18:17
  • 1
    @Martin: and worse, it's also a problem in that it *requires* a default constructor (which is not otherwise necessary for using `map`). Oh well... – Matthieu M. May 14 '12 at 18:38
  • 1
    Too bad C++ doesn't have an `operator[]=(key, value)`. – dan04 May 14 '12 at 22:14
3

I do not claim to know the original rationale for the decision, but it's not too hard to make one up. I think ;-)

The current behaviour of "insert or ignore" makes it very easy to implement the other two -- at least for those of us who aren't above creating and using non-member functions to supplement the standard library functionality ("it's not OOP-y enough!").

Example (written on the spot, so errors may be present):

template<typename Map>
void insert_or_update(Map& map, typename Map::value_type const& x)
{
  std::pair<typename Map::iterator, bool> result = map.insert(x);
  if (!result.second)
    result.first->second = x.second; // or throw an exception (consider using
                                     // a different function name, though)
}

Do note that as is, the function above doesn't really differ much from operator[] -- yes, it avoids default initialization, but at the same time (because I'm lazy) it fails to capitalize on move semantics that your up-to-date STL probably already supports for operator[].

Anyhow, any other insert behaviour for map would've made it more tedious to implement the others, as map::find only returns an end sentinel if the key isn't already in the map. With the help of <algorithm> (and especially lower_bound) it would, of course, still be possible to write performant accessory functions without drowning them implementation details and ugly generic constructs such as loops ;-).

eq-
  • 9,986
  • 36
  • 38
0

From insert() you don't expect existing objects in the container to be touched. That's why it simple does not touch them.

ypnos
  • 50,202
  • 14
  • 95
  • 141
  • 1
    Doesn't answer the *why it doesn't report an error?* part of the question, but yes it answers one part of the question.The behavior of the function is rather intuitive, expecting an `insert` call to modify existing elements would be rather counter intuitive. – Alok Save May 14 '12 at 14:28
  • 2
    No offense meant, but you're parroting back the defined semantics of the function, not providing a rationale. *Why* do I not expect existing elements to be touched? Because it's called "insert" and not "insert_or_replace" or what? Again, *for me* it was counter intuitive, and it doesn't help me understand when I'm told "no, it's not". :-) – Martin Ba May 14 '12 at 14:38
  • @Martin: Wouldn't `insert_or_ignore` (as in SQLite) be a better name than `insert_or_replace`? – dan04 May 14 '12 at 15:07
  • @dan04 - yes for the specified semantics. (Insert_or_replace was what I personally found more intuitive for insert and.) – Martin Ba May 14 '12 at 15:13
0

pair<iterator,bool> <- doesn't the bool part tell if the insertion succeed or not?

You can just update the value part of the returned iterator if the bool part is false to update the existing item with the same key.

BlueWanderer
  • 2,671
  • 2
  • 21
  • 36
  • The question mentioned this. You ignored the part of the question that mentioned the other four overloads of `std::map::insert`. – Ben Voigt May 14 '12 at 16:16