CODEWITHSUNDEEP
data-structures
Manas Verma
Manas Verma

Reputation: 472

Finding proper data structure c++

I was looking for some simple implemented data structure which gets my needs fulfilled in least possible time (in worst possible case) :-

(1)To pop nth element (I have to keep relative order of elements intact)
(2)To access nth element .

I couldn't use array because it can't pop and i dont want to have a gap after deleting ith element . I tried to remove the gap , by exchanging nth element with next again with next untill last but that proves time ineffecient though array's O(1) is unbeatable .

I tried using vector and used 'erase' for popup and '.at()' for access , but even this is not cheap for time effeciency though its better than array .

Upvotes: 6

Views: 393

Answers (4)

Maggi Iggam
Maggi Iggam

Reputation: 692

Well , tiered vector implemented on array would i think best fit your purpose . Though the tiered vector concept may be knew and little tricky to understand at first but then once you get it , it opens lot of question and you get a handy weapon to tackle many question's data structure part very effeciently . So it is recommended that you master tiered vectors implementation.

Upvotes: 3

Sebastian
Sebastian

Reputation: 1889

Warning: Don't take this answer seriously.

In theory, you can do both in O(1). Assuming this are the only operations you want to optimize for. The following solution will need lots of space (and it will leak space), and it will take long to create the data structure:

Use an array. In every entry of the array, point to another array which is the same, but with that entry removed.

Upvotes: 0

Dave Rager
Dave Rager

Reputation: 8150

An array will give you O(1) lookup but O(n) delete of the element. A list will give you O(n) lookup bug O(1) delete of the element.

A binary search tree will give you O(log n) lookup with O(1) delete of the element. But it doesn't preserve the relative order.

A binary search tree used in conjunction with the list will give you the best of both worlds. Insert a node into both the list (to preserve order) and the tree (fast lookup). Delete will be O(1).

struct node {
   node* list_next;
   node* list_prev;
   node* tree_right;
   node* tree_left;

   // node data;
};

Note that if the nodes are inserted into the tree using the index as the sort value, you will end up with another linked list pretending to be a tree. The tree can be balanced however in O(n) time once it is built which you would only have to incur once.

Update

Thinking about this more this might not be the best approach for you. I'm used to doing lookups on the data itself not its relative position in a set. This is a data centric approach. Using the index as the sort value will break as soon as you remove a node since the "higher" indices will need to change.

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

What you can try is skip list - it support the operation you are requesting in O(log(n)). Another option would be tiered vector that is just slightly easier to implement and takes O(sqrt(n)). both structures are quite cool but alas not very popular.

Upvotes: 3

Related Questions