[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-core-devel
Subject:    Re: KConfig sucks :-)
From:       Michael Matz <matz () kde ! org>
Date:       2001-08-30 6:27:21
[Download RAW message or body]

Hi,

On Wed, 29 Aug 2001, Waldo Bastian wrote:

> While I was debugging the mysterious non-working localisation I noticed that
> we use a QMap to store all entries (no surprise there) but since we write out
> the entries in order, most of the time we read the entries back in order as
> well, which means that effectively our QMap becomes a linked list and we get
> O(N) behaviour instead of O(log N).

Although I'm not exactly sure, what operation should be O(N):
What makes you think, that filling a QMap in a sorted manner makes
operations on that QMap be O(N) (compared to filling it randomly).
Internally a Red-Black tree is used, which is balanced, which by
definition can't degenerate into a linked list.


Ciao,
Michael.

[prev in list] [next in list] [prev in thread] [next in thread]