7

I am faced with an application where I have to design a container that has random access (or at least better than O(n)) has inexpensive (O(1)) insert and removal, and stores the data according to the order (rank) specified at insertion.

For example if I have the following array:

[2, 9, 10, 3, 4, 6]

I can call the remove on index 2 to remove 10 and I can also call the insert on index 1 by inserting 13.

After those two operations I would have:

[2, 13, 9, 3, 4, 6]

The numbers are stored in a sequence and insert/remove operations require an index parameter to specify where the number should be inserted or which number should be removed.

My question is, what kind of data structures, besides a Linked List and a vector, could maintain something like this? I am leaning towards a Heap that prioritizes on the next available index. But I have been seeing something about a Fusion Tree being useful (but more in a theoretical sense).

What kind of Data structures would give me the most optimal running time while still keeping memory consumption down? I have been playing around with an insertion order preserving hash table, but it has been unsuccessful so far.

The reason I am tossing out using a std:: vector straight up is because I must construct something that out preforms a vector in terms of these basic operations. The size of the container has the potential to grow to hundreds of thousands of elements, so committing to shifts in a std::vector is out of the question. The same problem lines with a Linked List (even if doubly Linked), traversing it to a given index would take in the worst case O (n/2), which is rounded to O (n).

I was thinking of a doubling linked list that contained a Head, Tail, and Middle pointer, but I felt that it wouldn't be much better.

Mogsdad
  • 44,709
  • 21
  • 151
  • 275
Code Doggo
  • 2,146
  • 6
  • 33
  • 58
  • Once you've said you want : access an element by its rank, remove an element at a given rank an insert an element at a given rank, why do you want anything other than a linked list (std::list) or dynamic array (std::vector) ? Please give you requirements before this question can be considered as unclear. – Serge Ballesta Apr 23 '15 at 07:41
  • Do you want to iterate through the collection? What is approximate size of the collection? – W.F. Apr 23 '15 at 07:41
  • @Serge Ballesta The running time to remove a given element in a vector is O(n) worst case. In addition, traversing a linked list is horrible in the sense of a large amount of nodes. – Code Doggo Apr 23 '15 at 07:42
  • You say "which can be defined by their order in which they were inserted in", but also you want to be able to "insert on index 1". So, in fact the index is not defined by the order, but by the index specified on insert? – Petr Apr 23 '15 at 07:43
  • @Petr Yes, you are correct. There is no comparisons of the objects being thrown into the structure. They are just stacked next to each other. – Code Doggo Apr 23 '15 at 07:45
  • Have you tried using a `std::vector`? Is it really the bottleneck in your application? Have you measured it? – MadScientist Apr 23 '15 at 07:47
  • @WojciechFrohmberg Yes I would like to be able to iterate through the collection as another task of mine is to find the minimal value of the collection. But what I stated above is the main concerns (the min value is have a trick up my sleeve). And roughly about ten thousand. There could be upwards to a hundred thousand. – Code Doggo Apr 23 '15 at 07:47
  • @MadScientist std::vector is my base line. Meaning I need something faster than a vector. I have been doing research and a lot of thinking of what I could do but I am unsure of what would be best. – Code Doggo Apr 23 '15 at 07:48
  • std::vector is really fast. Even thou it is O(n), usually it is much faster than LinkedList. Here you have comprehensive benchmark : http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html. Maybe you should consider using std::map.std::vector is really fast. Even thou it is O(n), usually it is much faster than LinkedList, here you have comprehensive benchmark : http://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html. Maybe you should consider using std::map. It gives you iterators and most operations are O(log N) . – kkamil Apr 23 '15 at 07:59
  • @DanielH, see also an update to my answer. – Petr Apr 23 '15 at 08:26

2 Answers2

8

In a basic usage, to be able to insert and delete at arbitrary position, you can use linked lists. They allow for O(1) insert/remove, but only provided that you have already located the position in the list where to insert. You can insert "after a given element" (that is, given a pointer to an element), but you can not as efficiently insert "at given index".

To be able to insert and remove an element given its index, you will need a more advanced data structure. There exist at least two such structures that I am aware of.

One is a rope structure, which is available in some C++ extensions (SGI STL, or in GCC via #include <ext/rope>). It allows for O(log N) insert/remove at arbitrary position.

Another structure allowing for O(log N) insert/remove is a implicit treap (aka implicit cartesian tree), you can find some information at http://codeforces.com/blog/entry/3767, Treap with implicit keys or https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.

Implicit treap can also be modified to allow to find minimal value in it (and also to support much more operations). Not sure whether rope can handle this.

UPD: In fact, I guess that you can adapt any O(log N) binary search tree (such as AVL or red-black tree) for your request by converting it to "implicit key" scheme. A general outline is as follows.

Imagine a binary search tree which, at each given moment, stores the consequitive numbers 1, 2, ..., N as its keys (N being the number of nodes in the tree). Every time we change the tree (insert or remove the node) we recalculate all the stored keys so that they are still from 1 to the new value of N. This will allow insert/remove at arbitrary position, as the key is now the position, but it will require too much time for all keys update.

To avoid this, we will not store keys in the tree explicitly. Instead, for each node, we will store the number of nodes in its subtree. As a result, any time we go from the tree root down, we can keep track of the index (position) of current node — we just need to sum the sizes of subtrees that we have to our left. This allows us, given k, locate the node that has index k (that is, which is the k-th in the standard order of binary search tree), on O(log N) time. After this, we can perform insert or delete at this position using standard binary tree procedure; we will just need to update the subtree sizes of all the nodes changed during the update, but this is easily done in O(1) time per each node changed, so the total insert or remove time will be O(log N) as in original binary search tree.

So this approach allows to insert/remove/access nodes at given position in O(log N) time using any O(log N) binary search tree as a basis. You can of course store the additional information ("values") you need in the nodes, and you can even be able to calculate the minimum of these values in the tree just by keeping the minimum value of each node's subtree.

However, the aforementioned treap and rope are more advanced as they allow also for split and merge operations (taking a substring/subarray and concatenating two strings/arrays).

Community
  • 1
  • 1
Petr
  • 9,812
  • 1
  • 28
  • 52
0

Consider a skip list, which can implement linear time rank operations in its "indexable" variation.

For algorithms (pseudocode), see A Skip List Cookbook, by Pugh.

It may be that the "implicit key" binary search tree method outlined by @Petr above is easier to get to, and may even perform better.

davidbak
  • 5,775
  • 3
  • 34
  • 50