Re: [boost] Re: indexed_set prerelease 7.0

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-10-30 05:57:04

Hi Thomas,

> On Thu, 30 Oct 2003, Vladimir Prus wrote:
> > some time ago I wrote a class called numbered_set. It was like a set (i.e
> > efficiently checked for duplicates) but had additional integer index, so
> > that all elements could be obtained by the index in constant time.
>
> Is your numbered_set code available somewhere?

I've put it to 

     http://zigzag.cs.msu.su:7813/numbered_set.h

Usual disclaimers apply ;-) It has not docs, and might not work everywhere. 
OTOH, it works with gcc 3.3 (it's still used in my project) and has quite 
small interface so lack of docs should not be a problem.

> I was recently looking for a beast similar, but not exactly the same as
> the numbered_set you describe.  Basically, I wanted an "Sequence Set".  I
> want Sequence-like iteration and insertion/removal behavior, but I want
> O(log n) search.  I also want to maintain the invariant that a
> particular value appears only once in the set.  

Looks very similiar to what I wanted.

> Basically, I wanted a
> shift register which I could efficiently search, with no duplicate
> values.
>
> I ended up just using a
>
>   list<ValueType>
>
> and manually updating a
>
>   map< ValueType, list<ValueType>::iterator >
>
> whenever I changed the list.  Obviously, it would be better to write a
> container that maintained the map for me "under the hood".

Again, seems very similiar. Only in my case it's vector<ValueType> and 
hash_set for tracking duplicates.

> Can I accomplish this with numbered_set?  Does some other container or
> container adapter in Boost do this?  My impression is that indexed_set is
> not what I want, since it is not a Sequence.

I hope Joaquín will tell about indexed_set. If indexed_set is not suitable, 
numbered_set might help.

- Volodya