[boost] [documentation]Need for "programmar's guide" or "tech notes"

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-01-07 11:51:51

Periodically, and probably inevitably, someone thinks of a possibly
better way to do something in a boost library.  For example, I
recently got the "brilliant" idea to maybe use inheritance to check
whether an item was already in an mpl::set and thus reducing, what I
assumed, was at least a linear time complexity for the has_key
metafunction.  Although:

http://www.boost.org/libs/mpl/doc/refmanual/has-key.html

claims "Amortized constant time" complexity, I assumed the compiler
has to do a linear lookup at least once for each has_key
instantiation.  After that, for each occurrence of the has_key with
the same template arguments, I guess the compiler has a constant time
(using a hash map?) method for finding the instantiation.  Anyhow,
that was my motivation.

The basic idea idea was to use inherit2<Member,TailSet> where Member
was the Member to be inserted into a set, and TailSet was the members
inserted before Member.  Then has_key would simply use type_traits
is_base_of<Member,TailSet> to see if Member was a member of TailSet
before doing the insertion.  If it was already a member, the just
return TailSet, if not, then return inherit2<Member,TailSet>.

Of course, before starting to code, I thought it might be a good idea
to see how mpl currently implemented the associative containers in
case this idea was already being used :) However, when I looked at the
mpl code to try to understand the the implementation, I got lost.  For
example, the output from cpp produces:

# 25 
"/home/evansl/prog_dev/boost-cvs/ro/boost/boost/mpl/set/aux_/has_key_impl.hpp" 
2

namespace boost
{
   namespace mpl
   {

     template <> struct has_key_impl <aux::set_tag >
     {
       template < typename Set, typename T > struct apply
# 47 
"/home/evansl/prog_dev/boost-cvs/ro/boost/boost/mpl/set/aux_/has_key_impl.hpp"
       : bool_ <
        (sizeof
         (Set::
          is_masked_ (aux::ptr_to_ref (static_cast < Set * >(0)),
                      static_cast < aux::type_wrapper < T > *>(0))) ==
         sizeof (aux::no_tag)) >
       {

       };
     };

   }
}
# 19 
"/home/evansl/prog_dev/boost-cvs/ro/boost/boost/mpl/set/aux_/at_impl.hpp" 2

I couldn't figure out the purpose of static_cast or Set:: is_masked_ ;
however, it seemed there was no counterpart to inherit2; so, I assumed
I wasn't reinventing the wheel (of course I "conveniently" didn't
notice that apparently no linear time complexity was involved).  So, I
forged ahead an implemented it ; however, I then realized that
has_key<inhert2<Member,TailSet>,TailSet> would return true since
TailSet was a supertype :( OK, so then I thought maybe using the
template argument deduction method in section 9.10 of _C++ Template
Metaprogramming_ (alias _C++TMP_) would avoid this.  That's now in the
boost vault under the "Template Metaprogramming" directory.

Then I thought again.  Using _C++TMP_ section 9.10 used a static_cast
also; so I looked further in the cpp output and found:

       static aux::no_tag is_masked_ (s_item const &,
                                     aux::type_wrapper < T > *);

and OOPS!, it was looking more like I'd reinvented the wheel after all
:( (I'm not totally sure, but it looks like that's what was
done. Please let me know if that's wrong.)

A "programmer's manual" describing, at least briefly, the
implementation, would help future redesigners find their way and avoid
the pain of reinventing yet another wheel.  This was called "technical
notes" before:

http://archives.free.net.ph/message/20051006.180034.8cd1ece3.en.html