CODEWITHSUNDEEP
c++arraysdata-structures
rwik
rwik

Reputation: 785

What is the fastest data structure to search and update list of integer values?

I have to maintain a list of unordered integers , where number of integers are unknown. It may increase or decrease over the time. I need to update this list of integers frequently. I have tried using vector . But it is really slow . Array appears to be faster , but since the length of list is not fixed, it takes significant amount of time to resize it . Please suggest any other option .

Upvotes: 2

Views: 5013

Answers (6)

ogni42
ogni42

Reputation: 1276

Considering your comments, it looks like it is std::set or std::unordered_set fits your needs better than std::vector.

Upvotes: 1

MissingNumber
MissingNumber

Reputation: 1182

If you are interested in Dynamic increments of Arrays size you can do this .

current =0;
x = (int**)malloc(temp * sizeof(int*));
x[current]=(int*)malloc(RequiredLength * sizeof(int));

So add elements to array and when elements are filled in x[current] You can add more space for elements by doing

x[++current]=(int*)malloc(RequiredLength * sizeof(int));

Doing this you can accommodate for RequiredLength more elements .

You can repeat this upto 1024 times which means 1024*RequiredLength elements can be

accommodated , here it gives you chance to increase size of array whenever you want it .

You can always access the n th element by X[ n / 1024 ][ n % 1024] ;

Upvotes: 1

JoeyMiu
JoeyMiu

Reputation: 149

well,deque has no resize cost,but if it's unordered,it's search time is linear ，and its delete and insert operation time in the middle of its self is even worth than vector.
if you don't need search by the value of the number,hashmap or map may be your choice .No resize cost.,then you set the key of the map to number's index,and the value to the number's value.the search and insert operation is better than linear.

Upvotes: 0

fatihk
fatihk

Reputation: 7929

std::list is definitely created for such problems, adding and deleting elements in list do not necessitate memory re-allocations like in vector. However, due to the noncontagious memory allocation of the list, searching elements may prove to be a painful experience ofcourse but if you do not search its entries frequently, it can be used.

Upvotes: -1

Tuan-Tran
Tuan-Tran

Reputation: 1

If sequential data structures fails to meet requirements, you could try looking at trees (binary, AVL, m-way, red-black ect ...). I would suggest you try to implement AVL tree since it yields a balanced or near balanced binary search tree which would optimize your operation. For more on AVL tree: http://en.wikipedia.org/wiki/AVL_tree

Upvotes: 0

Ira Baxter
Ira Baxter

Reputation: 95430

Use a hash table, if order of the values in unimportant. Time is O(1). I'm pretty sure you'll find an implementation in the standard template libraries.

Failing that, a splay tree is extremely fast, especially if you want to keep the list ordered: amortized cost of O(ln n) per operation, with a very low constant factor. I think C++ stdlib map is something like this.

Know thy data structures.

Upvotes: 1

Related Questions