From: Thomas Wenisch (twenisch_at_[hidden])
Date: 2003-10-30 04:09:10
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.
Computer Architecture Lab
Carnegie Mellon University
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk