Re: [boost] Re: combining maps and vectors-creatinginterchangeableversions?

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-12-02 10:04:53

Matthew Hurd ha escrito:

> > The second case you mention (several associative containers over the same
> > bundle of elements) is what my library indexed_set is ll about. You
> > can take a look at it at:
> >
> > http://groups.yahoo.com/group/boost/files/indexed_set.zip
>
> Very nice work especially the documentation, but I'm a sucker for bits of
> colour :-)
>

Thanx !

>
> It is half of what I had in mind.  It covers the indexing part for ordered
> traversal, but I wish to hash to access directly on different attributes
> which looks like it might be a straight forward additional to this lib.  I
> guess it is in the scope of the design but not the current implementation.
>
>

Exactly.

> It is good to see it can be extended to other indices, but perhaps this will
> make a bit of a mess of your documentation as the complexity for hashes,
> r-trees or whatever else that might be introduced will be specific to the
> index rather than the index set specification.  So perhaps such
> documentation for the index is orthogonal to the index set itself and the
> complexity specifications of the index set should perhaps be represented in
> terms of aggregates or otherwise of index complexity where appropriate.
>
> I see you mention the hashing in future work.
>

Yep, hashing is considered as a future extension of the library. Internally,
there's a plug'n'play framework designed so that future indices can be
acommodated into the existing code.
As you point out, the introduction of non-regular indices will have a
significant impact on the documentation. Complexity measures would
have to be rewritten in terms of "complexity signatures". Some kind
of concept for what an index is should be defined. This is merely
hinted in the current documentation, as it is rather complex now and
I decided to keep it as concrete as possible while there's no need
to do otherwise.

>
> I find the sentries idea is very compelling.  Interfacing to the signal and
> / or nascent fsm library would be nice with respect to this
>

Thanx again :)

>
> Allowing a type list, or some such, of policies meeting an index concept
> might be the most appropriate where the default policy is just as it is now,
> but perhaps not, as you might wish to add and remove indices at run time...
>
> What are your plans w.r.t. this?

I have not considered adding run-time support, the library is so very
focused in metaprogramming stuff and space&time efficiency.

As for the "index policies", a more or less equivalent scheme is already
implemented. Consider for instance:

typedef indexed_set<
  employee,
  index_list<
    unique<identity<employee> >,
    non_unique<member<employee,std::string,&employee::name> >
  >
> employee_set;

Each element of index_list is an *index specifier*, a kind of policy supplying
the data indexed_set needs in order to assemble all indices into a single
container
(in particular, such a specifier provides info about the node type used
by the index to construct its internal data structure, and the index
implementation
class itself.)

Following this scheme, a hash index would be plugged by writing the appropriate
code and providing a new specifier:

typedef indexed_set<
  employee,
  index_list<
    unique<identity<employee> >,
    non_unique<member<employee,std::string,&employee::name> >,
    hashed<...>
  >
> employee_set;

The ... part in hashed<...> is specific to the index, indexed_set imposes no
condition
on what kind of information the specifier is to be supplied. In most ocassions,
however,
new indices will take advantage of the key extraction utilities provided by the
library,
as in:

hashed<member<employee,int,&employee::id> > // hash by id

> I would be willing to attempt to add an SGI (say STL-PORT) and a dinkum-ware
> based (say vc7.1) hash implementation if you would like to suggest the best
> approach for this and if you'd think this would help rather than hinder you.
>

It certainly woud help! But the task is not trivial. Broadly speaking, you cannot
adapt a preexisting hash_set to indexed_set, instead you'll have to pick up
the code and assemble it into the new index. This is so because indexes normally
do not allocate any memory, it is the orchestrating indexed_set class that does
it --cf regular indices, which do not have any internal std::set doing the work.

I had thought about Matt Austern's hash proposal as a good starting point wrt
to the expected interface --I don't know how close this is to existing hash
implementations, though.

If you feel like doing the work, contact me by private email and we can discuss
this further. Currently I'm working on extending the key extraction framework,
hopefully this will be done before the year ends and I'll upload the library
to the sandbox then.

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo