|
|
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?
No.
* 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
performance.
----------------------
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
multimap.)
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
function.
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.)
------
Tutorial:
Rationale:
> STL containers are designed about the concept that each
^^^^^
Unless this is a Queen's English way to phrase it, that should be
"around."
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
^^
in
> 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
^^
on
> corresponding specifier will need additional information: for
^^^^^
. For
> instance, the specifiers unique and non_unique are provided
Tagging:
> If no tag is provided for an index (as it is the case for index
^^^^^
is
> #0 of the previous example), accessing to that index can only
^^^^^^^^^
access
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,
^^^^
do
> while the latter permits them (like std::multiset.)
^^^^^^^
permit
Index types:
> Sequenced indices are modelled after the semantics and
^^^^^^^^
"modeled" is, to my eye, and the ordering given at m-w.com, 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
^^
with
Index types:Regular indices:Key extraction:
> * The whole element serves as the key, as it is the case of the
^^^^^
is
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:
^^^^^^
length
Index types:Regular indices:Comparison predicates:
> These comparison predicates are not different to those used by
^^
from
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].
^^
in
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:
^^^^
we
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:
^^^^^^^^^^^^^^^^^^^
thus
> 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.
^^^
by
------
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
^^^^
of
> convenient notation and the possibility of incurring in
^^^^^^^^^^^^^^^
of
> non-conformances with the standard.
^^^^^^^^^^^^
conformance
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
^^^^^^^
often
Debugging support:
> Boost.IndexedSet safe mode is set by globally defining the
> macro BOOST_INDEXED_SET_ENABLE_INVARIANT_CHECKING. Error
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
BOOST_INDEXED_SET_ENABLE_SAFE_MODE?
Debugging support:
> Warning: Safe mode adds a very important overhead to the
^^^^^^^^^^^^^^^^^^^^^
adds
Simulating standard containers with indexed_set:Simulation of
associative containers:
> an so the substitution rules are:
^^
and
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:
^^^^^^^^^^
occurring
Metaprogramming and indexed_set:MPL analysis:
> An subtle but important distinction exists between
^^
A
Metaprogramming and indexed_set:MPL synthesis:
> Unfortunately, the intantiation syntax of indexed_set is not
> oriented to this sort of tasks:
^^^^^
task
Metaprogramming and indexed_set:MPL synthesis:
> In the example, mpl_index_list<index_list_t> works as a synonim
^^^^^^^
synonym
-- Rob Stewart stewart_at_[hidden] Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk