CODEWITHSUNDEEP
c++listdata-structuresinsertion
Peter
Peter

Reputation: 425

Efficient Data Structure for Insertion

I'm looking for a data structure (array-like) that allows fast (faster than O(N)) arbitrary insertion of values into the structure. The data structure must be able to print out its elements in the way they were inserted. This is similar to something like List.Insert() (which is too slow as it has to shift every element over), except I don't need random access or deletion. Insertion will always be within the size of the 'array'. All values are unique. No other operations are needed.

For example, if Insert(x, i) inserts value x at index i (0-indexing). Then:

And it'll need to be able to print out {5,1,2,3} at the end.

I am using C++.

Upvotes: 9

Views: 4240

Answers (7)

Peter Gerdes
Peter Gerdes

Reputation: 2978

There's this data structure which pushes insertion time down from O(N) to O(sqrt(N)) but I'm not that impressed. I feel one should be able to do better but I'll have to work at it a bit.

Upvotes: 0

Evgeni Sergeev
Evgeni Sergeev

Reputation: 23593

A solution that's included with GCC by default is the rope data structure. Here is the documentation. Typically, ropes come to mind when working with long strings of characters. Here we have ints instead of characters, but it works the same. Just use int as the template parameter. (Could also be pairs, etc.)

Here's the description of rope on Wikipedia.

Basically, it's a binary tree that maintains how many elements are in the left and right subtrees (or equivalent information, which is what's referred to as order statistics), and these counts are updated appropriately as subtrees are rotated when elements are inserted and removed. This allows O(lg n) operations.

Upvotes: 1

nndhawan
nndhawan

Reputation: 617

Regarding your comment:

List.Insert() (which is too slow as it has to shift every element over),

Lists don't shift their values, they iterate over them to find the location you want to insert, be careful what you say. This can be confusing to newbies like me.

Upvotes: 1

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

Use skip list. Another option should be tiered vector. The skip list performs inserts at const O(log(n)) and keeps the numbers in order. The tiered vector supports insert in O(sqrt(n)) and again can print the elements in order.

EDIT: per the comment of amit I will explain how do you find the k-th element in a skip list:

For each element you have a tower on links to next elements and for each link you know how many elements does it jump over. So looking for the k-th element you start with the head of the list and go down the tower until you find a link that jumps over no more then k elements. You go to the node pointed to by this node and decrease k with the number of elements you have jumped over. Continue doing that until you have k = 0.

Upvotes: 9

Fred Foo
Fred Foo

Reputation: 363517

You can use an std::map mapping (index, insertion-time) pairs to values, where insertion-time is an "autoincrement" integer (in SQL terms). The ordering on the pairs should be

(i, t) < (i*, t*)

iff

i < i* or t > t*

In code:

struct lt {
    bool operator()(std::pair<size_t, size_t> const &x,
                    std::pair<size_t, size_t> const &y)
    {
        return x.first < y.first || x.second > y.second;
    }
};

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like;

void insert(array_like &a, int value, size_t i)
{
    a[std::make_pair(i, a.size())] = value;
}

Upvotes: 1

Running Wild
Running Wild

Reputation: 3011

In c++ you can just use a map of vectors, like so:

int main() {
  map<int, vector<int> > data;
  data[0].push_back(1);
  data[1].push_back(3);
  data[1].push_back(2);
  data[0].push_back(5);
  map<int, vector<int> >::iterator it;
  for (it = data.begin(); it != data.end(); it++) {
    vector<int> v = it->second;
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i] << ' ';
    }
  }
  cout << '\n';
}

This prints:

5 1 2 3

Just like you want, and inserts are O(log n).

Upvotes: -1

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Did you consider using std::map or std::vector ?

You could use a std::map with the rank of insertion as key. And vector has a reserve member function.

Upvotes: 1

Related Questions