Jeremy Maitin-Shepard wrote:

This seems like a useful data structure, although I can't think of any specific use cases.

I use such a data structure right... keeping track of a GUI list that can have items inserted/removed in it. A regular number->item map doesn't work as it has to change the index of items on inserts/deletes.

I am assuming you are implementing it as a balanced binary tree where you keep track of the number of nodes in the subtree rooted at each node. (This allows finding a node by its numeric index in time.)

That is how I implemented it. The data structure is called a "rank tree", describe in the white book. I've mentioned the structure in this list before :-) -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq

Matthew Vogt wrote:

Rene Rivera <grafik.list <at> redshift-software.com> writes:

...

That is how I implemented it. The data structure is called a "rank tree", describe in the white book. I've mentioned the structure in this list before

What is the 'white book'? Is this the standard reference for structures in this area?

Somewhat standard in that it's used in most CS schools. Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest ISBN 0-262-03141-8 -- ISBN 0-07-013143-0 Second edition at... http://www.bookpool.com/.x/n5753dkkj4/sm/0262032937 Bookpool: Introduction to Algorithms, 2nd Edition Peter mentioned to me privately that the 1st edition is available online. Peter care to provide a link to it? PS. And since Peter also asked, and before more people ask. The description I refer to is in section 15.1 of the first edition. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq

"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:4057E121.8080207@redshift-software.com...

[...] That is how I implemented it. The data structure is called a "rank tree", describe in the white book. [...]

Hmm...DADS doesn't have it, and I have found that to be a most exhaustive and authoritative source: http://www.nist.gov/dads/ 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

Peter Palotas wrote:

That actually sounds pretty much what I was looking for. However I can't seem to find the source in the sandbox (using the web interface). Haven't poked around there before so maybe I'm just stupid, but I can't find the actual header-file in http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/libs/map/

Where can I find it? And how stable/complete is your implementation?

The headers are like in the regular Boost: ../boost-sandbox/boost/* I look at the implementation and it doesn't do what a rank tree does. It does make it easier to base a rank tree implementation against it. The part that is missing is keeping track of the rank of nodes as the tree changes, the constant time op, that lets one have the logN ops later on. [ Unless I missed something -- So correct me at will ;-) ] To David... It also looks to me that there is a much better way to support the custom index aspect of assoc containers with something I thought about recently, tuple_adaptor... The idea is to have a tuple compatible interface that can access a subset of a larger structure. You can then use the tuple adaptor as the comparison/index. Basically abstracting out the "index" like functionality you have. Here are some notes I made up about it last week...

...

...

...

tuple_adaptor, provides the boost::tuple interface, and types, given an existing structure and some of it's members. For example having this exiting structure:

struct data_op { int number; bool flag; std::string name; }; typedef tuple_adaptor<data_op,&data_op::number,&data_op::flag,&data_op::name> data_op_tuple; data_op_tuple x(1,false,"foo"); x.flag = true; x.get<0>() = 13; This facilitates adapting existing types for use in algorithms that take tuples. Another option this opens is proving a subset tuple interface to a large structure, for example: typedef tuple_adaptor<data_op,&data_op::number,&data_op::name> data_op_tuple_2; <<<< -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq

David B. Held wrote:

"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:4058C84D.2000008@redshift-software.com...

...

[...] I look at the implementation and it doesn't do what a rank tree does. It does make it easier to base a rank tree implementation against it. The part that is missing is keeping track of the rank of nodes as the tree changes, the constant time op, that lets one have the logN ops later on. [ Unless I missed something -- So correct me at will ;-) ]

Hmm...are you sure? Did you look at the rotate_right() and rotate_left() functions? The "indexes" wouldn't be correct if you didn't adjust them on insert/delete. Essentially, what I call "index" is probably what you call "rank".

No I wasn't sure, hence why I said I may have missed something ;-) Yes you are correct it does have the functionality. It still took me a while to find the exact place even with your hint above, IndexedNode rotate* and update*, that has the count.

does. You might want to take a closer look at that if you haven't already. I probably will soon so I can give it a thorough review.

Will do :-) -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq

David B. Held <dheld <at> codelogicconsulting.com> writes:

"Peter Palotas" <peter <at> smartbusiness.nu> wrote in message news:auto-000000364385 <at> statement.se...

...

I was wondering if there is any interest in a container that is a model of sequence (just like std::vector or std::list) and with an interface matching that of std::vector (maybe with minor differences due to effiency) but with different time complexities? [...]

Take a look at the policy-based map in the sandbox. I implement what I called "indexed nodes" which appear to give the complexity characteristics you describe. I'm not sure whether the indexed_set library soon to be reviewed also supports this feature or not, but given all the other features it has, I would be suprised if it didn't. ;)

Well, currently indexed_set does not have such an index type, although it could be probably implemented with relative ease. But I fail to see what this type of structure is useful for. From what I've read on this thread, the main reason one could want to have operator[] is that it allows the programmer to store the index of an element for later retrieval. But this can be also accomplished (and with better performance) if we store an iterator or a reference to the element instead. I guess I'm not fully understanding the use case. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

David B. Held <dheld <at> codelogicconsulting.com> writes: [...]

In fact, any time you want to present a large list of sorted data to a user [...] Does that help?

Yes it does. But then I think we are talking about two different data structures here: * Yours: A sorted container with ordinal-based access. * Peter's: A list-like container with ordinal-based access. Am I right about this? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

On 18. Mar 2004, at 11:50, David B. Held wrote:

...

[...] I guess I'm not fully understanding the use case. [...] 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.

I had a similar problem myself, but I found that the slower (lg N) lookup time (even though iteration from that point was linear) did not make up for the faster insertion, because, most of the time I used the lookup methods -- and in your listview example, I would think the same is the case in 99% of the applications I can envision. Similar with the client/server example, since the 3,000 clients only fetch data from the database as I understood it. My problem was that insertions could come in bursts, and could e.g. all go to the start of the container -- my solution was to create a cache or insertion queue (in lack of a better name), to which items were initially added, and lookup would take this queue into consideration. The queue was of fixed size and flushed (in O(n) time) when it was full. Basically giving me the same theoretical time complexities as only using a vector, but in practice making insertion of m items significantly faster. -- http://www.diku.dk/hjemmesider/studerende/duff/