CODEWITHSUNDEEP
c++hash
sinatrablue
sinatrablue

Reputation: 41

Hash function to switch on a string

I am trying to get to work a switch on a string in C++, with the help of a hash. It became personal between me and this code, so I don't wanna give up and use an enum, even though I finally have only like 8 strings to put in switch cases.

Combining what I saw on other topics, I wrote this very simple and not so reliable function, but that is enough for what I want to do, as it's not professional.

My function :

constexpr long hashstr (const string &str, int h=0)
{
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];
}

I then call it in this very simple main function (for now), but it won't compile, telling me that the case is wrong (not a constant). I don't understand this issue, as for me the string taken in arg is a constant, plus the function returns a constant expression.

My main :

int main (void) {

    string teststr;
    cout << "test string :::>  ";
    cin >> teststr;
    int tt = hashstr(teststr);
    cout << "res -->  " << tt << endl;

    switch ( hashstr(teststr) )
    {
    case hashstr("rosathefloridaturtle") :
        cout << "ROSA OK" << endl;
        break;

    default:
        cout << "ERROR" << endl;
        break;
    }

    return EXIT_SUCCESS;
}

Hoping that some of you can tell me what I'm not doing right...

Upvotes: 3

Views: 1693

Answers (2)

SHP
SHP

Reputation: 315

As what @Alan Birtles said, std::string is not a constexpr based on the compiler standard you currently use, thus you cannot use like this.

But one good news is that you don't need to use std::string_view !, you just need to use std::string::c_str() and use the char pointer to get the hash value.

Also, based on the demand, I think you may want to use a technique called natural overflow which is widely used in hash(actually, it's a modulo function, but remove modulo operator which also stands modulo MAX_VALUE), but the type it uses is unsigned integer, and as what's mentioned by Alan, signed overflow may trigger a ub. So use an unsigned type instead.

Here's a code I implemented for this usage.

#include <iostream>
#include <string>

using namespace std;

using ull = uint64_t;

constexpr ull hashstr(const char* s, size_t index = 0) {
    return s + index == nullptr || s[index] == '\0' ? 55 : hashstr(s, index + 1) * 33 + (unsigned char)(s[index]);
}

constexpr const char* a = "rosathefloridaturtle";

int main() {
    string s;
    cout << "test string :::>  ";
    cin >> s;
    ull tt = hashstr(s.c_str());
    cout << "res -->  " << tt << endl;
    switch (tt) {
        case hashstr(a):
            cout << "ROSA OK" << endl;
            break;
        default:
            cout << "ERROR" << endl;
            break;
    }
    return 0;
}

Upvotes: 3

Alan Birtles
Alan Birtles

Reputation: 36379

Unless you are using c++20 std::string is not constexpr so can't be used in hashstr.

The value returned is larger than is representable in long, as signed arithmetic overflow is undefined behaviour your code can't be used in constexpr.

Fixing these two issues gives the working code:

constexpr unsigned long hashstr (const std::string_view &str, int h=0)
{
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)(str[h]);
}

Note that if you look at the compiler output it probably tells you why your expression isn't constexpr, e.g. clang prints:

error: case value is not a constant expression
    case hashstr("rosathefloridaturtle") :
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:22:18: note: non-literal type 'const std::string' (aka 'const basic_string<char>') cannot be used in a constant expression
    case hashstr("rosathefloridaturtle") :

Changing to std::string_view prints:

error: case value is not a constant expression
    case hashstr("rosathefloridaturtle") :
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:9:47: note: value 97009635813568987014 is outside the range of representable values of type 'long'
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];
                                              ^
<source>:9:29: note: in call to 'hashstr("rosathefloridaturtle", 8)'
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];

Upvotes: 5

Related Questions