12

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:

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.

Community
  • 1
  • 1
MaksymB
  • 1,267
  • 10
  • 33
  • try to find an answer in http://softwarerecs.stackexchange.com/ – DawidPi Sep 29 '15 at 08:45
  • 5
    @DawidPi: Are you sure you understand either the question or the meaning of "software recommendation"? – user541686 Sep 29 '15 at 08:48
  • 2
    In software recommendation you are looking for already existing software in the market. In Software Recommendation you give your requirements about software you want and other people are helping you. I added this comment, when there was no text saying , that author wants to implement it himself, only question about open source implementation of this algorithm Am I wrong? – DawidPi Sep 29 '15 at 09:02
  • 4
    @DawidPi: Correct, I don't want to implement it myself. I need a ready-to-use C++ implementation. I added the last section only to say that if there is no C++ implementation, I would be glad to see at least 'any' implementation as a reference. – MaksymB Sep 29 '15 at 09:17
  • 1
    Whatever the answer to this question would be, you should benchmark it vs. a sorted `std::vector`. I would not be surprised finding the POI (like the insertion point) completely dominates for all real world sized collections. – Baum mit Augen Sep 29 '15 at 09:22
  • What's the universe you are maintaining? Is it just integers or more complex objects with an arbitrary total order? – Niklas B. Sep 29 '15 at 11:03
  • On what kind of objects do intends to use this structure? Could you specify? There might be a solution not using this structure at all. – sve Sep 29 '15 at 11:35
  • @svs: added some details. – MaksymB Sep 29 '15 at 12:02
  • 1
    just use a std::set, benchmark it and see if it's too slow for your needs. Unless you have critical performances, it will perform quite well. – dau_sama Sep 29 '15 at 12:24
  • @dau_sama: std::set will order the items automatically. I don't need the pointers to be ordered by its value. I want the data structure to keep the order I specify by moving the items around. – MaksymB Sep 29 '15 at 13:24
  • @Maxym a std::set can be constructed with a custom comparison operator... It seems that you'd need to have an extra integer or something to maintain unusual ordering as described in the other question – rubenvb Sep 29 '15 at 13:40
  • @rubenvb: that's true, but if I could provide comparison operator, I would not need an 'order-maintaining data structure'. Integer constant is not an option, because I will need to insert new elements many times in between two others. Sooner or later I'll need to relabel many items in the list. – MaksymB Sep 29 '15 at 13:47
  • @Maxym If you can ensure the wanted order can be maintained, use a `std::vector`, and if its performance dissapoints (and only then), switch to `std::list`. You'll need to keep control of the order yourself though, fully. – rubenvb Sep 29 '15 at 13:48
  • @Maxym just implement `operator<` and set will use that for ordering. Otherwise you can specify a custom function/functor for your needs.I wouldn't go farther than that. – dau_sama Sep 29 '15 at 14:02
  • 1
    Even if you find a good implementation of an order-maintenance data structure, it might turn out that the constant factors involved are much higher than the O(log n) factor introduced by common search data structures, for practical problem sizes – Niklas B. Oct 05 '15 at 13:53
  • @NiklasB. You are right! And That's why I wanted to play with existing implementation before taking any actions. – MaksymB Oct 05 '15 at 13:58
  • @Maxym In case you are interested in implementing one of these yourself, you should check out Erik Demaine's awesome lectures: https://www.youtube.com/watch?v=bY8f4DSkQ6M He introduces the list-order maintenance problem at 41:15 – Niklas B. Oct 05 '15 at 14:10

3 Answers3

5

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.

sve
  • 4,336
  • 1
  • 19
  • 30
0

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

Amsal N
  • 201
  • 2
  • 10
-2

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!

Paul Floyd
  • 5,530
  • 5
  • 29
  • 43
David Haim
  • 25,446
  • 3
  • 44
  • 78
  • Not to be pedantic, but I think you mean the [C++ standard library](http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about). – erip Sep 29 '15 at 12:14
  • 1
    a STL deque has [...constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle](https://www.sgi.com/tech/stl/Deque.html) as can have the C++ standard library implementation – BeyelerStudios Sep 29 '15 at 12:32
  • @BeyelerStudios according to here : http://www.cplusplus.com/reference/deque/deque/insert/ it's lineral to the number of items inserted. it *may* take another N actions if the library implements it in such sort. – David Haim Sep 29 '15 at 12:55
  • that's what I wrote... now you're the one quoting from a standard library reference... decide – BeyelerStudios Sep 29 '15 at 12:56
  • I'm not understanding you correctly. inserting in the from or back is O(1) , inserting on the middle can be O(1) OR O(N) depending on the implementation. but that does not cancel what I responded. I might have assumed the OP insert at the front/back – David Haim Sep 29 '15 at 13:03
  • 2
    @DavidHaim: no, under reordering I meant deletion/insertion in random positions (modified OP to be more explicit). Also position comparison O(N) is not acceptable. O(lg N) may be acceptable, but the articles state that even O(1) is possible, that's why I'm looking for existing implementation. – MaksymB Sep 29 '15 at 13:35