[MultiIndex] "Compatible Sorting Criterion"
The docs mention that the definition is cumbersome. I think you could probably do much better with a formulation that relies on the concept of being partitioned with respect to a predicate function. See www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html and the wording changes (now in the standard) at: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#270 -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams <dave <at> boostpro.com> writes:
The docs mention that the definition is cumbersome. I think you could probably do much better with a formulation that relies on the concept of being partitioned with respect to a predicate function. See
www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
and the wording changes (now in the standard) at:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#270
I'm glad you bring this up: I already knew your work on N1313 by the time I was writing the compatible sorting thing, and decided to go for my formulation instead because the partition phrasing obscures, in my opinion, the intuition behind this: One can use a sorted range of X's to find embedded Y's if sorting of X's implies sorting of Y's. This intuition is a strong leit motif in composite keys, for instance. The partition formulation is undeniably neater technically but IMHO it leaves the reader perplexed as to what their actual applications are. All of this is highly subjective, of course. Off topic: It is a pity that the partition-based semantic extension to binary_search and similar was not also applied somehow to std::[multi]set, as the motivations in N1313 extend naturally to this case. Boost.MultiIndex ordered indices do provide this extension and I know this has been the reason for its usage in certain contexts besides its multi-indexing capabilities. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
on Sat Nov 01 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
David Abrahams <dave <at> boostpro.com> writes:
The docs mention that the definition is cumbersome. I think you could probably do much better with a formulation that relies on the concept of being partitioned with respect to a predicate function. See
www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
and the wording changes (now in the standard) at:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#270
I'm glad you bring this up: I already knew your work on N1313 by the time I was writing the compatible sorting thing, and decided to go for my formulation instead because the partition phrasing obscures, in my opinion, the intuition behind this: One can use a sorted range of X's to find embedded Y's if sorting of X's implies sorting of Y's. This intuition is a strong leit motif in composite keys, for instance.
Interesting you should say so. IMO thinking of partitioning reveals much more about the fundamental requirements related to "ordered search."
The partition formulation is undeniably neater technically but IMHO it leaves the reader perplexed as to what their actual applications are. All of this is highly subjective, of course.
Yes.
Off topic: It is a pity that the partition-based semantic extension to binary_search and similar was not also applied somehow to std::[multi]set, as the motivations in N1313 extend naturally to this case. Boost.MultiIndex ordered indices do provide this extension and I know this has been the reason for its usage in certain contexts besides its multi-indexing capabilities.
Good point. I suggest you write a proposal for the committee. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (2)
-
David Abrahams -
Joaquin M Lopez Munoz