New Category: Programming (this week: swap and concept_check)

I’m starting a new category for programming tips. I jokingly referred to something as the C++ feature of the week (for Mace development) with one of our developers, and he responded that he needed to subscribe. And it seemed like a good idea, so now I think I’ll start trying to blog about these new features I learn about.

So to start it off, there are two C++ features of the week for this past week:

1. STL collection swap. The C++ STL Collections contain a swap() method, which takes another collection (of the same type) as a parameter. The method does what’s expected — to swap the one collection’s elements with the other. What makes this an interesting function is that it does it in constant time. It doesn’t require constructing, copying, or otherwise wasting time with the two collections. It just does pointer copies of internal collection state. To see how this is useful, consider these two cases I’ve applied this to:
   • Maps within maps. In one case, a Mace programmer had a map from an int to a vector. In this case, the int represented the number of things in the vector (admittedly, this is a bit of a simplification). So, when removing something from the vector, you would remove the vector from the map, then re-add it with the new key. (This is because for other good reasons, the key of a map entry cannot be changed). Because of the cost of this removal and re-addition, the programmer had originally implemented this using pointers, which, while correct and efficient, gave some of our other tools problems, and so we wanted to re-write it without using pointers. swap() made this possible. To do the update, use this code:
     
void removeElement(IntVectorMap& ivmap, int size) {
IntVectorMap::iterator i = ivmap.find(size);
assert(i != ivmap.end());
i->second.pop_front();
ivmap[size-1].swap(i->second);
ivmap.erase(i);
}

     This does involve a construction of a new collection, but moves the elements of the collection quite efficiently. Since we will erase the original map entry, causing the old vector to cease to exist, the fact that it now holds no elements does not matter.
   • The second case was one where we wanted to iterate through a set, but other code might be adding things to the set at the same time. To maintain code safety, we must not lose newly added things, so we can process them later. The original design involved making a copy of the set, then clearing the original set, and iterating over the copy. Once again, swap() is the right tool here too.
     
void processSet(IntSet& s) {
IntSet t;
t.swap(s);
for(IntSet::iterator i = t.begin(); ...) {
...
}
if (!s.empty()) { processSet(s); }
}

     As an added bonus, if you need to hold a lock to touch S, you can simply acquire the lock and do the switch, a very fast operation, the release the lock.
2. boost::concept_check. We were updating our serialization code, but found that the compiler error messages on template errors are hard-to-decipher (to be generous). These errors were caused by one of two problems in one of our cases. First, we had added a new template parameter, and inserted it before some existing ones. In code which hadn’t been updated though, if they provided the older optional template parameters, the compiler would get very confused, and report error messages which could not be deciphered, and pointed to lines of code which didn’t make any sense. In the other error case, the default template parameter might not work with other types passed. (Specifically, it was a parameter telling how to serialize a collection, and the collection elements might not have been serializable.) This message was a little easier to decipher, complaining about types which could not be serialized, but still didn’t point to the right lines of code.

   Using boost’s concept check, we were able to help both of these problems. In the first case, we wrote a base class for all valid parameters of the template, then used a concept check to make sure the template parameter was convertible to the base class. Passing in the older parameter now would generate a shorter, easier to understand message, and the concept check library makes sure that the line of code makes sense. In the second case, we had to write our own concept checker, which would essentially just write code that needed to be able to compile (in this case, instantiating the type, serializing it, and deserializing it). Again, the concept_check library would make sure the error message was pointed to in the right place.

That’s all for this edition. Watch the programming category if you want to see other programming tips.