[boost] Re: Is there any interest in this container?

From: David B. Held (dheld_at_[hidden])
Date: 2004-03-18 05:50:46

"Joaquin M Lopez Munoz" <joaquin_at_[hidden]> wrote in message
news:loom.20040318T093028-312_at_post.gmane.org...
> [...]
> I guess I'm not fully understanding the use case.

As one poster mentioned, it has to do with GUIs.  Although I've
used this structure in non-GUI contexts, the original motivation
was the back-end of a Win32 ListView.  I had an application
where data was being inserted continuously (not at a high rate,
but high enough that I didn't want O(N) insert).  The data had to
be sorted, and you needed to be able to jump to any arbitrary
point in the data and start iterating, without doing an O(N) scan.
That's because a virtual ListView will let you scroll to any point
in the list, and pass a linear index at which you must start dumping
items.  So if you have a listview with 3,000 items, the user could
scroll to item 2,500, at which point your data structure must be
able to deliver a screenful of data beginning with that index.  So
my solution was to modify std::map (since it already had the
sorting invariant and reasonably fast insert) so that you got an
O(log n) indexed lookup.  Once you get the first lookup, you can
just iterate for the remaining display elements (amortized
constant).

In fact, any time you want to present a large list of sorted data to a
user (consider a client/server scenario, for instance), and the user
can request data beginning at a certain ordinal index, the "rank
tree" (as Rene calls it) is a useful structure to have.  For instance,
imagine a client that can browse a remote table of thousands of
employee records that the server has cached in memory.  Suppose
the client displays 100 records per page, and the user says: "Let
me see page 30".  If you only have one client, it would not be
unreasonable for the server to do a linear search to record 3,000.
If you have 50 clients, that linear search starts to look pretty bad,
and the O(log n) ordinal/rank search starts to look pretty good.
Does that help?

Dave

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.581 / Virus Database: 368 - Release Date: 2/9/2004