I am a complete novice in C++. I am trying to read a file and build a lookup table (more like a hashtable just to check the existence of a string value). The file has about 300 thousand entries that I will use to build a lookup table. And after this, I will be performing some 1 million lookups on this. What is the most efficient way of doing this? Is it the map (google's first result) or is there a better structure for this purpose?
Based on the scenario, you probably also want to look at Tries
Try: http://en.wikipedia.org/wiki/Unordered_map_%28C%2B%2B%29
In general hash tables are good, but if you want "the most efficient way" you'll have to provide more details.
map has log(n) lookups, but you can achieve O(1) with a hash table, as you suggested. It looks like STL implements one, called hash_map.
C++ std::map is not a hash table, but you could use it for a lookup table if you wanted.
Its performance characteristics as guaranteed by the C++ standard are:
- O(log n) for searching for an element
- O(log n) for inserting a new element
- O(log n) for removing an element
There will definitely be memory overhead because the std::map is generally implemented with trees (and quite possibly a red-black tree), and pointers will be kept for each node in the map.
For better performance characteristics, you might want to look into Google's Sparsehash
If you want to check just the existance of a string value set is suffiecient as you don't have any key-value pairs. See here for documentation.
What you need is TRIE data structure. The dictionary is implemented widely using this data structure. Moreover it has O(n) lookup time where n is the length of the string and occupies less space. Trie has the abilities to quickly search for, insert, and delete entries.
If you have a very good hash function (no collision on your dataset) and you just need to check if entry exists or not, you try a bitset (say from http://bmagic.sourceforge.net/)
i believe it can reduce memory requirements and it's very fast.