Friday, April 06, 2007

C++ Templates Are Wizardry

I had to make a fix to a C++ program, and instead of doing the same old thing I had done before, I decided to effect a righteous STL/Boost standard solution. Here's the problem, I had a bunch of named objects and I needed to store them someplace.

I had a map and it worked until my boss asked, "is it case insensitive? does it ignore suffixes?" "No, should it?" "Yes & yes."

Though you wouldn't normally think of it, map requires a comparator to function. C# calls the same thing a sorted list, b/c they don't hide the fact that in order to work, the data structure has to be sorted on keys, and this comparator keeps the keys in sorted order. This comparator was what I needed to make my map work.

If I have two equivalent keys "Thing" and "thing.subthing" and want them to map to the same value, I can do so with a comparator function. Simply declare my map as map and then define a comparator functor that ignores the things like case and the stuff after the suffix character. The first part was a simple Boost exercise:

class comparator
bool operator()(const string& s1, const string& s2) const
string t1(s1);
string t2(s2);
transform (t1.begin(),t1.end(),t1.begin(), tolower);
transform (t2.begin(),t2.end(),t2.begin(), tolower);
//(more goes here later)
return t1 < t2;

The boost string algorithm is the way to go here. You should make it your friend. This handles the string insensitive part. If that's all you need. You're done.

Note: you MUST implement a LESS THAN function or the std::map template won't work.

I had to ignore all the stuff to the right of the decimal point. So, I added the following bit:

size_t dot1 = t1.find(".");
size_t dot2 = t2.find(".");
if (dot1!=string::npos)
t1 = t1.substr(0,dot1);
if (dot2!=string::npos)
t2 = t2.substr(0,dot2);

I was a little disappointed with this solution. I had hoped to just adjust the end iterators of the transform() calls above. However, it got gnarlie and harder to understand than this. If you know how can replace the transform() call with something using a back_inserter(), let me know.

After I got this working, I was impressed at how unhelpful the compiler and the language were in diagnosing the errors I'd made. I mentioned to a colleague that templates are the greatest thing ever invented, but they require a wizard to use gracefully. He agreed and suggested that if I did this every day, I'd be more efficient at diagnosis. He's right. When you work with something every day, you grok the philosophy of why things work, and you get a feel for why unhelpful compiler error messages say what they do.

No comments: