CODEWITHSUNDEEP
c++algorithmdata-structures
MaksymB
MaksymB

Reputation: 1307

Order-maintenance data structure in C++

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

I found good articles which discuss this problem:

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

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.

Upvotes: 13

Views: 2294

Answers (3)

Amsal N
Amsal N

Reputation: 211

You can use skip list similar to how you use std::list

Skip lists were first described in 1989 by William Pugh. To quote the author:

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

http://drum.lib.umd.edu/handle/1903/542

Upvotes: 0

David Haim
David Haim

Reputation: 26476

STL is the solution to your problem.
It's the standard, proven and efficient containers and the algorithms that support them. almost all of the containers in STL support the actions you have mentioned.

It's seems like std::deque has the best qualities to the tasks you are referring to:
1) Insertion : both from to the back and to the front in O(1) complexity
2) Deletion : unlike contiguous containers, std::deque::erase is O(N) where N is the number of items deleted. meaning that erasing only one item has the complexity of O(1)
3) Position comparison : using std::advance, the complexity on std::deque is O(N)
4) Sorting : using std::sort, usually will use quick sort for the task, and will run in O(n* log n). In MSVC++ at least, the function tries to guess what is the best sorting algorithm for the given container.

do not try to use open source solution/building your own library before you have tried using STL thoroughly!

Upvotes: -3

sve
sve

Reputation: 4356

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.

Upvotes: 5

Related Questions