vicente.botet <vicente.botet <at> wanadoo.fr> writes:
----- Original Message ----- From: "Andy Venikov" <avenikov <at> gmail.com> To: <boost <at> lists.boost.org> Sent: Friday, November 12, 2010 7:21 PM Subject: Re: [boost] Minimizing Dependencies within Generic Classes for Faster
and Smaller Programs
It looks like multi index container could greatly benefit from it. In fact, I think the example in the paper really represents an implementation of a multiindex container.
Or is multi-index already employing this technique?
_______________________________________________ Hi, The example in the paper coudl be considered as a kind of dynamic polymorphic multi-index. Boost.MultiIndex uses static polymorphism. I don't know if MultiIndex uses this technique. Joaquin?
Hi Andy and Vicente, Boost.MultiIndex iterators are not SCARY (better said, they are not SCARY in the way it'd be really useful) for the following independent reasons: 1. When in safe mode (http://tinyurl.com/37cq7tp ), iterators need to access internal information of the index they are associated to, hence they are dependent on the index type. In fact, I think this is a general problem of the SCARY approach with safe- or checked- iterator modes provided by some STL implementations. 2. When not in safe mode, the iterator type is not pure-SCARY in that it depends not only on the value type, but also on the allocator type. Why so? Because this dependency allows for the creation of advanced (and useful) shared-memory containers by way of Boost.Interprocess allocators, see http://tinyurl.com/2vfpbpw . Again, I think this is a potential general problem (not specifically related to Boost.MultiIndex) of the SCARY approach. 3. With these caveats, Boost.MultiIndex iterators can be said to be SCARY as long as they belong to the same category of index (ordered, hashed, sequenced, random.access) in some situations, not in others. For instance, the following compiles and works: // example 1 typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> > >
multi_t1;
typedef multi_index_container< int, indexed_by< ordered_non_unique<identity<int>,std::greater<int> > >
multi_t2;
multi_t1::nth_index<0>::type::iterator it1; multi_t2::nth_index<0>::type::iterator it2; it1=it2; // SCARY! but the following, which would be far more useful, does *not* work: // example 2 typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> >, ordered_non_unique<identity<int>,std::greater<int> > >
multi_t;
multi_t::nth_index<0>::type::iterator it1; multi_t::nth_index<1>::type::iterator it2; it1=it2; To understand why example 2does not work, and cannot be made to work without some runtime penalty, consider the typical (somewhat idealized) node structure of a std::set: struct node { int color; node* parent,left,right; value_type value; }; Obviously, iterators for independent std::set types with the same value_type are pointing to the same kinf of stuff, so SCARY is in principle possible. Now, the node structure of a two-index multi_index_container like the one defined at example 2 looks like this: struct node { int color1; node* parent1,left1,right1; int color2; node* parent2,left2,right2; value_type value; }; iterators associated to the first index do use the first group of tree traversal parameters (color1, parent1, left1, right1) whereas iterators associated to the second index use the second group (color2, parent2, left2, right2). So, it1 and it2 types *need* to be different because they act differently, and this is why the line it1=it2; results in a compiler error. To make the SCARY assignment work, that is, to allow for it1 and it2 to be of the same type, such a "unified" operator would have to be provided with some runtime info as to whether to use the first or the second group of tree taversal parameters. This of course is not optimal in terms of speed or space. The example developed at N2911 comes close to what could be thought of as a dynamic multi_index_container. This beast has pros and cons with respect to the current static multi_index_container, which are more or less those of dynamic vs. static approaches: - dynamic allows for run-time specification and modification of the indices comprising the container, and, if well designed, for SCARY assignment. - dynamic has some unavoidable penalties in performance and space consumption. Some years ago I played a little with a toy prototype of a dynamic multi_index_container but never went too far since I didn't see much public interest in the idea (and, truth be said, writing this is no minor task). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo