首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >避免std::map::find()的键构造

避免std::map::find()的键构造
EN

Stack Overflow用户
提问于 2012-05-10 22:59:58
回答 3查看 2.8K关注 0票数 25

假设我有一个std::map<std::string, int>。可以将std::string与没有std::string临时字符的C字符串(const char*)进行比较。然而,map::find()似乎迫使我构造一个临时的std::string,这可能需要一个内存分配。我该如何避免这种情况?从概念上讲,这很容易,但STL似乎阻止了这一点。

代码语言:javascript
复制
#include <map>

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

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-06-23 15:25:34

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

C++14通过添加std::map::find的模板重载解决了这个问题--相关的建议是N3657。在C++14中,您的程序将如下所示:

代码语言:javascript
复制
#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类型。

代码语言:javascript
复制
#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");
    }
}
票数 15
EN

Stack Overflow用户

发布于 2012-05-10 23:49:08

如果从文字构造字符串对您来说确实是一个性能瓶颈,那么您可以使用自己的类,而不是包含字符串或指向文字的指针的std::string。缺点是一些额外的复杂性,加上要插入到容器中的元素的指针大小。请注意,按照map的要求,该值是不可变的,因此存储c_str的结果是安全的。

代码语言:javascript
复制
class mystring
{
    std::string  str;
    const char * value;
public:
    mystring() : value(NULL)
    {
    }
    void setString(const std::string & s)
    {
        assert(value == NULL);
        str = s;
        value = str.c_str();
    }
    void setLiteral(const char * s)
    {
        assert(value == NULL);
        value = s;
    }
    bool operator<(const mystring & rhs)
    {
        return strcmp(literal, rhs.literal) < 0;
    }
};

std::map<mystring, int> m;
mystring text;
text.setString(some_key);
m.insert(std::make_pair(text, some_data));
// ...
mystring key;
key.setLiteral("Olaf");
m[key] = new_value;
票数 1
EN

Stack Overflow用户

发布于 2018-06-01 15:49:44

没有办法为map::find()函数专门定义一个比较器。相反,我建议您使用创建比较程序(myOwnCmp)并为您的程序删除std::map<char*, int, myOwnCmp>。对于非常大的程序或当测试用例的数量非常多时,它将相对比std::map<string, int>更快,因为通过调用字符串构造函数创建字符串,然后再调用其析构函数会消耗大量时间。使用const char*作为键将只涉及指针比较。

当您通过覆盖insert函数或创建您自己的add函数来填充map时,您需要注意的唯一一件事是创建char*的单独本地副本,该副本将作为参数出现,因为指针可能稍后会被修改或删除。因此,在将char*作为键添加到map之前,您需要确保保留了char*的本地副本。

代码应该是这样的:

代码语言:javascript
复制
 struct myOwnComp {
        bool operator()(const char* a, const char* b) const {
            return (strcmp(a, b) < 0);
        }
    };

std::map<char*, int, myOwnComp> mymap;

void addToMap(char*& ref, int value)
{
    char *key = new char[strlen(ref) + 1]{};
    std::copy(ref, ref + strlen(ref), key);
    mymap[key] = value;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10536788

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档