Matwey V. Kornilov <matwey.kornilov <at> gmail.com> writes:
09.03.2015 10:02, Joaquin M Lopez Munoz пишет:
iterator_to does not do any kind of search based on x, but takes a reference to an element of the container and returns an iterator to it (roughly speaking, converts an element pointer to a node pointer). [...]
As far as I understand, there should be some pointer magic, like the following
struct node { T obj; ... // Rest };
so given x, (node*)&x will point to the struct enveloping the object and should provide access to index-specific data to allow iterator incrementation and dereferencing. What kind of additional data is stored in node?
None. The thing is done via some careful casting (careful so as to stay within what the standard allows for): this is the key code, at lines 64-69 and 87-93 of boost/multi_index/detail/index_node_base.hpp: static index_node_base* from_value(const value_type* p) { return static_cast<index_node_base *>( reinterpret_cast<pod_value_holder<Value>*>( /* std 9.2.17 */ const_cast<value_type*>(p))); } template<typename Node,typename Value> Node* node_from_value(const Value* p) { typedef typename Node::allocator_type allocator_type; return static_cast<Node*>( index_node_base<Value,allocator_type>::from_value(p)); }
What I want is to understand if the following code is correct and works in O(1):
[...] auto it = map_.get<1>().find(key); if (it != map_.get<1>().end() ) { map_.get<0>().iterator_to(*it)-map_.get<0>().begin(); }
This is correct and works in O(1). Additionally, you might want to use project, which is specifically designed for converting iterators between indices: auto it = map_.get<1>().find(key); if (it != map_.get<1>().end() ) { map_.project<0>(it)-map_.get<0>().begin(); } Performance is going to be the same or even better (if the optimizer's not too good), and this is probably clearer. Joaquín M López Muñoz Telefónica