Compile time string hashing

Question

I have read in few different places that using c++0x's new string literals it might be possible to compute a string's hash at compile time. However, no one seems to be ready to come out and say that it will be possible or how it would be done.

• Is this possible?
• What would the operator look like?

---

I'm particularly interested use cases like this.

void foo( const std::string& value )
{
   switch( std::hash(value) )
   {
      case "one"_hash: one(); break;
      case "two"_hash: two(); break;
      /*many more cases*/
      default: other(); break;
   }
}

Note: the compile time hash function doesn't have to look exactly as I've written it. I did my best to guess what the final solution would look like, but meta_hash<"string"_meta>::value could also be a viable solution.

Answer 1

Note that the form shown here wasn't accepted into the standard, as noted below.

Compile time string processing is guessed to become possible through user-defined literals proposed in N2765.
As i already mentioned, i don't know of any compiler that currently implements it and without compiler support there can be only guess work.

In §2.13.7.3 and 4 of the draft we have the following:

Otherwise (S contains a literal operator template), L is treated as a call of the form
operator "" X<'c1', 'c2', ... , 'ck'>() where n is the source character sequence c1c2...ck. [Note: The sequence c1c2...ck can only contain characters from the basic source character set. —end note]

Combine that with constexpr and we should have compile time string processing.

update: i overlooked that i was reading the wrong paragraph, this form is allowed for user-defined-integer-literals and -floating-literals, but apparently not for -string-literals (§2.13.7.5).
This part of the proposal seems to have not been accepted.

That being said, with my limited glimpse at C++0x, it might look something like this (i most likely got something wrong):

template<char c, char... str>
struct hash {
    static const unsigned result = c + hash<str...>::result;
};

template<char c>
struct hash {
    static const unsigned result = c;
};

template<char... str> 
constexpr unsigned
operator "" _hash() {
    return hash<str>::result;
}

// update: probably wrong, because the above 
// form is not allowed for string-literals:    
const unsigned h = "abcd"_hash;

---

If Jerrys approach works, then the following should work however:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}

Answer 2

At least by my reading of §7.1.5/3 and §5.19, the following might be legitimate:

unsigned int constexpr const_hash(char const *input) { 
    // really simple hash function...
    return static_cast<unsigned int>(*input) 
         && static_cast<unsigned int>(*input) + hash(input+1); 
}

This does seem to follow the basic rules in §7.1.5/3:

1. The form is: "return expression;"
2. Its only parameter is a pointer, which is a scalar type, and therefore a literal type.
3. Its return is unsigned int, which is also scalar (and therefore literal).
4. There is no implicit conversion to the return type.

There is some question whether the *inputs involve an illegal lvalue to rvalue conversion, and I'm not sure I understand the rules in §5.19/2/6/2¹ and §4.1 well enough to be sure about that.

Usage would be something like:

switch(std::hash(value)) {
    case const_hash("one"): one(); break;
    case const_hash("two"): two(); break;
    // ...
    default: other(); break;
}

To comply with the requirements of §5.19/2/6/2 you might have to do something like this though:

// one of the `constexpr`s is probably redundant, but I haven't figure out which.
char constexpr * constexpr v_one = "one"; 

// ....

case const_hash(v_one): one(); break;

1. I'm using the extra 'slash' numbers to refer to unnumbered bullet points, so this is the second bullet point inside if the sixth bullet point under §5.19/2. I think I might have to talk to Pete Becker about whether it's possible to add some sort of numbers/letters/roman numerals down the hierarchy to identify pieces like this...