Posts Tagged ‘software’

Choosing an STL Sequence Container

Saturday, June 9th, 2012

The C++ Standard Template Library has a fairly good selection of container classes, and in particular “sequence” containers. For some reason (I’ve always assumed it’s familiarity), most people seem to use std::vector as their container-of-choice, but experience shows that it’s actually the best choice less often that one would think.

So how do you pick the right sequence container? Often, it’s not an easy or obvious choice. Each container has different trade-offs : there’s the obvious difference of some provide features that others don’t – but there are also the more subtle differences in memory allocation characteristics, performance guarantees, and some perhaps less easily quantifiable characteristics (such as cache locality).

This is based on something I wrote a little while ago when corresponding with my friend & colleague Luca Bolognese on his recent series of articles on functional programming in C++ (which is well worth a read).

Just as there’s no “one size fits all” container (and, by inference, no “one size fits all default” container), there’s no one size fits all mechanism for choosing a container (although profiling can help a lot) – but this is roughly how I choose a container (before I can profile, naturally!).

A decision tree for selecting a sequence container:

  • I’m in a rush and can’t be bothered to read the rest: use std::deque
  • I know at compile time exactly how many elements will be needed (and will they all fit on our stack!) – If so, use std::array.
  • I need constant-time random access (it’s worth noting that we often *think* we do, but actually don’t – YAGNI applies). If you DO need it, then we can eliminate std::list/std::forward_list as candidates.
  • I need bidirectional iteration (again, we need this less often that we thing). If so, eliminate std::forward_list from consideration
  • Will elements often be added/removed “in the middle” (i.e. not at the ends)? std::forward_list or std::list are probably the best choices. (Unless you eliminated them earlier due to constant time random-access requirements); these two are particularly useful when the contained elementes are expensive to move/copy, since they don’t need to shuffle things around when you add or remove elements. Of course, it may be possible to reduce the cost of move/copy by having a container of (preferably smart) pointers, rather than directly containing the objects.
  • Do we need the contents as a contiguous array? use std::vector (and call reserve with a reasonable guesstimate beforehand if we can) – sometimes, anyway; I’ve seen cases where it’s faster to build my collection as a std::deque, then transform to std::vector later on.)
  • Use std::deque.

Or, to put it another way, “default to std::deque unless there’s a good reason not to”.  That’s an overly-strong statement, but it’s a reasonable starting point. In a typical application, deque will give you better memory allocation characteristics than any of the others (aside from std::array, but that’s extremely limited in its application). vector can beat it IF you have a good estimate for how big the collection is going to get (but otherwise can tail off dramatically). deque will typically give you better cache locality than list/forward_list, and it’s insert/remove at the ends characteristics are better than any of the containers except the two list types.

Naturally, every case will be different – and no set of ‘rules of thumb’ is going to work every time (this is one of the things which distinguish rules of thumb from laws of physics). Commonly, we don’t know ahead of time which of those criteria is going to have the most significant impact on what we’re doing; when I find myself in that situation, I’ll use std::deque; once I have a firmer idea of the criteria, I’ll go back and revisit that choice (which – quite often – is as simple as changing a typedef). And of course – as with all ‘optimisations’ – measure, measure and measure again!

Unit testing – with a Catch

Saturday, June 9th, 2012

For fun, I’ve been working on a little iPhone project (a simple password manager – the code is pretty horrible right now, but you can find it on github if you’re curious).

Naturally, I wanted to write some unit tests – and thought it was about time to try out a framework I’ve been meaning to take a look at for a while; it’s called Catch, and written by a friend (and sometime colleague) of mine – Phil Nash. First impressions are very good.

It’s amazingly easy to get up and running; just download it, include a header file – and write a few tests. Here’s a trivial example, with a couple of tests:


#define CATCH_CONFIG_MAIN #include "catch.hpp"
TEST_CASE( "Simple/Number1", "A simple test" )
  int i = 0;
  REQUIRE( i == 1 ); // Naturally, this should fail!
TEST_CASE( "Simple/Number2", "Another test" )
  int i = 0;
  REQUIRE( i == 0 ); // .. and this should pass

And there you go – compile that, and run it – the output looks something like this:

[Started testing]

[Running: Simple/Number1]
test.cpp:7: i == 1 failed for: 0 == 1
[Finished: 'Simple/Number1' 1 test case failed (1 assertion failed)]

[Testing completed. 1 of 2 test cases failed (1 of 2 assertions failed)]


It has some very nice features:

  • It works for both C++ and Objective-C (strictly, the test cases need to be in Objective-C++, but you test Objective-C components with them)
  • The ease of use of the TEST_CASE macro, which hides all the horrid boilerplate that many frameworks seem to insist on.
  • It works on multiple platforms (although so far I’ve only actually run it on OS X).
  • Distributed under the Boost licence, which is about as permissive as they come.
  • It’s a header-only implementation, so no libraries to build and link to.
  • It’s much easier to get yourself started than any other testing framework I’ve used (and I’ve used a few…)

So what’s the Catch? Well, none that I can see – aside from Phil reserves the right to use that particular pun well past it’s sell by date… (Phil has a truly astonishing stockpile of puns, so I’m not sure why he thinks he needs another – but there you go…)

It’s early days for me with Catch, but I’m sure I’ll write more on it some other time. But for now, it gets my recommendation.