避免std::map::find()的键构造
假设我有一个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");
}回答 3
Stack Overflow用户
发布于 2014-06-23 15:25:34
您的担忧是实实在在的，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");
}
}Stack Overflow用户
发布于 2012-05-10 23:49:08
如果从文字构造字符串对您来说确实是一个性能瓶颈，那么您可以使用自己的类，而不是包含字符串或指向文字的指针的std::string。缺点是一些额外的复杂性，加上要插入到容器中的元素的指针大小。请注意，按照map的要求，该值是不可变的，因此存储c_str的结果是安全的。
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;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*的本地副本。
代码应该是这样的：
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;
}https://stackoverflow.com/questions/10536788
复制相似问题
腾讯云开发者
