Re: [boost] Formal Review: Indexed Set

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2004-03-23 15:40:48

Hello,

> The review of Indexed Set library, written by
> Joaquín M López Muñoz starts today (March 20)
> and runs for 10 days.
>
> Latest version (9.4) of the library is available on:
> http://groups.yahoo.com/group/boost/files/indexed_set.zip
> (328 kB)

Downloaded and installed it sucessfully.

> What it is?
>   indexed_set is generic, STL compliant container
>   providing one or more views

I still regard these views more as indices, because they are populated at
insertion time IIUC.

> on its data. These views
>   allow to use data sorted according to different criteria.
>   Change in container data is automatically
>   propagated into all views.
>
>   How many views and what ordering is applied is
>   specified in declarative way, as template parameter.

This I like.

> What it is good for?
>   - it can replace multiple collections of data and
>     hand-written code keeping them in sync.
>   - it can replace standard containers (as std::set or
>     std::list) if these may not meet future reqirements.
>   - it can serve as basic for other libraries.
>     For example RTL (relational tables library) may use
>     indexed_set to hold its data.

To try it out I ported the example from
http://www.cs.rpi.edu/~musser/stl-book/source/ex18-01.cpp.txt to use
indexed_set<>. Port attached. I didn't see a performance penalty. But the
test could be IO bound and I didn't profile.

> Other features of indexed_set:
>   - sorting can be performed on result of member function
>     (similar to calculated indexes in RDBMS).
>   - indexed_set can be used as 'wrapper' over other data
>     structures, e.g you can see data in std::vector
>     as being sorted in set-like structure (but without
>     structures being synchronized).
>   - many, many others ...

I miserably failed to define a composite unique key for my indexed_set.
Should this be possible? One more question: is there an (easy?) way to
iterate over the distinct values of an index (or to define the index as the
set of distinct values of the related attribute(s))?

> Future development:
>   - planned functionality is described on its own page
>     in documentation.
>   - indexed_set may also implement access to its data
>     in the same way as std::deque, with random O(1) access

I'd have to do much more homework to understand the current version.

> History of the project:
>   - it started as 'bimap' library more than year ago,
>   - some two dozen iterations were released,
>   - several Boost people expressed their interest
>     or did suggest features.

Good that they did.

> Boost-wide reusable parts of the library:
>   - indexed_set includes (nearly verbatim) copy
>     of Andrei Alexandresu ScopeGuard. It is intended
>     as stop-gap until Boost wide library emerges.
>   - maybe auto_space.hpp can be liften into utilities.

Hm.

> Portability:
>   - see document page for list of compilers and their issues
>   - Can someone try to run tests under release mode of VC 6.5?
>     We got different results with different machines.

Still somebody developing for that compiler? Incredible.

> Word from the autor:
>   "Thank you for reviewing indexed_set. There are several
>   points, mostly concerning naming, that I'd like to be discussed
>   during the review. You can find these at the URL
>
>   http://groups.yahoo.com/group/boost/files/indexed_set_review_notes.html
>
>   If you evaluate the library and deem it acceptable for
>   Boost,

Yes, I do.

> please walk the extra mile and express your opinions
>   about the issues brought forward in the review notes.
>   Naming issues are quite sensitive, and I'd like to reach
>   as general a consensus as possible."

If Joaquín is going to invent indexed_map, too, then indexed_set is OK.
Otherwise we seem to be working with something like an indexed_table or
table IMHO. Namespace boost would be OK for me. Regular indices are OK,
because I didn't need sequenced ones until now ;-). Ordered_(non)_unique
would be OK to resolve the std:: name clash, but no strong preference here.

No opinion regarding nth_index_type and update/modify/replace. No problem
with header dependencies.

Best regards,
Joerg