46

std::map has an insert method that takes a "hint" iterator that will reduce the insertion time from log(n) to constant time if the hint is correct. Its pretty obvious how this would work, since the container could just make sure the newly added item has a key that is less than the hint and has a key that is greater than the item before the hint. Otherwise the hint was wrong and it performs a normal insert.

std::unordered_map also has a similar insert with hint function. What, if anything, does the hint do? Its not obvious to me how another a "hint" iterator could be used to speed up a hash map insertion.

If it is used, what is an appropriate "hint". In std::map, the hint is typically found by calling lower_bound on the map.

Improve this question
2
  • 12
    I think the hint overload is just for interface-compatability with the normal std::map, since you'd have to know exactly where the hash for your value was to be inserted to do anything useful - which means you need to factor in the load, the buckets, etc, basically reproducing what unordered_map does internally. Also, as you noted, insert is amortized O(1) anyways. Commented Mar 21, 2013 at 22:54
  • 1
    So to be clear, you are saying it doesn't do anything? That's what I had guessed..that it was just for compatibility. Commented Mar 21, 2013 at 22:58

2 Answers 2

Reset to default
29

It is an interface compatibility issue. Basically, the design is done considering the interface of std::map.

In other words, for std::unordered_map it does not differ a hint is provided or not.

Additional Information from the comments here:

The interface compatibility is very important because being able to quickly/easily switch between map and unordered_map provides the valuable flexibility of painlessly transition since performance is often the deciding factor in choosing one over the other.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

+1 Yes, the interface compatibility is very important for generic code (e.g. where the container is a template parameter: template <class Map>). Being able to quickly/easily switch between map and unordered_map is very important since performance is often the deciding factor in choosing one over the other.
@HowardHinnant: as OP noted, a hint is typically obtained by call to map::lower_bound(), and unordered_map doesn't have this method (cos it's meaningless for unordered container). Doesn't this mean interface compatibility is still not provided?
@AndyT: There are clear limits to the interface compatibility. However find and equal_range are other rich sources of iterators which can be found in both API's. If switching back and forth is an important goal for you, you stick to the common API subset. The committee has done everything it can to make the subset as large as is practical, such as allowing you to provide a useless hint when inserting into an unordered_map.
@HowardHinnant: shouldn't clarity have higher priority than convenience? In this case convenience is small because just gives you a bit more compatible interface. I believe in summary time spent by confused people trying to realized how to use that hint argument is greater than time won by people who really needed to switch between map and unordered_map. Of course, it's my subjective opinion.
@AndyT: This is always an option for you: cplusplus.github.io/LWG/lwg-active.html#submit_issue
|
7

The hint allows the unordered map implementation to do a value compare first to see if the hint works. This avoids having to do the hash function which can be more costly than a compare operation.

Improve this answer

4 Comments

can you give an example of how this would work? Ie, how you would find a hint and use it to insert into a map?
I think the point here is that if the hint points at the correct item... that is, the key is already in the unordered_map, then the insert will see that (by comparing the value at the hint against the passed in value), and not need to compute the hash. If the key is not in the unordered_map, I think there would be no improvement in that case.
In the typical use cases I've encountered with using the hint in a std::map, the insert is only called with the hint at the point when you already know the item is not in the map, because you've first searched and found its not there but where it would be (using lower_bound). So seems like this use of the hint on unordered_map, if true, would have no practical value.
Do extant stdlib implementations do this?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.