避免std :: map :: find（）的关键构造 [英] Avoiding key construction for std::map::find()

问题描述

假设我有一个 std :: map< std :: string，int> 。 std :: string 可以与没有 std :: string 暂时的C字符串（const char *）进行比较。但是， map :: find（）似乎强迫我构造一个临时 std :: string 内存分配。如何避免这种情况？从概念上来说很容易，但STL似乎阻止了这一点。

Suppose I've got a std::map<std::string, int>. std::string can be compared to C strings (const char*) without std::string temporaries. However, map::find() appears to force me to construct a temporary std::string, which probably requires a memory allocation. How do I avoid this? Conceptually it's easy, but the STL appears to prevent this.

#include <map>

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

推荐答案

对于C ++ 11没有好的解决方法。

Your concern is real, and there's no good workaround for C++11.

C ++ 14通过添加 std :: map ::的模板化重载来修复此问题找到 - 相关投标是 N3657 < a>。在C ++ 14中，您的程序将如下所示：

C++14 fixes this issue by adding a templated overload of std::map::find — the relevant proposal is N3657. In C++14, your program would look like this:

#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有一个断开）

(std::less<> is the generalized "less-than" comparator, equivalent to operator<. C++03 and C++11 have a broken-by-design version of this comparator that forces both arguments to be the same type. C++14 finally does it right.)

不幸的是，委员会似乎已经决定，这个比较器的设计版本强制两个参数是相同的类型。人们应该通过所有的C ++ 11代码并更新每个容器以使用 std :: less<> 作为比较器 - 它不仅仅是默认的。这个决定没有好的理由;它只是它的方式。 （参见我上面关于破解设计的注释。）几年后，在引入真实版本之前，C ++有一个坏习惯来引入破碎版本的东西。）

Unfortunately the Committee seems to have decided that people should go through all their C++11 code and update every container to use std::less<> as the comparator — it doesn't just happen by default. There's no good reason for this decision; it's just The Way It Is. (See my comments above about broken-by-design. C++ has a bad habit of introducing broken versions of things before introducing the "real" versions several years later.)

对于C ++ 11， std :: map :: find 只有一个重载（ const Key& ），因此任何解决方法都必须涉及将 Key 类型更改为更便宜 - 我们不能仅仅比较比较器，因为当执行到达比较器时，我们已经提升了键类型的 find 的参数。

For C++11, std::map::find has only one overload (the one that takes const Key&), so any workaround will necessarily involve changing the Key type to be less expensive — we can't just fiddle with the comparator, because by the time execution reaches the comparator, we've already promoted find's argument to the Key type.

#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");
    }
}

这篇关于避免std :: map :: find（）的关键构造的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！