I'm looking for a data structure

I assume requirement 2 is a no-brainer. Keeping track of the number of items is a sinch.

For 1, 3 and 4, is it really that you need access to the Nth element, or is it sufficient to simply access an element whose key is some integer cookie value?

By the way, I'm yet to be convinced that a skip-list is the best option in any circumstance, in practice. A self-balancing binary-tree beats a skip-list every time, if you ask me.
In this case, some kind of self-balancing binary-tree where each node additionally stored how many nodes were below it would seem to work. Of course it'd mean implementing the data structure yourself though, which probably means it's a bad idea. Oh and a second tree or hash-table for the reverse lookup.

[Edited by - iMalc on February 11, 2009 12:17:02 AM]

std::map or similar.

Quote:

Original post by iMalc I assume requirement 2 is a no-brainer. Keeping track of the number of items is a sinch. For 1, 3 and 4, is it really that you need access to the Nth element, or is it sufficient to simply access an element whose key is some integer cookie value?

Let's make the problem concrete. I think this has all of the features I need...

You have a list of elements (which are unique), and a scroll view of the elements.

You need to be able to access quickly the nth through n+mth elements.

You need to be able to locate an element in the list by index.

You need to be able to delete elements from the list efficiently at any location, by either index or by element.

You need to be able to determine what fraction of the elements are being viewed, and at what fraction you are at.

Most naive implementations have horrible behaviour when you have a 100,000 to 1 million+ entry list, and you proceed to delete ~10% of them (distributed semi-randomly). A vector/deque with fast random-access to the nth element costs O(n^2) time. A map/set etc has O(nlgn) time for this, but you cannot get reliable indexes out of that collection.

Quote:

By the way, I'm yet to be convinced that a skip-list is the best option in any circumstance, in practice. A self-balancing binary-tree beats a skip-list every time, if you ask me.

*nod*, but writing skip-lists is easier than writing red-black trees. Writing "rotate", for example, would be a bit of a bitch when you also have to keep track of the count of elements along each branch. Skip lists ... well, what has to be done is relatively obvious.

Quote:

In this case, some kind of self-balancing binary-tree where each node additionally stored how many nodes were below it would seem to work. Of course it'd mean implementing the data structure yourself though, which probably means it's a bad idea. Oh and a second tree or hash-table for the reverse lookup.

Yes -- if you have persistant iterators into the first structure, you the reverse lookup is semi-easy, just annoying. As it happens, the boost multi index implementation happens to solve that annoyance, and do it more efficiently than the naive method.

And no, a std::map doesn't give you access to the nth element.

Quote:

Original post by NotAYakk Quote: By the way, I'm yet to be convinced that a skip-list is the best option in any circumstance, in practice. A self-balancing binary-tree beats a skip-list every time, if you ask me. *nod*, but writing skip-lists is easier than writing red-black trees. Writing "rotate", for example, would be a bit of a bitch when you also have to keep track of the count of elements along each branch. Skip lists ... well, what has to be done is relatively obvious.

Yes I had worked out that rotations would need to manipulate the counts that that they would certainly require some thought.
I certainly agree that a skip-list would be easier to implement.
In any case though, I think I understand your requirements exactly now, and I'll see if I can think of a good solution (that involves writing rather little code) over the course of today.

Quote:

Original post by NotAYakk An ordered collection of elements, where the order is determined by the user of the collection, not the properties of the elements. Fast access of nth element by the parameter n. Fast length(). Fast deletion of nth element by the parameter n. Fast insertion of nth element by the parameter n. Fast reverse-lookup of (element) to (location) (or persistent iterators, either works). And lg(n) is fast enough.

Sounds like std::set to me. (What you call "reverse lookup" is provided by .find().) Except for the access-of-nth element. You could re-implement std::set and store a "number of children" count in each node; tree balancing operations would be slowed by a constant factor (so you still get logarithmic deletion, insertion and lookup, and constant size stored in the root node), and nth-element access could be written easily enough too (and would easily be demonstrated to be logarithmic).

Although I'm having difficulty imagining why you have these requirements. In particular, "access of nth element" at all is actually kind of a red flag for me.

Quote:

Original post by Zahlman Sounds like std::set to me. (What you call "reverse lookup" is provided by .find().) Except for the access-of-nth element. You could re-implement std::set and store a "number of children" count in each node; tree balancing operations would be slowed by a constant factor (so you still get logarithmic deletion, insertion and lookup, and constant size stored in the root node), and nth-element access could be written easily enough too (and would easily be demonstrated to be logarithmic). Although I'm having difficulty imagining why you have these requirements. In particular, "access of nth element" at all is actually kind of a red flag for me.

That all mirrors my thoughts exactly.

As this sounds somewhat like the container behind some custom listview type of object, rather than looking up items by index, I suggest keeping track of an iterator to the first visible item. As the number of visible items is always a relatively small number (typically less than about 50), then a std::advance from there to even the last item visible isn't so bad.
Insertion or deletion from any visible point is also just as easy, you again use std::advance.
Surely you don't need to be able to delete an item from a completely arbitrary position, but instead only need to delete one that is in view?
Container indexes need then not come into it at all.

Or putting it another way, "It's not what your container can do for you, but what you can do for your container!"

[Edited by - iMalc on February 12, 2009 12:38:17 AM]

In that case, you'd still need to be able to scroll randomly to the X% of the model, and you'd need to know at what percentage of the model you are at.

Both require access-by-nth.

On top of that, in the even that some other view deletes items from your model, you need to be able to decide what is in your view.

Think a list of 1 million+ items, a view at some random (say, at 830,000) offset into it. Some random element is deleted. Then you switch your view to the 20 items visible from the 27% mark of the list by grabbing the scroll bar.

I don't think that calling advance 270,000 times is the right answer.

And yes, I can reimplement a red-black tree where each node keeps track of what the number of nodes under it is. Writing red-black trees flawlessly sucks.

Is the only boost multi_index with "get nth" operators (like at and []) access random_access_index? It does look like I'm doomed to either punt or roll my own.

There is an implementation of an augmented interval tree here. It modifies the rb tree code that underlies both the gnu stdlib std::set and std::map structures (note licensing though you adapt stlport version). To get the interval properties it adds a single extra node element recording the maximum value across the nodes below it and preserves this through the tree rotations. This additional max node value then permits effecient traversal/iteration of overlapping intervals. I cant quite envisage how you might go about recording an n/accumulated position (If i understand the problem correctly) but working from a known good starting point like stl_tree.h might be easier than starting from scratch.

Quote:

Original post by NotAYakk In that case, you'd still need to be able to scroll randomly to the X% of the model, and you'd need to know at what percentage of the model you are at. Both require access-by-nth. On top of that, in the even that some other view deletes items from your model, you need to be able to decide what is in your view. Think a list of 1 million+ items, a view at some random (say, at 830,000) offset into it. Some random element is deleted. Then you switch your view to the 20 items visible from the 27% mark of the list by grabbing the scroll bar. I don't think that calling advance 270,000 times is the right answer.

It's not that you'd call advance 270000 times, but that you'd call it once to advance by 270000 places (still taking O(n) time). But, yes I hadn't considered the effect of needing to scroll. I was thinking of something embedded I wrote that only had up & down buttons.

It looks like chairthrower to the rescue!

Solution:
http://en.wikipedia.org/wiki/AVL_tree
Duh, I should have remembered AVL trees. :)

Quick google of AVL trees gives me:
http://stlavlmap.sourceforge.net/
http://meshula.net/articles/AVL.html

Except they don't let you look up an item by index, because they don't store the count of nodes beneath them, only the height of the tree beneath them, or the balance factor difference.
I would have suggested a bastardised AVL tree earlier if I thought you'd go for it. I've got all the common self-balancing trees implemented on my website.

Quote:

Original post by iMalc Except they don't let you look up an item by index, because they don't store the count of nodes beneath them, only the height of the tree beneath them, or the balance factor difference. I would have suggested a bastardised AVL tree earlier if I thought you'd go for it. I've got all the common self-balancing trees implemented on my website.

Funny, I thought I was suggesting a bastardised red-black tree in a roundabout way. ;)

Yep, AVL trees don't do it, other than using the counter 'adjacent to' and maintained with the rotations. :/ For a second I thought I could use the counter as a proxy for the AVL height value, but it gets messy when I try to do that.