Boost logo

Boost :

From: Rob Stewart (stewart_at_[hidden])
Date: 2004-03-29 18:18:39

    * What is your evaluation of the design?

Well conceived, but I dislike the inheritance of index zero's
interface. (More below.)

    * What is your evaluation of the implementation?

The aspects revealed in the documentation are solid. I have not
inspected the code.

    * What is your evaluation of the documentation?

Overall: excellent. Some points later.

    * What is your evaluation of the potential usefulness of the library?

It strikes me as a very useful library. There have been many
occasions when I've handcrafted a solution for which this library
would have sufficed.

Indeed, there is a current class we use daily that provides for a
runtime selectable sorting criteria, but only offers one choice
among several upon instantiation. If the overhead is minimal, it
would be advantageous to use Indexed Set to provide multiple
views of the underlying data as there are clients that want
differing views now.

    * Did you try to use the library? With what compiler? Did you have any problems?


    * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?

I read the documentation pretty carefully over the course of an
hour or two. (As I did it on different days and between other
tasks, I can't say with certainty how much time I spent. Writing
these comments as I went increased the duration as well.)

    * Are you knowledgeable about the problem domain?

Given that I've created ad hoc solutions in the same vein, yes.
However, I have not created a Boosted library, so some aspects
exceed my expertise.

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

Yes, Boost should accept this library.

Documentation Issues.

The main page mentions "STL-like indices," but I don't think of
the Standard Library as providing indices, so this doesn't mean
anything to me.

While it will complicate matters somewhat, I'd prefer to see the
examples written as if "namespace is = boost::indexed_sets" (or
similar) were in effect. That would highlight the functionality
not already in namespace boost.

"Lookup" is only one word when it is used as a noun. When used
as a verb, it is spelled "look up."

The initial discussion of "regular indices" in the tutorial gave
me no idea what they were. Even after the example, I was left
wondering what that "regular index" thing actually was. I didn't
see anything called "regular index" in the example code. It
wasn't until the "Index types" section that I find the definition
of a "regular index."

Your discussion of modify_key doesn't mention any impact on the
Index Set should the new key change the sort order or violate a
unique index.

I didn't find the use of "far pointer" helpful. It connotes the
pointer types germane to segmented memory architectures (old
Intel, for example). Since the only thing you're trying to
convey is that the pointer-like type indexed_set may see chains
to another pointer-like type which may chain to yet another, ad
infinitum, may I suggest "chained pointer" instead?

Your "safe mode" name is inconsistent with the
"invariant-checking mode." The latter clearly indicates what is
being checked, whereas the other doesn't. I expected that "safe
mode" would be a superset, but it is orthogonal. How about
naming it "precondition-checking mode?" A related issue is that
you say that invariant-checking can be turned on separately from
"safe mode" and that the former indicates an internal error.
However, I don't see how you can assert that the failure to
maintain an invariant is an internal error if you don't ensure
the preconditions were met. IOW, shouldn't turning on
invariant-checking mode imply turning on precondition-checking?

In Debugging support:Invariant-checking mode, in the advanced
topics page, you write:

> It is recommended that users of Boost.IndexedSet always set the
> invariant-checking mode. By default (i.e. if the user has not
> provided a definition for BOOST_INDEXED_SET_INVARIANT_ASSERT),
> this mode will not perform any check at all in NDEBUG builds,
> but it does not have a significant impact in the compiled
> binary either, so you need not set off invariant-checking for
> release compilations.

I have two questions. First, why is this information buried in
the advanced topics page? The mode should be highlighted in the
main documentation path. Second, if the overhead is so small,
why not leave it on by default in all builds and then give users
a means to disable it? Users can then decide whether to disable
it in all builds or only release builds.

Both the tutorial and the advanced topics pages claim
indexed_set's simulation of std::set, for example, is as
efficient as the real thing, yet the performance page shows a
10-20% overhead. You should qualify your claims of equal
performance such that you say indexed_set has "nearly" as good

Naming Issues.

I, too, find "mix" too cute, so "multi_container" is better, but
that is rather indicative of implementation and doesn't clearly
convey the idea of multiply indexing data. Thus, I'm in favor
of "multi_index," but the most recent "multi-index container"
notion may be the best course to remove all confusion.

I don't like the "non_unique" stuff. I wonder whether it could
be dropped altogether, leaving "unique" as a modifier when that
property is present. Otherwise, how about "dup" (short for
duplicate, in case it wasn't obvious) as a modifier? (You could
also use "multi" to mirror the idea behind multiset and

I think that "get<>" should be named "get_index<>" as that it
will read better in use:

   ... = es.get_index<1>();

"member" and "const_mem_fun" seem to overlap based soley on the
names. I suggest that "member" be renamed "data_member" to avoid
confusion regarding the use of "member" to invoke a member

From: Joaquin M Lopez Munoz <joaquin_at_[hidden]>
> I think I have something that may please everybody:
> template<int N> struct nth_index;
> template<typename Tag> struct index;
> template<int N> struct nth_index_iterator;
> template<int N> struct nth_index_const_iterator;
> template<typename Tag> struct index_iterator;
> template<typename Tag> struct index_const_iterator;

I like that approach.

Design Issues

I don't really like that index 0 is the default behavior. I'd
rather an Index Set not behave like any of its indexes. Yes that
means you must say get(_index)<0>() when you want the first
index, but I like the idea of that being explicit. There's no
opportunity to change a typedef from std::list, for example, to
boost::indexed_set and silently use the wrong index or silently
change the complexities. I don't see indexed_set as a drop-in
replacement for existing types, so I don't want it to be easy to
do that.

I don't like the assymmetry between get<> and the pair
nth_indexed_type<> and indexed_type<>. I'd prefer that
indexed_type<> be used, like get<>, for either a number or a tag.

Why does tag<> accept multiple "names?" Is there a motivating
example for why a single name isn't sufficient? I ask because
the class is more complicated than it otherwise needs to be.
That translates into more documentation to explain it and longer
-- by however much -- compilation times.

Documentation Nitpicks

(Sorry, no diffs.)


> STL containers are designed about the concept that each
Unless this is a Queen's English way to phrase it, that should be

Introduction:Multiple sorts on a single set:
print_out_by_name() in the example code has a comment referencing
"i" which should reference "name_index" instead.

A bidirectional list with fast lookup:
> When performance is a concern, we will need an additional data
> structure that indexes the elements in tc, presumably by

> alphabetical order. Boost.IndexedSet allows precisely to do
does precisely

> this through the combination of sequenced and regular indices:

A bidirectional list with fast lookup:
> Now, occurrences and delete_word have logarithmic
> complexity. The programmer can use index #0 for accessing the
> text as with std::list, and resort to index #1 when logarithmic

>From the context, the reader may read that as "sort again" rather
than "fall back on." I suggest changing "resort to" to "use" to
avoid the confusion.

Index specification:
> In general, we can specify an arbitrary number of indices: each
> of the arguments of index_list is called an index
> specifier. Depending of the type of index being specified, the

> corresponding specifier will need additional information: for
. For

> instance, the specifiers unique and non_unique are provided

> If no tag is provided for an index (as it is the case for index

> #0 of the previous example), accessing to that index can only

Index types:
> Regular indices, which sorts the elements like std::sets do,
> and provide a similar interface. There are unique and

Change to, "Regular indices sort their elements like std::sets do
and provide a similar interface."

> non-unique variants: the former does not allow for duplicates,

> while the latter permits them (like std::multiset.)

Index types:
> Sequenced indices are modelled after the semantics and
"modeled" is, to my eye, and the ordering given at, the
more normal spelling. YMMV.

Index types:Regular indices:Unique and non-unique variants:
> For instance, if we augment employee to include an additional
> member for the Social Security number, which is reasonably
> enough to be treated as unique, the following captures this

Either, "which is reasonably treated as unique," or, "which is
reasonable enought to treat as unique."

Index types:Regular indices:Specification:
> The first optional argument is used if tags are associated to

Index types:Regular indices:Key extraction:
> * The whole element serves as the key, as it is the case of the

Index types:Regular indices:Key extraction:
> specifies by means of identity that the whole element objects
element objects themselves

Index types:Regular indices:Key extraction:
> Consider the following extension of our example where sorting
> on the third index is based upon the lenght of the name field:

Index types:Regular indices:Comparison predicates:
> These comparison predicates are not different to those used by

Index types:Regular indices:Special lookup operations:
> Regular STL containers fail to provide this functionality,
> which often leads to inelegant workarounds: consider for
> instance the problem of determining the employees whose IDs
> fall on the range [0,100].

Index types:Regular indices:Special lookup operations:
> and write now the search as
now write

Index types:Regular indices:Special lookup operations:
> Here were are not only passing IDs instead of employee objects:

Index types:Regular indices:Updating:
> Updating is a powerful capability not provided by standard STL
> containers, and one that comes specially handy when strong
is especially

> In the case of update, the original value is kept and the
> method returns without altering the container, but modify
> cannot afford such approach, since the modifying functor leaves
such an

> no trace of the previous value of the element. Integrity
> constraints considerations thus lead to the following policy:

> when a collision happens in the process of calling modify, the
> element is erased and the method returns false. This difference
> in behavior between update and modify has to be considered by
> the programmer on a case-per-case basis.

Boost.IndexedSet Advanced topics:

Advanced features of Boost.IndexedSet key extractors:
> The Key Extractor concept allows for a same object being a key
> extractor from several different types, possibly through
> suitably defined overloads of operator():

If I understand what you meant, this makes more sense:

The Key Extractor concept allows the same object to extract keys
from several different types, possibly through suitably defined
overloads of operator():

Use of member_offset:
> In these cases, a replacement utility member_offset has been
> provided that does the work of member at the expense of a less

> convenient notation and the possibility of incurring in

> non-conformances with the standard.

Debugging support:
> C++ does not enjoy direct support for Design by Contract
> techniques: these are customarily implemented as assertion
> code, oftenly turned off in release mode for performance


Debugging support:
> Boost.IndexedSet safe mode is set by globally defining the

Debugging support:
> Warning: Safe mode adds a very important overhead to the

Simulating standard containers with indexed_set:Simulation of
associative containers:
> an so the substitution rules are:

Metaprogramming and indexed_set:MPL analysis:
> Given an indexed_set instantiation, the following nested types
> are provided for compile-time inspection of the various types
> concurring in the definition of the indexed_set:

Metaprogramming and indexed_set:MPL analysis:
> An subtle but important distinction exists between

Metaprogramming and indexed_set:MPL synthesis:
> Unfortunately, the intantiation syntax of indexed_set is not
> oriented to this sort of tasks:

Metaprogramming and indexed_set:MPL synthesis:
> In the example, mpl_index_list<index_list_t> works as a synonim

Rob Stewart                           stewart_at_[hidden]
Software Engineer           
Susquehanna International Group, LLP  using std::disclaimer;

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