Re: [boost] Re: indexed_set prerelease 7.0

From: Thomas Wenisch (twenisch_at_[hidden])
Date: 2003-10-30 04:09:10

Hi Volodya,

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

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.

Regards,
-Tom Wenisch
Computer Architecture Lab
Carnegie Mellon University