Re: [boost] Re: Formal Review: Indexed Set

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2004-03-27 12:44:48

Hi Joaquin,

you wrote:

> > > > I miserably failed to define a composite unique key for my
indexed_set.
> [...]
> >
> > I already had. Trying to define
> >
> > typedef is::indexed_set<
> >   study,
> >   is::index_list<
> >     is::non_unique<is::tag<student_tag>,
> >         is::identity<study>, advisor_comparer>,
> >     is::non_unique<is::tag<advisor_tag>,
> >         is::identity<study>, date_comparer>
> >     is::unique<is::tag<pk_tag>, compose_key<
> >         BOOST_INDEXED_SET_MEMBER(study, string, name),
> >         BOOST_INDEXED_SET_MEMBER(study, string, advisor)
> >       >
> >     >,
> >   >
> > > tcs_genealogy;
> >
> > failed to compile in compose_key's
> >
> >   template<typename Arg>
> >   result_type operator()(Arg& arg)const;
> >
>
> Now I think I know what you're after. compose_key composes
> two keys the way mathematical composition of functions
> work, i.e.
>
>   comp_key(arg) := key1(key2(arg))
>
> and this is not what you want to do (if I understood you
> right.) Instead, you may use lex_compare (as you are already
> doing in your TCS port.)

Yes, something like

typedef is::indexed_set<
  study,
  is::index_list<
    is::unique<is::tag<student_tag>,
        is::identity<const study>, advisor_comparer>,
    is::non_unique<is::tag<advisor_tag>,
        is::identity<const study>, date_comparer>
  >
> tcs_genealogy;

does what I want. Thanks!

[...]

> > If namespace boost is not OK, then namespace boost::container probably
would
> > be a better choice.
>
> But I think auxiliary components (index_list, unique, tag, etc.)
> should have a namespace of their own. They're too specific to
> inhabit boost::container, IMHO.

OTOH it might be surprising to search for the components of one library in
different namespaces.

Two more remarks:

1. Documentation

My linux browser (konqueror) has difficulties to correctly display the
indexed_set documentation. HTML tidy shows a couple of problems.

2. Performance test

Compiling the performance tests with ICC 8.0 uncovered a problem in
indexed_set.hpp:

67,69c67,69
<   template <typename,typename,typename,typename> friend class
detail::index_base;
<   template <typename,typename>                   friend class
detail::header_holder;
<   template <typename,typename>                   friend class
detail::converter;
---
>   template <typename,typename,typename> friend class  detail::index_base;
>   template <typename,typename>          friend class
detail::header_holder;
>   template <typename,typename>          friend class  detail::converter;
Test results for GCC 3.3.2
1 regular index
  10^3 elmts: 141.24%
  10^4 elmts: 147.67%
  10^5 elmts: 152.57%
  space gain: 100.00%
1 sequenced index
  10^3 elmts: 154.99%
  10^4 elmts: 157.43%
  10^5 elmts: 153.71%
  space gain: 100.00%
2 regular indices
  10^3 elmts: 108.23%
  10^4 elmts: 124.78%
  10^5 elmts: 121.79%
  space gain:  90.00%
1 regular index + 1 sequenced index
  10^3 elmts: 123.96%
  10^4 elmts: 137.12%
  10^5 elmts: 145.98%
  space gain:  87.50%
3 regular indices
  10^3 elmts: 100.11%
  10^4 elmts: 119.70%
  10^5 elmts: 129.12%
  space gain:  86.67%
2 regular indices + 1 sequenced index
  10^3 elmts:  99.25%
  10^4 elmts: 113.62%
  10^5 elmts: 116.37%
  space gain:  84.62%
Test results for ICC 8.0
1 regular index
  10^3 elmts: 105.45%
  10^4 elmts: 106.74%
  10^5 elmts: 105.98%
  space gain: 100.00%
1 sequenced index
  10^3 elmts: 112.29%
  10^4 elmts: 112.20%
  10^5 elmts: 111.43%
  space gain: 100.00%
2 regular indices
  10^3 elmts:  63.17%
  10^4 elmts:  67.35%
  10^5 elmts:  71.65%
  space gain:  90.00%
1 regular index + 1 sequenced index
  10^3 elmts:  65.19%
  10^4 elmts:  69.00%
  10^5 elmts:  72.62%
  space gain:  87.50%
3 regular indices
  10^3 elmts:  49.76%
  10^4 elmts:  57.97%
  10^5 elmts:  60.94%
  space gain:  86.67%
2 regular indices + 1 sequenced index
  10^3 elmts:  49.07%
  10^4 elmts:  52.71%
  10^5 elmts:  51.55%
  space gain:  84.62%
I don't have an explanation for the difference.
Best,
Joerg