Current version

v1.10.4 (stable)


Main page
Archived news
Plugin SDK
Knowledge base
Contact info
Other projects


Blog Archive


A couple of days ago I found myself writing a breadth-first search routine in C++ for a particular puzzle (Klotski, to be specific). Since I was using Visual C++, I needed a set for the board database, and decided to use its stdext::hash_set.

stdext::hash_set... sucks.

See, Visual C++'s Standard Template Library (STL) is based on the implementation from Dinkumware, and has the following prototype:

template<class Key,
class Traits = hash_compare<Key, less<Key> >,
class Allocator = allocator<Key> >
class hash_set;

Notice two things about this hash set implementation: it takes a less-than predicate, and it doesn't take an equality predicate. What the frick kind of hash table requires a less-than predicate??? And we're not talking about a predicate for the hash code here, but a less-than comparison operator for the whole key. It defeats one of the main advantages of a hash container, since IMO it's often easier to write hash and equality predicates instead of a less-than predicate, as long as you aren't dealing with floats. I've never seen a hashed container that required this -- not in SGI-STL/STLport, not in Java, not in the .NET Framework. As you might expect, this means that VC8's hash_set is a pain in the butt to use and is slow. Thankfully, C++ TR1's unordered_set follows the SGI-STL/STLport path rather than Dinkumware's.

I haven't really had a need for a full blown hash_map or a hash_set in VirtualDub, but I'm thinking that if I do, I'll be better off writing my own....


This blog was originally open for comments when this entry was first posted, but was later closed and then removed due to spam and after a migration away from the original blog software. Unfortunately, it would have been a lot of work to reformat the comments to republish them. The author thanks everyone who posted comments and added to the discussion.