Best container for random search based on string key

snack · 2010-12-17 09:22:19

Hi, I have a list of data objects indexed by a univocal string key. I need to perform fast random searches on this list, based on the key value. My current C++ implementation uses an STL map:

map<string, DataObject>

and I search items using operator[].

I was wondering if there is a better choice for the container than STL map, eg., some container which is heavily specialized for this kind of task, or some optimized STL algorithm to perform search instead of map::operator[]. Insertion is not an issue since the list is filled once and for all when my program starts, so I don't need to add items subsequently.
Many thanks

Allan · 2010-12-17 09:30:21

If you can use TR1 features, a std:tr1::hash<string> would be good.

stfn · 2010-12-17 10:11:03

Ordered containers such as std::map usually perform with a lookup time of logarithmic complexity due their implementation using balanced binary trees. In your case any unordered container like a hash table will most probably perform much better as those generally locate data in constant complexity.

Last edited by stfn (2010-12-17 10:11:48)

snack · 2010-12-17 11:50:02

Thank you both for the suggestion. I'm trying with boost::unordered_map. The search time in my tests dropped from 0.25 s to 0.06 s, quite impressive...
Are there better alternatives than boost::unordered_map? Speed is never enough...
But I'm already happy with this so don't bother too much

Last edited by snack (2010-12-17 11:51:15)

Allan · 2010-12-17 11:59:32

boost::unordered_map is basically a hash table if I remember correctly.

snack · 2010-12-17 12:00:53

Yes it is. It's blazing fast, and since my previous implementation was based on STL map the port is quite easy, so I think I found my sweet spot
Thanks again

tavianator · 2010-12-17 17:30:30

My favourite data structure for a string-keyed associative array is the PATRICIA trie. I find they perform comparably to hash tables. You can find a C implementation by me here, and I'm sure there's good C++ implementations. It sounds like you've already got performance where you want it, but I just figured I'd bring up another option.

Allan wrote:

If you can use TR1 features, a std:tr1::hash<string> would be good.

Allan wrote:

boost::unordered_map is basically a hash table if I remember correctly.

std::tr1::hash<> is the function object that actually performs hashing; std::tr1::unordered_map<> is a hash map. By the way, if you can use the tr1 headers instead of boost, you'll cut out a gigantic dependency for your project.

snack · 2010-12-17 18:40:05

Thank you very much tavianator for your suggestion. My software needs to run in different environments which are not under management so I have to rely on standard libraries like boost. Including the unodered map in my project using boost headers is fine for me but I'll give a try to your proposal.

Trent · 2010-12-17 19:41:48

snack wrote:

Thank you very much tavianator for your suggestion. My software needs to run in different environments which are not under management so I have to rely on standard libraries like boost.

Erm... boost isn't standard, it's a third-party library.

snack · 2010-12-17 21:47:49

Trent wrote:

snack wrote:
Thank you very much tavianator for your suggestion. My software needs to run in different environments which are not under management so I have to rely on standard libraries like boost.
Erm... boost isn't standard, it's a third-party library.

I know, but it's sufficiently famous to make it easy to convince the IT guys to install it on our pc-farms...

Arch Linux

#1 2010-12-17 09:22:19

Best container for random search based on string key

#2 2010-12-17 09:30:21

Re: Best container for random search based on string key

#3 2010-12-17 10:11:03

Re: Best container for random search based on string key

#4 2010-12-17 11:50:02

Re: Best container for random search based on string key

#5 2010-12-17 11:59:32

Re: Best container for random search based on string key

#6 2010-12-17 12:00:53

Re: Best container for random search based on string key

#7 2010-12-17 17:30:30

Re: Best container for random search based on string key

#8 2010-12-17 18:40:05

Re: Best container for random search based on string key

#9 2010-12-17 19:41:48

Re: Best container for random search based on string key

#10 2010-12-17 21:47:49

Re: Best container for random search based on string key

Board footer