避免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
(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屋!