multi_index: iterator_to complexity
Hi, The following two calls have constant complexity (according to docs) for all indices: iterator iterator_to(const value_type& x); const_iterator iterator_to(const value_type& x) const; As far as I understand, the single way to reach the constant complexity in searching by pointer is to store the objects in continuous memory area. Is it correct?
Matwey V. Kornilov <matwey.kornilov <at> gmail.com> writes:
Hi,
The following two calls have constant complexity (according to docs) for all indices:
iterator iterator_to(const value_type& x); const_iterator iterator_to(const value_type& x) const;
Correct, these are constant complexity.
As far as I understand, the single way to reach the constant complexity in searching by pointer is to store the objects in continuous memory area.
Is it correct?
No, it's not correct. In fact, elements in a multi_index_container are *not* stored contiguously. 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). So, whereas the following works as expected: multi_index_container<int,...> m; ... const int& x=*(m.find(...)); auto it=m.iterator_to(x); the following does not: multi_index_container<int,...> m; ... int x=*(m.find(...)); auto it=m.iterator_to(x); // undefined behavior because x is a copy of a value inside m, not a reference to the value itself, which is what iterator_to requires. Joaquín M López Muñoz Telefónica
09.03.2015 10:02, Joaquin M Lopez Munoz пишет:
Matwey V. Kornilov <matwey.kornilov <at> gmail.com> writes:
Hi,
The following two calls have constant complexity (according to docs) for all indices:
iterator iterator_to(const value_type& x); const_iterator iterator_to(const value_type& x) const;
Correct, these are constant complexity.
As far as I understand, the single way to reach the constant complexity in searching by pointer is to store the objects in continuous memory area.
Is it correct?
No, it's not correct. In fact, elements in a multi_index_container are *not* stored contiguously.
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). So, whereas the following works as expected:
multi_index_container<int,...> m; ... const int& x=*(m.find(...)); auto it=m.iterator_to(x);
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? What I want is to understand if the following code is correct and works in O(1): typedef std::pair<const Key, Value> container_value_type; typedef boost::multi_index::multi_index_container< container_value_type, boost::multi_index::indexed_by< boost::multi_index::random_access<>, boost::multi_index::hashed_unique< boost::multi_index::member< container_value_type, const Key, &container_value_type::first> > > > container_type; container_type map_; //... auto it = map_.get<1>().find(key); if (it != map_.get<1>().end() ) { map_.get<0>().iterator_to(*it)-map_.get<0>().begin(); // unique number from 0 to map_.size()-1 }
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
Joaquin M Lopez Munoz <joaquin <at> tid.es> writes:
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 [...]
I think I misunderstood your question. Of course nodes store additional data other than the value itself. The data depends on the indices making up your container. A short explanation on this is given at: http://stackoverflow.com/a/4208349/213114 Joaquín M López Muñoz Telefónica
participants (2)
-
Joaquin M Lopez Munoz -
Matwey V. Kornilov