Am 22.02.2008 um 00:56 schrieb Pavel Sanda:
easy. But 2 is not supported as far as I could see. Without knowing
the
implementation details, I wonder why. It wouldn't be hard to put
"counters"
into the nodes of the red-black-tree, which count the number of
children.
But it seems this is not implemented.
why it should be supported - isnt it in the nature of "set" the
elements are
in no particular order and to offer i-th member API just because set
is implemented
by rb-tree is imho no good design.
Well, the set is a sorted container by definition, see here:
http://www.sgi.com/tech/stl/set.html
unfortunately i'm not aware of any standard stl class offering
just 'balanced tree' api which would be enough for your requirements
(namely 2).
btw why we need (2)?
The completion popup accesses this containter in a random access way.
Though probably it would be enough to speed up the first access (e.g.
for the first line in the popup). The following accesses will be very
near to the first one, hence the simple iterators can be used here.
My first idea would be to use two maps:
- one std::map<docstring, size_t> sorted by string (to make the lookup
by string fast)
- and std::map<size_t, docstring> sorted by position in the first map
(to make the random access lookup fast).
Stefan
