storing ID's
Author
ok I know there''s a really good way to do this but I forget what it''s called... Basically I have these ID''s that I need to keep track of that range from 10000 - 99999 perhaps. I want to just call something like void AddID(35325) and be able to call something like bool IDExists(35325) to check if it has been put in. I could make a dynamic array with functions that scroll through but i swear there was a really good way to do this i read about in another post a few months ago.. something like a list or a table ^^
You probably want a hashtable. Offers constant time insertion and lookup. Depending on your implementation language there is almost certainly an existing solution out there. In java, look up java.util.HashMap, in C++, I''m not quite sure, stl::hash_set or std::hash_multiset look promising.
You may want to lookup either a binary tree or a vector for efficiency. Binary will probably be a bit faster if you dont mind the coding.
With binary, it will be quicker to do a search, exspecialy if your adding nodes in weird locations. If you are just adding one on top of the other, and wish to count the nodes, use a vector.
[edited by - paulcesar on November 12, 2003 12:07:54 AM]
With binary, it will be quicker to do a search, exspecialy if your adding nodes in weird locations. If you are just adding one on top of the other, and wish to count the nodes, use a vector.
[edited by - paulcesar on November 12, 2003 12:07:54 AM]
Both binary tree and vector are less efficient for what he wants to do.
Hashtable: Insertion is O(1). Lookup is O(1).
Binary Tree: Ideally, insertion is O(log n). Lookup is O(log n).
Vector: Insertion O(1). Lookup O(n).
Additionally, you could keep a sorted vector, in which case:
Sorted Vector: Insertion O(n) (depending on implementation, might be O(log n)), Lookup(log n).
O(1) is better than O(log n) which is better than O(n). For his/her purposes, a Hash seems to be the best solution.
Hashtable: Insertion is O(1). Lookup is O(1).
Binary Tree: Ideally, insertion is O(log n). Lookup is O(log n).
Vector: Insertion O(1). Lookup O(n).
Additionally, you could keep a sorted vector, in which case:
Sorted Vector: Insertion O(n) (depending on implementation, might be O(log n)), Lookup(log n).
O(1) is better than O(log n) which is better than O(n). For his/her purposes, a Hash seems to be the best solution.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
