Order-maintenance data structure in C++

Question

I'm looking for a data structure which would efficiently solve Order-maintenance problem. In the other words, I need to efficiently

• insert (in the middle),
• delete (in the middle),
• compare positions of elements in the container.

I found good articles which discuss this problem:

• Two Algorithms for Maintaining Order in a List,
• Two Simplified Algorithms for Maintaining Order in a List.

The algorithms are quite efficient (some state to be O(1) for all operations), but they do not seem to be trivial, and I'm wondering if there is an open source C++ implementation of these or similar data structures.

I've seen related topic, some simpler approaches with time complexity O(log n) for all operations were suggested, but here I'm looking for existing implementation.

If there was an example in some other popular languages it would be good too, this way I would be able at least to experiment with it before trying to implement it myself.

Details

I'm going to

• maintain a list of pointers to objects,
• from time to time I will need to change object's order (delete+insert),
• given a subset of objects I need to be able to quickly sort them and process them in correct order.

Note

The standard ordering containers (std::set, std::map) is not what I'm looking for because they will maintain order for me, but I need to order elements myself. Similar to what I would do with std::list, but there position comparison would be linear, which is not acceptable.

Answer 1

If you are looking for easy-to-implement and efficient solution at the same time you could build this structure using a balanced binary search tree (AVL or Red-Black tree). You could implement the operations as follows:

• insert(X, Y) (inserts X immediately after Y in the total order) - if X doesn't have a right child set the right child of X to be Y, else let Z be the leftmost node of tree with root X.right (that means the lowest Z = X.right.left.left.left... which is not NULL) and set it's left child of Z to be Y. Balance if you have to. You can see that the total complexity would be O(log n).
• delete(X) - just delete the node X as you'd normally will from the tree. Complexity O(log n).
• compare(X,Y) - find the path from X to the root and the path from Y to the root. You can find Z , the lowest common ancestor of X and Y, from those two paths. Now, you can compare X and Y depending on whether they are in the left or in the right subtree of Z (they can't be in the same subtree at the same time since then Z won't be their lowest common ancestor). Complexity O(log n).

So you can see that the advantage of this implementation is that all operations would have complexity O(log n) and it's easy to implement.