Boost logo

Boost :

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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at