Contradiction vs. Concentration
emmtrix Tech Posts: Work & Fun with C++ Standard
Congratulations, you have made it until the end of our emmtrix Tech Posts mini-series Work & Fun with C++ Standard! As a reward you have earned one last task. 😊 It is a mysterious case at first sight and once you solve it, you might find it funny and that all the details make sense. The category is Knowledge, so there is something to be learned along the way. Here, some background first:
The standard library in C++ defines the following associative containers: set, multiset, map and multimap.
Let’s focus on the map and multimap classes. The classes store key-value pairs in an ordered (sorted by keys) manner. map supports unique keys, multimap supports equivalent keys (multiple elements with the same key).
Both of them define the function insert(p, t), where p is an iterator (see it as a pointer to some element) indicating the insertion point and t is the value to be inserted.
Contradiction: Remember what we wrote about our container classes? They are ordered! Now, how on earth can you insert an element at an arbitrary position p?
Well, you cannot. 😊
Concentration: Let’s dive into the C++ Standard and check what we really expect out of insert(p, t): “t is inserted as close as possible to the position just prior to p.” There you are: “as close as possible”!
For map, t will always be inserted at the predefined position independent of p and this will still be as close as possible (rather impossible to be any closer than what is predefined).
We have proved that in our enigmatic function, its main requirement is not violated, but the mystery has not been completely resolved. For that we need you!
Task: Why does it make sense to have the parameter p after all?
Hint: Look into multimap and remember what we wrote about it.
Disclaimer: There is another reason why insert(p, t) could be useful even for map, but the reason is minor and we will not go into it.
Feel free to leave your answer in the comments below, and before we meet again try to find some fun in C++, not only work! 😉
Read on if you want to know the solution to the tasks…
First of all, the hint indicated that a multimap object can have multiple elements with equivalent keys.
In such a scenario, in which there is already at least one element prior to the insertion, with the key same as of the element to be inserted, it can be meaningful to have parameter p, because it determines the exact position of the inserted element among the elements with equivalent keys.