Jump to content
  • Advertisement
Sign in to follow this  
LewsTherin

Data structure to hold thousands of unique structs?

This topic is 4835 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

I'm looking for a data structure that can hold a whole bunch of struct{}s, and do it quickly. Each unique value should only be stored once. It has to be very fast at searches and insertions. I was thinking maybe a hash table, but it seems like that would decimate my ram. Any suggestions? It's not really important, but it would be nice to know if such a thing existed before I ran off and made my own :P [Edited by - LewsTherin on August 21, 2005 5:01:26 PM]

Share this post


Link to post
Share on other sites
Advertisement
For quick searching and inserting use a binary tree. If you are going to do alot of deleting use a linked list. Thats about it.

Share this post


Link to post
Share on other sites
Quote:
Original post by LewsTherin
I was thinking maybe a hash table, but it seems like that would decimate my ram.

...decimate your RAM? Care to explain that to me? Couldn't you just use linked lists for each bucket?

Share this post


Link to post
Share on other sites
Quote:
Original post by LewsTherin
Any suggestions? It's not really important, but it would be nice to know if such a thing existed before I ran off and made my own :P


If you are using C++ then yes i suggest you don't run off and make your own unless you want to learn to how write one. C++ standard library provides containers, the choice you have here is either std::(multi)set/map (typically implemented via a red-black tree) or a non standardized extension hash_(multi)set/map (implemented with hash tables) that most compilers provide which is currently being reviewed for standardization and some compilers already implement it under the newer name std::tr1::unordered_(multi)set/map

Share this post


Link to post
Share on other sites
A hash table should be faster and occupy much less space than a red-black tree.
Remember that the average red-black tree (at least the one used in GCC's STL implementation) requires three extra pointers and a boolean per node (16 bytes on x86). A hash table on the other hand doesn't need more than a single pointer per node and one pointer per bucket. I guess you should try profiling them but I'm willing to bet that both searching and (especially) insertion is a lot faster into a hash table (with a proper number of buckets and hashing algorithm) than a binary tree.

So unless you need in-order traversal I suggest trying a hash table instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by doynax
A hash table should be faster and occupy much less space than a hash table.


eh?



Share this post


Link to post
Share on other sites
Quote:
Original post by Nitage
Quote:
Original post by doynax
A hash table should be faster and occupy much less space than a hash table.

eh?
D'oh.. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by LewsTherin
I'm looking for a data structer that can hold a whole bunch of struct{}s, and do it quickly. Each value is guaranteed to be unique.
It has to be very fast at searches and insertions.


But this seems the definition of the standard std::set<YourStructure> !!!

The set is a tree so your search time is O(log n)
If you insert an element you are guaranteed this is unique in the set.
The set is sorted for construction
Erasing or inserting elements does not invalidate your iterators.


Read more

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!