Stefan Schimanski wrote:
As I see this here now: this it_ was a first start to improve the
performance of the (long-)words set in the Buffer. This is used to
store the long words for the completion popup. Now the problem are
these requirements:
1. the semantics of a set, i.e. every item shouldn't appear more often
than once.
2. fast (log n should be ok) access to words.begin() + i, i.e. the
i'th element.
3. sorting should be possible
4. fast insertion
5. fast removal
As std::sets are represented as red-black-trees internally, 1,3,4,5
are 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.
Any idea how to solve this?
As nobody seems to know, and it really looks as something fundamental
for data structures: I found some 1995 paper [1] by Chris Okasaki (the
guy who wrote the "Purely functional data structures" book) describing
(Skrew) binary random-access trees. It is more or less what I proposed
with the balanced trees and some weight counting of the branches.
What about my suggestion to use a hash table?
Abdel.
