Why is it not possible to give std::map::find a hint when one can give std::map::insert a hint?

[Karen Pease]

This question is, of course, not specific only to std::map, but that's what I've been working with so I'll focus on that.

The definition for std::insert allows:

iterator insert (iterator position, const value_type& val);

Where position is a hint. One can likewise emplace with a hint:

template <class... Args>
  iterator emplace_hint (const_iterator position, Args&&... args);

The purpose of hints, of course, being so that std::map doesn't have to iterate through its red-black tree from the start, it can begin near its destination, dramatically reducing search time on a large tree.

So why does std::map::find not allow a hint?

  iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

Why must we search through the whole red-black tree with every find even if we know approximately where our lookup target will be?

-----------
In case you want a use case scenario...
-----------

In my particular case, I'm making a particular K-d tree class and its searchable node index is to be a std::map keyed off an class based around trinary bits, wherein:

0 = left-child
1 = no child
2 = right-child

The map would be, thusly, std::map<TrinaryKeyClass, KdTreeNode>

Such that a 1-dimensional case might have a key like:

02202111

... meaning "The key of the node representing left child's right child's right child's left child's right child". (Note that in a real-world case it'll generally be many-dimensional  and with much longer keys, but we'll keep it simple here).

Since one doesn't know how deep the tree goes for an arbitrary element that we want to look up the node for, we have to iterate down to find the deepest layer. The logic flow for an element whose max-depth key would be 02202002 would thus be:

---
Does 01111111 exist (std::map::find)?
Yes, it does. Then does 02111111 exist (std::map::find)?
Yes, it does. Then does 02211111 exist (std::map::find)?
Yes, it does. Then does 02201111 exist (std::map::find)?
Yes, it does. Then does 02202111 exist (std::map::find)?
Yes, it does. Then does 02202011 exist (std::map::find)?
No, does not. Thus 02202111 is the deepest we can go. Return the iterator we were given when we ran std::map::find on 02202111.
---

The search could also be done non-linearly - for example, trying 02201111 first, then 02202011, then 02202111, and thus potentially saving lookup time.  Either way, each iterator that we retrieve by our std::map::find is guaranteed to be "near" the iterator that we want to lookup next. With each step we progress, we get nearer and nearer the final destination. So obviously it only makes sense to want to pass this "hint" to std::map::find. Except, of course, we can't, because it doesn't appear to be in the standard, so each find has to search the tree from the beginning.

So, back to the original question:

1) Why is this not in the standard? Why only let some functions that do a search hint but not others? I'd think std::map::find would be the most obvious case where a person would want to give a hint....
2) What's the proper solution to this problem? Should I subclass std::map and implement my own std::map::find which takes a hint? It'd be ugly but if that's what I have to do...

Thanks  :)

 - kv, Karen

[Karen Pease]

Hmm, just caught a couple errors with the above post and also found a possible solution to my use case (but not a general purpose solution):

 * I should have been discussing std::map::lower_bound / std::map::upper_bound when talking about using the return value from a map lookup, since std::map::find doesn't return a neighboring iterator if the find fails.
 * The lack of hinting applies equally also to std::map::lower_bound and std::map::upper_bound
 * As a possible solution to my problem, if I restructure my keys suchly:

0 = no child
1 = left-child
2 = right-child

... and then search for the max depth element (for example, lower_bound(TrinaryKeyClass(12212112)), it should return the deepest element in the tree that exists. So that will suit my needs.

Nonetheless, I'm sure there's tons of use cases out there where that solution wouldn't apply, and it just seems odd that insert and emplace would allow hints but not find / upper_bound / lower_bound.

 - kv, Karen

[xavi]

Implementations are allowed to ignore the hint, and in the case of gcc, it just checks if the insertion position is immediately before or after the provided iterator, and otherwise it performs a full search. That wouldn't be of much use in your case. Anyway, restructuring the keys is a much better solution. 

It would probably be interesting to add a generic rbtree to the standard. Almost all implementations use an rbtree to implement set and map, so they would just need to expose it. Having something like boost's intrusive_rbtree (and other intrusive containers) in the standard would also make sense to me.

2014-02-11 Karen Pease <karen...@gmail.com>:

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.

[jerome.sa...@outlook.fr]

You can use the generic algorithm find_if on the pairs of the map, and a fonction object

[Tony V E]

I'm not against a hint on map::find, but I have questions about your kd-tree (as I just wrote one as well).

Why are you using a map?  A typical node-based kd-tree is already a tree and already logN, what is the benefit of using a map?