C++ boost::multi_index: order of iterator_to member function

Question

Reading the boost::multi_index reference, I discovered that the iterator_to method has constant order. How is that possible? I mean, if an iterator is a different object than the value_type it represents, how is possible the container finds their corresponding internal node without searching on the index?

The only solution I can think of is that the address of the container's "internal node" (or whatever it is) is the same as the value_type it holds (for example, putting the node header just below the value_type or something). If the passed argument is a reference to an interal value_type, the corresponding iterator can be construct easily through the argument's address to get the red-black node.

But!! What about the C++ standard restricction that there's cannot be two objects with same address? What about alignment, padding, fill or any of those things that can happen at memory level?

*What about the C++ standard restricction that there's cannot be two objects with same address?* Why shouldn't there be two references to objects with the same address? Imagine I have a function that takes two references, and I supply it with two times the same object? — Marcus Müller, Jun 26 '16 at 20:53
If my memory doesn't betray me from those times when I was reading things from the standard, a reference is NOT an object, and both reference arguments will "point" to a same and unique object. There's no violations of the rule at all. But, in my "supposition" about the internals of the multiindex container, we have two different objects: the value_type saved on the container, and the node which actually saves it. — ABu, Jun 26 '16 at 22:48

score 1 · Accepted Answer · edited May 23 '17 at 11:58

Your intuition is correct: the value is part of a larger node structure (as explained for instance here) and iterator_to merely calculates the address of the node from the address of the value_type subobject. Now, the pointer arithmetics involved rely on the fact that the node (or the base class where the value is stored) is standard-layout, which guarantees that a pointer to first subobject (the value) can be cast to a pointer to the structure (the node): the relevant code can be looked at here.

C++ boost::multi_index: order of iterator_to member function

1 Answers1