Boost logo

Boost :

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:

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

namespace boost
   namespace mpl

     template <> struct has_key_impl <aux::set_tag >
       template < typename Set, typename T > struct apply
# 47
       : bool_ <
          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:

Boost list run by bdawes at, gregod at, cpdaniel at, john at