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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (22)

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

#include <map>

int main()
{
    std::map<std::string, int> m;
    m.find("Olaf");
}
提问于
用户回答回答于

你的担忧是真实的,并且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 ++ 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");
    }
}
用户回答回答于

实际上没有办法强制find使用与用于创建不同的比较运算符map。如果你可以传递一个不同的东西find,它如何保证两个比较都能提供相同的顺序?

相反,只要想一下这些情况:

1)你正在通过char*你的程序。在这种情况下,不要那样做。std::string如果需要,可以使用一次,尽可能接近原点。然后不需要转换。

2)你正在尝试查找字符串文字。在这种情况下,为什么关键是string?使关键字成为一个很好命名的枚举类型:

enum names { OLAF };
map<names, int> m;
m.find(OLAF);

3)你想找到这两个字符串和C字符串文字。在这种情况下,我将创建一个由枚举索引的字符串全局查找表,但在main的开始处创建一次。然后你会打电话m.find(global_strings[OLAF]);

编辑:你似乎非常专注/关注string这里的性能影响。你有没有分析你的应用程序,并发现string分配是你应用程序时间的重要部分?我当然会相信这在嵌入式系统/设备上。

另外,你已经标记了你的问题C ++,但你似乎完全拒绝使用C ++内置的字符串特性,这远远不止“性价比”。它提供了各种有用的功能/方法/操作符,但最重要的是它为您管理内存,因此您不会花费数天或数周来查找毫无疑问会出现的真正隐患的错误。

如果你从网络读取可变长度的数据我不能完全把握之间的性能差异char* buffer = new char[needed_size];和类似的东西std::string s; s.resize(needed_size);以外,使用string提供了一定的安全和内存管理你。

扫码关注云+社区