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

From: Hurd, Matthew (hurdm_at_[hidden])
Date: 2003-12-02 16:52:51

> On Behalf Of Joaquín Mª López Muñoz
> Subject: Re: [boost] Re: combining maps and vectors-
> creatinginterchangeableversions?
> 
> Matthew Hurd ha escrito:
> 

<snip>

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

Fair enough.  Almost invariably (is that code for "mostly", or always, but just in case I'm wrong...) my code represents a compiled schema and the run-time configuration of such is not important.  So the approach makes sense to me.

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

Cool.  I should tackle writing this.

> 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 also think that providing support for hashes on ordered indices would be preferred where you want to trade space for time in extracting bounded ranges.  This is similar, in some respects, to the first use case I mentioned in the original mail.

So, something like...

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

Then you're only a step away from compile time index complexity and capability traits and compile time query optimisation taking advantage of available indices ;-)

Then all you need then is the autoselection of indices and containers based on explicit time and space complexity requirements or the use cases derived from instantiation. Let the best container / index win ;-)  This nirvana is something I've thought about for a long time and I certainly see index_step as a nice step along this long long long term, perhaps impossible, direction.

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

When I read the Matt Austern proposal, quite a while ago now, I seem to remember the conclusion being more of a review than a specification, but my thinking on this thinking is probably the wrong thinking, I think ;-)  I don't remember what was done w.r.t. the issue of forward and bi-directional iterators being used by the SGI and dinkumware libraries respectively.  I'll revisit it to clear the haze.

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

Sounds fun.  I'll try extending it. I will contact you off line.

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

Regards,

Matt Hurd
_______________________

Susquehanna Pacific P/L
hurdm_at_[hidden]
+61.2.8226.5029
_______________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.