Data structure to hold thousands of unique structs?
Author
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]
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.
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?
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
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.
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.
Quote:Original post by doynax
A hash table should be faster and occupy much less space than a hash table.
eh?
Quote:Original post by NitageD'oh.. :)Quote:Original post by doynax
A hash table should be faster and occupy much less space than a hash table.
eh?
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
