C++ unordered_map<string, ...> 不构造字符串的查找

Question

我有 C++ 代码可以调查一个大字符串并匹配很多子字符串。我尽可能避免构造 std::strings，方法是像这样编码子字符串:

char* buffer, size_t bufferSize

然而，在某些时候，我想在其中一个中查找子字符串:

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

所以，为了做到这一点，我去:

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

构造一个 std::string 的唯一目的是查找。

我觉得我可以在这里做一个优化，通过...将 unordered_map 的键类型更改为某种临时字符串冒名顶替者，一个像这样的类...

class SubString
{
    char* buffer;
    size_t bufferSize;

    // ...
};

... 执行与 std::string 相同的逻辑来散列和比较，但在它被销毁时不会释放其缓冲区。

所以，我的问题是:是否有办法让标准类执行此操作，还是我自己编写此类？

Answer 1

您要执行的操作称为异构查找。自 C++14 起，它就支持 std::map::find 和 std::set::find (注意函数的版本 (3) 和 (4)，它们以查找值类型为模板)。对于无序容器来说更复杂，因为它们需要被告知或找到所有键类型的散列函数，这些散列函数将为相同的文本生成相同的散列值。有一项关于 future 标准的提案正在考虑中: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::string s 用于无序容器键，但可以从你的 const char* 中廉价地构建一个每次你打电话find .注意 operator==上面必须计算出你做了什么(使用的惯例是如果指针的 nullptr 则 std::string 成员正在使用中)所以它比较正在使用的成员。哈希函数必须确保 std::string具有特定文本值的哈希值将产生与 const char* 相同的哈希值(默认情况下，GCC 7.3 和/或 Clang 6 不会 - 我同时使用这两者，记得其中一个有问题，但不是哪个)。