[boost] Formal Review: Indexed Set

From: Jeff Garland (jeff_at_[hidden])
Date: 2004-03-27 22:21:13

Let me start by saying thanks to Joaquín for the contribution of this library.
 The amount of effort here is staggering.  I believe this will be a very handy
addition to boost. 

* What is your evaluation of the potential usefulness of the library?
Quite useful -- library provides solution to frequently requiring design
problem with stl collections.  It will effectively replace lots of poorer
hand-coded solutions.

* What is your evaluation of the documentation?
Good. Quite extensive.  I didn't have time to read it all. I also ran
checklink on docs -- no broken links.

* Did you try to use the library?  With what compiler?  Did you have any problems?
Yes.  
Compiled examples and test with gcc 3.3.1 on Mandrake 9.2 against Boost 1.31. 
All tests passed.  
I also successfully wrote some code that uses library.
Only problem was mine.  I was having a 'Pascal' moment -- starting my index at
1 instead of zero ;-)

* How much effort did you put into your evaluation? 
~5 hours spent. Read docs, compiled examples, wrote programs.

* Are you knowledgeable about the problem domain?
Sure, if using standard collections counts ;-)

* What is your evaluation of the design?
Overall the design appears to be quite solid and complete.

* What is your evaluation of the implementation?
Cursory glance thru implementation.  Overall the source seems well organized
and conforms with boost standards. Of course, like many boost libraries
reading the code in this library is a challenge, even though it is well written.  

* Do you think the library should be accepted as a Boost library?  
Yes.

*********
Now for some questions / comments:

1) Dead code in index_node.hpp?

I don't think the ':' is legal below -- I assume this is dead code?

template<typename Super> struct index_node_trampoline:index_node_impl{};

template<typename Super>
struct index_node:Super,index_node_trampoline<Super>
...

2) bidirectional_map

My first interest in this library started when it was just a bi-directional
map.  Now it has become something much broader and more powerful.  Curiously,
the bi-directional map part seems to have taken a back seat -- being pushed
into the examples as an 'exercise for the reader'.

I think that this is unfortunate.  I like to see bidirectional_map as an
official part of the library.  A few reasons for this: 

  a) bidirectional_map will be documented up front as a part of the library.  
  b) For me it is my current primary use of this library -- even though it is
now so flexible I'll have to rethink how I use containers in designs.
  c) Complex code is pushed on the user.  For example, the code below  is from
examples/bimap.cpp

template<typename FromType,typename ToType>
struct bidirectional_map
{
  typedef std::pair<FromType,ToType> value_type;

#if defined(BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS) ||\
    defined(BOOST_MSVC)&&(BOOST_MSVC<1300) ||\
   
defined(BOOST_INTEL_CXX_VERSION)&&defined(_MSC_VER)&&(BOOST_INTEL_CXX_VERSION<=700)

....

It is obvious from this that there are some portability issues.  Putting this
sort of detail on library users is too mcch to expect from users in my opinion.

But it is only a suggestion since it took me all of 5 minutes to pull out the
core of the example to a header file.

3) Serialization support
In future directions you say  "Once Robert Ramey's serialization library gets
accepted into Boost..."

I'd love to see Joaquín at least attempt this soon -- it would serve as an
excellent review of serialization which is upcoming shortly :-)

4) Should the SGI/HP copyrights be included in the source files which are
based off the stl_tree.h implementation?  

5) Naming

For the namespace/library name I suggest boost::multiindex_containers. 

Rationale:
 -- The library provides several stl-like container types (set, list, map) --
hence the plural 'containers'.
 -- The containers all have multiple indexes -- hence multiindex.

I don't have an opinion on the other naming issues.

Jeff