C++ unordered_map<string, ...> lookup without constructing string

Question

I have C++ code that investigates a BIG string and matches lots of substrings. As much as possible, I avoid constructing std::strings, by encoding substrings like this:

char* buffer, size_t bufferSize

At some point, however, I'd like to look up a substring in one of these:

std::unordered_map<std::string, Info> stringToInfo = {...

So, to do that, I go:

stringToInfo.find(std::string(buffer, bufferSize))

That constructs a std::string for the sole purpose of the lookup.

I feel like there's an optimization I could do here, by... changing the key-type of the unordered_map to some kind of temporary string imposter, a class like this...

class SubString
{
    char* buffer;
    size_t bufferSize;

    // ...
};

...的逻辑与std :: string相同，以进行哈希和比较，但销毁后不释放其缓冲区。

所以，我的问题是：是否有办法让标准类做到这一点，还是我自己编写此类？

Answer 1

您想要做的称为异构查找。从 C++14 开始，它就支持std::map::find和std::set::find（注意函数的版本 (3) 和 (4)，它们是在查找值类型上模板化的）。对于无序容器来说更复杂，因为它们需要被告知或找到所有键类型的哈希函数，这些函数将为相同的文本产生相同的哈希值。有一项关于未来标准的提案正在考虑中：http : //www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r0.html

同时，您可以使用另一个已经支持异构查找的库，例如boost::unordered_map::find.

如果您想坚持使用std::unordered_map，您可以通过std::string在您的旁边存储一个成员来避免创建如此多的临时字符串unordered_map，您可以将值重新分配给，然后将其传递string给find。您可以将其封装在自定义容器类中。

另一种方法是编写一个自定义类来用作您的无序容器键：

struct CharPtrOrString
{
    const char* p_;
    std::string s_;

    explicit CharPtrOrString(const char* p) : p_{p} { }
    CharPtrOrString(std::string s) : p_{nullptr}, s_{std::move(s)} { }

    bool operator==(const CharPtrOrString& x) const
    {
        return p_ ? x.p_ ? std::strcmp(p_, x.p_) == 0
                         : p_ == x.s_
                  : x.p_ ? s_ == x.p_
                         : s_ == x.s_;
    }

    struct Hash
    {
        size_t operator()(const CharPtrOrString& x) const
        {
            std::string_view sv{x.p_ ? x.p_ : x.s_.c_str()};
            return std::hash<std::string_view>()(sv);
        } 
    };
};

然后，您可以CharPtrOrString从std::strings构造用于无序容器键，但const char*每次调用find. 请注意，operator==上面必须确定您做了哪个（使用的约定是，如果指针的nullptr然后std::string成员正在使用），那么它会比较正在使用的成员。散列函数必须确保std::string具有特定文本值的 a 将产生与 a 相同的散列const char*（默认情况下它不会与 GCC 7.3 和/或 Clang 6 一起使用 - 我同时使用两者并记得一个有问题但不是哪个）。