Am 24.02.2008 um 12:50 schrieb Andre Poenitz:
On Sun, Feb 24, 2008 at 11:52:04AM +0100, Stefan Schimanski wrote:
Am 24.02.2008 um 11:14 schrieb Andre Poenitz:
On Sat, Feb 23, 2008 at 11:33:18PM +0100, Stefan Schimanski wrote:
Hi!
I would like to use the multi_index classes from the boost library.
Unfortunately this is not in the boost version we have in svn. Is
it just
old or do we have only a selection of boost modules?
We only bundle those parts of boost that we actively use, so if you
really need it, we would add it...
However, you'll have a hard time to convince me that it is "really
needed"
without a bit more detailed analysis. I've seen your five(?)
requirements,
yet I've not seen profiler data proving that a "more traditional"
approach is inappropriate.
I fact I very much doubt now that multi_index is the right tool. It
does
not give the log-time random-access I need. It has random-access
iterators
for lists, but they do not use the alphabetic order. I have done some
googling yesterday, but without success to find anything for C++.
It seems
I need my own rb-tree with weights implementation :-/
Have you profile data using a plain std::set? Is it really bad?
Random access is linear with sets. QCompleter needs this, and even in
the case of sorted completions (where a binary search is possible) it
will search the first element matching a prefix which is O(log n)*O(n)
operation then. This is just to find the first element in the popup.
Then following lookups can be accelerated by caching the iterator. But
still, O(n) would be already quite a lot IMO.
But get real numbers, I will implement this version now. Let's see...
Stefan
