[C++ CODE] First Non Repeating Char in String

I'd have thought this would be effective:

std::string::value_type firstNonRep(std::string const & s) {
    std::unordered_set<std::string::value_type> chars;
    for (auto c : s) {
        bool ok;
        std::tie(std::ignore, ok) = chars.insert(c);
        if (!ok) return c;
    }
    return '_';
}

That's one linear scan of the portion of the string up to and including the repeated character, plus a search which might be linear, but is more likely constant. While the memory usage varies according to the number of non-repeated characters prior to the first repeated character, it will be relatively efficient. Constant memory doesn't always mean low memory, of course, and the advantage of this construct is that it's trivially templatized for Unicode strings etc.

We can reduce the memory slightly by using a trivial Bloom filter instead:

std::string::value_type firstNonRep(std::string const & s) {
    unsigned long long bloom;
    std::unordered_set<std::string::value_type> chars;
    for (auto c : s) {
        unsigned long long chk = c + ((c % 13) << 8);
        auto old_bloom = bloom;
        bloom |= chk;
        if (old_bloom != bloom) continue;
        bool ok;
        std::tie(std::ignore, ok) = chars.insert(c);
        if (!ok) return c;
    }
    return '_';
}

If you really want to enforce the O(n)/O(1), though, we need to do two things:

1) We won't exit the loop early. That will slow the algorithm down to the level you need.

2) Use a custom allocator to ensure that enough memory for any situation is allocated. This will dramatically increase memory, but allow it to be constant.

The fact both of these make the algorithm demonstrably worse is why I don't like these kinds of artificial constraints...

Updated the post with the problem link!! (There are sample test cases to test your code!!)