Use unordered_map when key order is not important

- Unordered_map is faster for lookup, O(1) vs O(logn).  We profiled them
previously with GCC 4.8.1 to make sure, it holds even for small
collections.

I saw also a lot of string copying in the Checks, I'm going to look to
cut those down as well.