c++ - 避免 std::map::find() 的 key 构造

Question

假设我有一个 std::map<std::string, int> . std::string可以与没有 std::string 的 C 字符串 (const char*) 进行比较临时工。但是，map::find()似乎迫使我 build 一个临时的std::string ，这可能需要分配内存。我该如何避免这种情况？从概念上讲，这很容易，但 STL 似乎可以防止这种情况发生。

#include <map>

int main()
{
    std::map<std::string, int> m;
    m.find("Olaf");
}

Answer 1

您的担忧是真实的，C++11 没有好的解决方法。

C++14 通过添加 std::map::find 的模板化重载解决了这个问题。 ——相关提案为N3657 .在 C++14 中，您的程序将如下所示:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <algorithm>

class std_string {
    char *m_s;
public:
    std_string() { m_s = nullptr; }
    std_string(const char* s) { puts("Oops! A new std_string was constructed!"); m_s = strdup(s); }
    ~std_string() { free(m_s); }
    std_string(std_string&& ss) = delete;
    std_string(const std_string& ss) = delete;
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; }
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; }
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; }
};

int main()
{
    {
        puts("The C++11 way makes a copy...");
        std::map<std_string, int> m;
        auto it = m.find("Olaf");
    }
    {
        puts("The C++14 way doesn't...");
        std::map<std_string, int, std::less<>> m;
        auto it = m.find("Olaf");
    }
}

( std::less<> 是广义的“小于”比较器，等价于 operator<。C++03 和 C++11 有这个比较器的设计破坏版本，它强制两个参数都是相同的类型。C++14 终于做对了。)

不幸的是，委员会似乎已经决定人们应该检查他们所有的 C++11 代码并更新每个容器以使用 std::less<>作为比较器——它不只是默认发生。这个决定没有充分的理由；这就是它的方式。 (请参阅我上面关于设计破坏的评论。C++ 有一个坏习惯，即在几年后引入“真实”版本之前引入破坏版本。)

对于 C++11，std::map::find只有一个重载(需要 const Key& 的那个)，因此任何解决方法都必然涉及更改 Key类型更便宜——我们不能只摆弄比较器，因为当执行到达比较器时，我们已经提升了 find对 Key 的论点输入。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <algorithm>

class std_string {
    char *m_s;
public:
    std_string() : m_s(nullptr) { }
    std_string(const char* s) : m_s(strdup(s)) { puts("Oops! A new std_string was constructed!"); }
    ~std_string() { free(m_s); }
    std_string(std_string&& ss) : m_s(nullptr) { std::swap(m_s, ss.m_s); }
    std_string(const std_string& ss) : m_s(strdup(ss.data())) { puts("Oops! A new std_string was constructed!"); }
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;

    const char* data() const { return m_s; }

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; }
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; }
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; }
};

struct string_or_ptr {
    union {
        const char* ptr;
        alignas(std_string) unsigned char str[sizeof (std_string)];
    } m_u;
    bool m_deep;

    char const* & ptr() { return m_u.ptr; }
    std_string& str() { return *reinterpret_cast<std_string*>(m_u.str); }
    char const* const & ptr() const { return m_u.ptr; }
    std_string const& str() const { return *reinterpret_cast<const std_string*>(m_u.str); }

    string_or_ptr() : m_deep(false) { ptr() = ""; }
    string_or_ptr(const char* s) : m_deep(false) { ptr() = s; }
    string_or_ptr(std_string&& s) : m_deep(true) { new ((void*)&str()) std_string(std::move(s)); }
    string_or_ptr(const std_string& s) : m_deep(true) { new ((void*)&str()) std_string(s); }
    ~string_or_ptr() { if (m_deep) str().~std_string(); }
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;


    operator const char*() const { return m_deep ? str().data() : ptr(); }

    bool operator< (const char* s) const { return strcmp((const char*)*this, s) < 0; }
    bool operator< (const std_string& ss) const { return (const char*)*this < ss; }
    bool operator< (const string_or_ptr& sp) const { return strcmp((const char*)*this, (const char*)sp) < 0; }
    friend bool operator< (const char* s, const string_or_ptr& sp) { return strcmp(s, (const char*)sp) < 0; }
    friend bool operator< (const std_string& ss, const string_or_ptr& sp) { return ss < (const char*)sp; }
};

int main()
{
    {
        puts("The C++11 way...");
        std::map<std_string, int> m;
        auto it = m.find("Olaf");
    }
    {
        puts("The C++11 way with a custom string-or-pointer Key type...");
        std::map<string_or_ptr, int> m;
        auto it = m.find("Olaf");
    }
}