Boost logo

Boost :

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

I ended up just using a


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.

-Tom Wenisch
Computer Architecture Lab
Carnegie Mellon University

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