std::tie and Strict Weak Ordering

One of the requirements for placing objects into a std::map or std::set is that the Key type has Strict Weak Ordering, usually via std::less. Writing a suitable comparator for an abritary structure is a pretty trivial excercise. The problem is,  it is also trivially easy to make a mistake.
If the comparator is not Strict Weak, there will be no compiler warning or alarm bells. Worse still, if you are unlucky, there will be no indication at runtime either. Just occasional, seemingly at random, inserting or deleting an item will segfault.
If only we didn't have to write these trivial comparators ourselves!

The C++ Standard Committe has a paper n3326 on compile time reflection that contains a hidden little gem. The tuple helper function std::tie can be used to write a comparator function for you!

A quick reminder, std::tie is a shorthand way of binding seperate elements to a tuple.

tuple< int, int > coords( 1, 2 );
int x;
int y;
tie( x, y ) = coords;

The trick to tie is that it creates a tuple of references to elements - its the reference version of make_tuple. Usefully a tuple defines the full set of comparison operators ==, <, >, >=, <= and !=. The comparison operators are not restricted to the exact same tuple type either, but work with any tuple where each corresponding member is comparable.

It's the ability to tie references into a tuple combined with the tuple comparison operators that allows the shorthand trick. Consider the following struct:

struct Burger {
  int  bacon;
  int  meat; 
  int  green_stuff;
  string name;
};

Thanks to std::tie we can easily write a map friendly operator<:

bool operator<( const Burger& l, const Burger& r ) {
  return tie( l.bacon, l.meat, l.green_stuff, name ) < tie( r.bacon, r.meat, r.green_stuff, r.name );
}

similarly equality:

bool operator==( const Burger& l, const Burger& r ) {
  return tie( l.bacon, l.meat, l.green_stuff, name ) == tie( r.bacon, r.meat, r.green_stuff, r.name );
}

That not only saves a lot of typing but is safer too. Even better, there is no abstraction penalty to pay, a release build  produces identical code to a hand written function.

There is a caveat though, as usual care needs to be taken with floating point types. Unfortunately the ieee standard dictates that floats set to NAN will compare unordered always - even when compared with itself. Because of this float types do not satisfy Strict Weak Ordering when set to NAN, so the above tie trick fails unless you are careful to never place a NAN into a map key.

C++11 string switch

C++11 added a slew of new features - lambda, auto, uniform initilizers, move semantics - the list is large. Near the bottom, almost forgotten, is general const expressions. C++11 adds the new keyword constexpr (n2335), which at first glance seems like just an esoteric tightening of const, but actually is so much more.  C++ has always had the constant expressions, so explicitly labelling something as such would seem to not gain much. But au contraire, constexpr is an incredibly useful addition that will greatly simplify meta programming in C++.

What can you do with constexpr that you can't you do with templates? Turns out, lots:

You can generate a compile time string hash (string hashing). Perform all sorts of compile time string manipulation (constexprstr). Do compile time unit conversion, and generate philosphical debate (turing).

constexpr can also interact with other C++11 features in interesting ways. For example using string hashing and user literals it is possible to do a very good approximation of a string switch statement.

Lets start with a compile time string hasher, like the one found here.

// FNV-1a constants
static constexpr unsigned long long basis = 14695981039346656037ULL;
static constexpr unsigned long long prime = 1099511628211ULL;

// compile-time hash helper function
constexpr unsigned long long hash_one(char c, const char* remain, unsigned long long value)
{
    return c == 0 ? value : hash_one(remain[0], remain + 1, (value ^ c) * prime);
}

// compile-time hash
constexpr unsigned long long hash_(const char* str)
{
    return hash_one(str[0], str + 1, basis);
}

// run-time hash
unsigned long long hash_rt(const char* str) {
    unsigned long long hash = basis;
    while (*str != 0) {
        hash ^= str[0];
        hash *= prime;
        ++str;
    }
    return hash;
}
constexpr long long operator"" _hash( const char* str, size_t n ) {
    return hash_( str );
}

Now we can use the _hash string literal to generate a compile time string hash, which can be used anywhere a constant expression can be, such in in non-type template parameters and switch statements!

template < long long n >
struct some_template {
    static const long long value = n;
};

void print( const char * str ) {
    switch ( hash_( str ) ) {
       case  "hello"_hash: std::cout << "hello string passed\n"; break;
       case  "world"_hash: std::cout << "world string passed\n"; break;
    };
}

int main() {

    long long hash = some_template< "hello"_hash >::value;

    print( "hello" );
    print( "world" );

    return 0;
}

Of course it's not really limited to strings either, the technique can be extended to any type that has a hash and constexpr constructor.