Re: [boost] [MultiIndex] Why do constructions of multi_indx_base_type<> andmulti_index_node_type<> differ?

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2008-05-23 13:44:52

Grzegorz Jakacki <jakackipub <at> enpoka.com> writes:

> 
> Hello,
> 
> I have a question about implementation details of MultiIndex.
> 
> The type multi_index_base_type<> is created with the metafunction
> nth_layer<>, which in turn uses mpl::eval_if_c<> and mpl::apply2<> to
> build the type by recursion.
> 
> The construction of the type multi_index_node_type<> is very similar,
> but it is implemented in more succinct way using
> mpl::reverse_iter_fold<> and mpl::bind2<>.
> 
> I am trying to find out whether there are reasons to keep the
> more complex construction for multi_index_base_type<>,
> your input will be appreciated.

Hello Greg,

The seemingly superfluous nth_layer stuff was added in Boost 1.33
in order to help reduce the length of the resulting type names
associated with multi_index_container instantiations: some compilers
(notably older versions of MSVC) can choke when symbol names
get too long.

For instance, consider the following instantiation:

  struct employee
  {
    int         id;
    std::string name;
    int         ssnumber;
  };

  typedef multi_index_container<
    employee,
    indexed_by<
      ordered_unique<identity<employee> >,
      ordered_non_unique<member<employee,std::string,&employee::name> >,
      ordered_unique<member<employee,int,&employee::ssnumber> >
    >
  > employee_set;

In Boost 1.32, the type employee_set::nth_index<0>::type
expands to (in GCC):

boost::multi_index::detail::ordered_index<
 boost::multi_index::identity<employee>,
 std::less<employee>,
 boost::multi_index::detail::ordered_index<
   boost::multi_index::member<employee, std::string, &employee::name>,
   std::less<std::string>,
   boost::multi_index::detail::ordered_index<
     boost::multi_index::member<employee, int, &employee::ssnumber>,
     std::less<int>,
     boost::multi_index::detail::index_base<
       employee,
       boost::multi_index::indexed_by<
         boost::multi_index::ordered_unique<
           boost::multi_index::identity<employee>,
           boost::multi_index::detail::null_arg,
boost::multi_index::detail::null_arg
         >,
         boost::multi_index::ordered_non_unique<
           boost::multi_index::member<employee, std::string, &employee::name>,
           boost::multi_index::detail::null_arg,
boost::multi_index::detail::null_arg
         >,
         boost::multi_index::ordered_unique<
           boost::multi_index::member<employee, int, &employee::ssnumber>,
           boost::multi_index::detail::null_arg,
boost::multi_index::detail::null_arg
         >,
         mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
         mpl_::na, mpl_::na, mpl_::na,mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na
       >,
       std::allocator<employee>
     >,
     boost::multi_index::tag<
       mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na,
       mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na,
       mpl_::na, mpl_::na, mpl_::na, mpl_::na
     >,
     boost::multi_index::detail::ordered_unique_tag
   >,
   boost::multi_index::tag<
     mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
     mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
     mpl_::na, mpl_::na
   >,
   boost::multi_index::detail::ordered_non_unique_tag
 >,
 boost::multi_index::tag<
   mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
   mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
   mpl_::na, mpl_::na
  >, boost::multi_index::detail::ordered_unique_tag
>

which is rather long. With the introduction of nth_layer
the same type reduces to:

boost::multi_index::detail::ordered_index<
  boost::multi_index::identity<employee>,
  std::less<employee>,
  boost::multi_index::detail::nth_layer<
    1, employee,
    boost::multi_index::indexed_by<
      boost::multi_index::ordered_unique<
        boost::multi_index::identity<employee>, mpl_::na, mpl_::na
      >, 
      boost::multi_index::ordered_non_unique<
        boost::multi_index::member<employee, std::string, &employee::name>,
mpl_::na, mpl_::na
      >,
      boost::multi_index::ordered_unique<
        boost::multi_index::member<employee, int, &employee::ssnumber>,
mpl_::na, mpl_::na
      >,
      mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
mpl_::na, mpl_::na,
      mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na
    >,
    std::allocator<employee>
  >,
  boost::mpl::vector0<mpl_::na>,
  boost::multi_index::detail::ordered_unique_tag
>

(Not all the reduction comes from the introduction of nth_layer,
though). The key point here is that without nth_layer each
index specifier appears twice, on the indexed_by<> list and
later in the "base" type index_base. nth_layer merely implements
some form of type hiding to prevent this.

Pushing this type hiding idea further the user can for instance
redefine employee_set as:

  struct employee_set_indices:
    indexed_by<
      ordered_unique<identity<employee> >,
      ordered_non_unique<member<employee,std::string,&employee::name> >,
      ordered_unique<member<employee,int,&employee::ssnumber> >
    >
  {};

  typedef multi_index_container<
    employee,
    employee_set_indices
  > employee_set;
  
in which case employee_set::nth_index<0>::type shrinks
to the short and sweet:

boost::multi_index::detail::ordered_index<
  boost::multi_index::identity<employee>,
  std::less<employee>,
  boost::multi_index::detail::nth_layer<
    1, employee,
    employee_set_indices,
    std::allocator<employee>
  >,
  boost::mpl::vector0<mpl_::na>,
  boost::multi_index::detail::ordered_unique_tag
>

More on type hiding at

http://www.boost.org/doc/libs/1_35_0/libs/multi_index/doc/compiler_specifics.html#symbol_reduction

Any particular reason why you're studying the internals
of B.MI? You're certainly a brave folk, as the constructions
inside can be a little messy without any supporting
documentation. Get back if you need further help.

Best regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo