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

From: Matthew Hurd (matt_at_[hidden])
Date: 2003-12-02 05:32:48

> On Behalf Of Joaquín Mª López Muñoz
> Subject: Re: [boost] Re: combining maps and vectors -
> creatinginterchangeableversions?
> 
> "Hurd, Matthew" ha escrito:
> 
> > As an aside... in addition to this I often find myself creating two
> > container collections over and over again...
> >
> > The first is a map and hash_map for ordering and fast look up.  The
> > second being a vector for a fast direct repository and other containers
> > for lookup / indexing.
> >
> > There is a container composition / indexing library waiting in those use
> > cases somewhere wanting to fall out...
> >
> 
> 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 :-)

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.

I see this text 
<quote>
Indices
Although indexed_set is planned for future inclusion of several types of
index implementations, currently Boost.IndexedSet only supports so-called
regular indices which mimic the functionality of std::set and std::multiset,
so our discussion will be strictly focused on these. 
</quote>

I see the access complexity for finding is O(log(n)) due to the map usage
which is a price too high to pay for my current excursions.  

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.

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

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 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.

This would meet many of my immediate needs.

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

Regards,

Matt Hurd