What is the best (time and space efficient) dictionary based data structure? I have a large set of strings (1 billion) of equal size ( 32 to 64) and I would like to store them in an dictionary so that I can do the set membership test.
Asked
Active
Viewed 706 times
0
-
It's rare to have a data structure that is best by both time and space efficiency metrics. Figuring out the usage pattern expected would be a good idea here - for example, do you only insert your keys once and then look them up many times, or do you frequently add and delete keys, or do you insert them once and then only look them up once, or .... – twalberg Nov 29 '16 at 18:21
-
Are the strings limited in the characters they contain? (Hexadecimal? Only uppercase?) – 1201ProgramAlarm Nov 29 '16 at 18:22
1 Answers
0
Use std::map, in which the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key.
If you don't need to have the map sorted by its keys, use an std::unordered_map, which is faster than map containers to access individual elements by their key.
You can read more on map v/s unordered_map at this question.
