Sorting hashes...

[incutonez]

Is there an easy way to sort a hash by its values?

What I'm doing is building a dictionary of words from a text file, and my wordStruct looks like so (including hash map declaration in main):

struct wordStruct
{
	string word;
	int wordCount;
	int docCount;
	vector<int> docs;
};

hash_map<string, wordStruct> dict;

I can populate the hash map just fine, what my problem is is efficiency (most likely with sorting)... right now, I convert this hash map into a vector (which is really bad since I'm mirroring the hash map, thus doubling how much memory I'm using), then Merge Sort the vector and use that as a way to print by my wordCount, but it takes quite a while for a text file of size 600 kb (and I would definitely like to go higher...), so is there a way to sort this hash more easily? Any advice would be appreciated!

[laserlight]

You can store the iterators in a vector, and then sort the iterators according to the wordCount members of what they refer to.

By the way, the TR1 extensions to the standard library include unordered_map, which will become part of the C++ standard library, so you may wish to use that instead of hash_map.

[incutonez]

Ahhhh, I'll trying storing the iterators, good idea!

For some reason, my tr1 doesn't have unordered_map... if I do "std::tr1::" I have no words that begin with u... so I guess I don't have VS 2008's updated libs? I actually had to download a "feature pack" to get my hash_maps working, but still no unordered_map. It's really odd.

[incutonez]

BUMP. Any advice on getting unordered_map to work?

[Lindley]

Well, you can always use the unordered_map from Boost if necessary.

[incutonez]

Ahhh, forgot Boost had its own unordered_map.

I changed the hash_map to store the iterators in the vector--no change. Still took the usual 4 minutes, which is terrible, haha.

Then I changed to unordered_map, without storing the iterators in the vector--no change. Still 4 minutes.

Then I used unordered_map and its iterators... 12 seconds.

Nice job all. Thanks!