"Joaquin M Lopez Munoz" <joaquin@tid.es> wrote in message news:loom.20040318T093028-312@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