blocks|key|359603|text|如果从文字构造字符串对您来说确实是一个性能瓶颈，那么您可以使用自己的类，而不是包含字符串或指向文字的指针的std::string。缺点是一些额外的复杂性，加上要插入到容器中的元素的指针大小。请注意，按照map的要求，该值是不可变的，因此存储c_str的结果是安全的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|359604|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;|code-block|syntax|javascript|359605|entityMap^0|1H|B|2T|3|3C|5|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]|$9|R|A|S|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|T|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|U|8|@]|D|@]|E|$]]]|L|$]]

If the construction of a string from a literal is really a measured performance bottleneck for you, you can use your own class instead of a <code>std::string</code> that holds either a string or a pointer to a literal. The downside is some extra complication, plus adding the size of a pointer to the elements you're inserting into the container. Note that the value is immutable as required by <code>map</code>, so it's safe to store the results of <code>c_str</code>.

<pre><code>class mystring
{
 std::string str;
 const char * value;
public:
 mystring() : value(NULL)
 {
 }
 void setString(const std::string &amp; s)
 {
 assert(value == NULL);
 str = s;
 value = str.c_str();
 }
 void setLiteral(const char * s)
 {
 assert(value == NULL);
 value = s;
 }
 bool operator&lt;(const mystring &amp; rhs)
 {
 return strcmp(literal, rhs.literal) &lt; 0;
 }
};

std::map&lt;mystring, int&gt; m;
mystring text;
text.setString(some_key);
m.insert(std::make_pair(text, some_data));
// ...
mystring key;
key.setLiteral("Olaf");
m[key] = new_value;
</code></pre>

blocks|key|575406|text|您的担忧是实实在在的，C%2B%2B11没有好的解决方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|575407|C%2B%2B14通过添加std::map::find的模板重载解决了这个问题--相关的建议是N3657。在C%2B%2B14中，您的程序将如下所示：|offset|length|style|CODE|575408|#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%2B%2B11+way+makes+a+copy...");
++++++++std::map<std_string,+int>+m;
++++++++auto+it+=+m.find("Olaf");
++++}
++++{
++++++++puts("The+C%2B%2B14+way+doesn't...");
++++++++std::map<std_string,+int,+std::less<>>+m;
++++++++auto+it+=+m.find("Olaf");
++++}
}|code-block|syntax|javascript|575409|(std::less<>是广义的“小于”比较器，相当于operator<。C%2B%2B03和C%2B%2B11的这个比较器有一个被设计破坏的版本，它强制两个参数为同一类型。(+C%2B%2B14最终做到了这一点。)|575410|不幸的是，委员会似乎已经决定，人们应该检查他们所有的C%2B%2B11代码，并更新每个容器以使用std::less<>作为比较器-这不是默认情况下发生的。这个决定没有很好的理由；它就是这样的。(请参阅我上面关于被设计破坏的评论。C%2B%2B有一个坏习惯，那就是在几年后引入“真正的”版本之前，先引入一些不完整的版本。)|575411|对于C%2B%2B11，std::map::find只有一个重载(接受const+Key&的重载)，所以任何变通方法都必然涉及更改Key类型以降低开销-我们不能只摆弄比较器，因为当执行到达比较器时，我们已经将find的参数提升为Key类型。|575412|#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%2B%2B11+way...");
++++++++std::map<std_string,+int>+m;
++++++++auto+it+=+m.find("Olaf");
++++}
++++{
++++++++puts("The+C%2B%2B11+way+with+a+custom+string-or-pointer+Key+type...");
++++++++std::map<string_or_ptr,+int>+m;
++++++++auto+it+=+m.find("Olaf");
++++}
}|575413|entityMap|0|LINK|mutability|MUTABLE|url|http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3657.htm^0|0|9|E|17|5|0|0|0|1|B|R|9|0|18|B|0|8|E|V|A|1P|3|2S|4|32|3|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|13|8|@$D|14|E|15|F|G]]|9|@$D|16|E|17|1|18]]|A|$]]|$1|H|3|I|5|J|7|19|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|1A|8|@$D|1B|E|1C|F|G]|$D|1D|E|1E|F|G]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1F|8|@$D|1G|E|1H|F|G]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1I|8|@$D|1J|E|1K|F|G]|$D|1L|E|1M|F|G]|$D|1N|E|1O|F|G]|$D|1P|E|1Q|F|G]|$D|1R|E|1S|F|G]]|9|@]|A|$]]|$1|S|3|T|5|J|7|1T|8|@]|9|@]|A|$K|L]]|$1|U|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]]|V|$W|$5|X|Y|Z|A|$10|11]]]]

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

C++14 fixes this issue by adding a templated overload of <code>std::map::find</code> — the relevant proposal is <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3657.htm" rel="noreferrer">N3657</a>. In C++14, your program would look like this:

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;map&gt;
#include &lt;algorithm&gt;

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&amp;&amp; ss) = delete;
 std_string(const std_string&amp; ss) = delete;
 std_string&amp; operator=(std_string&amp;&amp; ss) = delete;
 std_string&amp; operator=(const std_string&amp; ss) = delete;

 bool operator&lt; (const char* s) const { return strcmp(m_s, s) &lt; 0; }
 bool operator&lt; (const std_string&amp; ss) const { return strcmp(m_s, ss.m_s) &lt; 0; }
 friend bool operator&lt; (const char* s, const std_string&amp; ss) { return strcmp(s, ss.m_s) &lt; 0; }
};

int main()
{
 {
 puts("The C++11 way makes a copy...");
 std::map&lt;std_string, int&gt; m;
 auto it = m.find("Olaf");
 }
 {
 puts("The C++14 way doesn't...");
 std::map&lt;std_string, int, std::less&lt;&gt;&gt; m;
 auto it = m.find("Olaf");
 }
}
</code></pre>

(<code>std::less&lt;&gt;</code> is the generalized "less-than" comparator, equivalent to <code>operator&lt;</code>. 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.)

Unfortunately the Committee seems to have decided that people should go through all their C++11 code and update every container to use <code>std::less&lt;&gt;</code> 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.)

For C++11, <code>std::map::find</code> has only one overload (the one that takes <code>const Key&amp;</code>), so any workaround will necessarily involve changing the <code>Key</code> 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 <code>find</code>'s argument to the <code>Key</code> type.

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;map&gt;
#include &lt;algorithm&gt;

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&amp;&amp; ss) : m_s(nullptr) { std::swap(m_s, ss.m_s); }
 std_string(const std_string&amp; ss) : m_s(strdup(ss.data())) { puts("Oops! A new std_string was constructed!"); }
 std_string&amp; operator=(std_string&amp;&amp; ss) = delete;
 std_string&amp; operator=(const std_string&amp; ss) = delete;

 const char* data() const { return m_s; }

 bool operator&lt; (const char* s) const { return strcmp(m_s, s) &lt; 0; }
 bool operator&lt; (const std_string&amp; ss) const { return strcmp(m_s, ss.m_s) &lt; 0; }
 friend bool operator&lt; (const char* s, const std_string&amp; ss) { return strcmp(s, ss.m_s) &lt; 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* &amp; ptr() { return m_u.ptr; }
 std_string&amp; str() { return *reinterpret_cast&lt;std_string*&gt;(m_u.str); }
 char const* const &amp; ptr() const { return m_u.ptr; }
 std_string const&amp; str() const { return *reinterpret_cast&lt;const std_string*&gt;(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&amp;&amp; s) : m_deep(true) { new ((void*)&amp;str()) std_string(std::move(s)); }
 string_or_ptr(const std_string&amp; s) : m_deep(true) { new ((void*)&amp;str()) std_string(s); }
 ~string_or_ptr() { if (m_deep) str().~std_string(); }
 std_string&amp; operator=(std_string&amp;&amp; ss) = delete;
 std_string&amp; operator=(const std_string&amp; ss) = delete;


 operator const char*() const { return m_deep ? str().data() : ptr(); }

 bool operator&lt; (const char* s) const { return strcmp((const char*)*this, s) &lt; 0; }
 bool operator&lt; (const std_string&amp; ss) const { return (const char*)*this &lt; ss; }
 bool operator&lt; (const string_or_ptr&amp; sp) const { return strcmp((const char*)*this, (const char*)sp) &lt; 0; }
 friend bool operator&lt; (const char* s, const string_or_ptr&amp; sp) { return strcmp(s, (const char*)sp) &lt; 0; }
 friend bool operator&lt; (const std_string&amp; ss, const string_or_ptr&amp; sp) { return ss &lt; (const char*)sp; }
};

int main()
{
 {
 puts("The C++11 way...");
 std::map&lt;std_string, int&gt; m;
 auto it = m.find("Olaf");
 }
 {
 puts("The C++11 way with a custom string-or-pointer Key type...");
 std::map&lt;string_or_ptr, int&gt; m;
 auto it = m.find("Olaf");
 }
}
</code></pre>

blocks|key|359723|text|没有办法为map::find()函数专门定义一个比较器。相反，我建议您使用创建比较程序(myOwnCmp)并为您的程序删除std::map<char*,+int,+myOwnCmp>。对于非常大的程序或当测试用例的数量非常多时，它将相对比std::map<string,+int>更快，因为通过调用字符串构造函数创建字符串，然后再调用其析构函数会消耗大量时间。使用const+char*作为键将只涉及指针比较。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|359724|当您通过覆盖insert函数或创建您自己的add函数来填充map时，您需要注意的唯一一件事是创建char*的单独本地副本，该副本将作为参数出现，因为指针可能稍后会被修改或删除。因此，在将char*作为键添加到map之前，您需要确保保留了char*的本地副本。|359725|代码应该是这样的：|359726|+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)+%2B+1]{};
++++std::copy(ref,+ref+%2B+strlen(ref),+key);
++++mymap[key]+=+value;
}|code-block|syntax|javascript|359727|entityMap^0|5|B|1P|U|3B|L|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]|$9|T|A|U|B|C]|$9|V|A|W|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|X|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|Y|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|Z|8|@]|D|@]|E|$M|N]]|$1|O|3|-4|5|6|7|10|8|@]|D|@]|E|$]]]|P|$]]

There is no way to specifically define a comparator for <code>map::find()</code> function. Instead I would advice you to use create your comparator (myOwnCmp) and delcare a <code>std::map&lt;char*, int, myOwnCmp&gt;</code> for your program. For very large programs or when the number of testcases are very high, it will be comparatively faster than <code>std::map&lt;string, int&gt;</code> because the time spend to create a string by calling the string constructor and later calling its destructor consumes significant amount of time. Using const char* as the key will only involve pointer comparison.

The only thing you need to take care of is to make a separate local copy of the char* coming as an argument when you are populating the map by overriding the insert function or by creating your own add function, because there are chances that the pointer can later be modified or deleted. So you want to make sure that you have kept a local copy of the char* before adding it as the key to the map.

The code would go something like this:-

<pre><code> struct myOwnComp {
 bool operator()(const char* a, const char* b) const {
 return (strcmp(a, b) &lt; 0);
 }
 };

std::map&lt;char*, int, myOwnComp&gt; mymap;

void addToMap(char*&amp; ref, int value)
{
 char *key = new char[strlen(ref) + 1]{};
 std::copy(ref, ref + strlen(ref), key);
 mymap[key] = value;
}
</code></pre>

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

<pre><code>#include &lt;map&gt;

int main()
{
 std::map&lt;std::string, int&gt; m;
 m.find("Olaf");
}
</code></pre>

Avoiding key construction for std::map::find()

容器

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

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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