Archived

This topic is now archived and is closed to further replies.

storing ID's

This topic is 5142 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 ^^

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites