我创建了一个小型解析器,并希望使循环部分尽可能快。因此,我想避免使用移动语义进行复制。但我不明白如何将移动语义和循环结合起来。我的循环看起来类似于此:
string word = "";
string s = "pip pip pop som"
unordered_map<string, int> dic;
for (char c : s) {
if ('a' <= c && c <= 'z') { // lower case
word.push_back(c);
}
else if ('A' <= c && c <= 'Z') { // upper case
word.push_back(c + 32);
}
else if (!word.empty()) { // word ended
++dic[word]; // I would like to avoid copying here
word.clear();
}
}
if (!word.empty()) {
++dic[word];
}
dic 将包含:
“som” 1
“pip” 2
“pop” 1
我尝试将std::move(word)
其放入dic
,但没有成功。您能否建议如何避免在此处复制并使用std::move
?遗憾的是我无法word
在循环内创建变量。
当我为这个问题举一个简单的例子时,它变得更加令人困惑:
#include <iostream>
#include <utility>
#include <map>
#include <ranges>
int main()
{
using namespace std;
map<string, int> m;
string word;
for (auto i : views::iota(0, 10)) {
word.push_back('a');
++m[word]; // I would like to avoid copying here
word.clear();
}
for (auto [word, count] : m) {
cout << word << ' ' << count << endl;
}
return 0;
}
根据您在第一个循环中写入的内容,输出将会有所不同。
word.push_back('a');
++m[word];
word.clear();
输出:
10
word.push_back('a');
++m[word];
输出:
1
aa 1
aaa 1
aaaa 1 aaaaa
1
aaaaaa 1
aaaaaaa 1
aaaaaaaa 1
aaaaaaaaa 1
aaaaaaaaaa 1
word.push_back('a');
++m[move(word)];
输出:
4
aa 3
aaa 2
aaaa 1
最后一个让我很困惑。看起来它并没有移动值,但它也没有在每次迭代中复制它。
我可以想象,为什么它不动——因为该变量word
正在下一次迭代中使用,并且它的寿命更长。
但为什么复制的这么混乱?
12
最佳答案
2
TL;DR:当您在下一次迭代中仍然需要它的值时,您无法通过移动而不是复制字符串来提高性能。
没什么奇怪的事情发生。
第一种情况:
word.push_back('a');
++m[word];
word.clear();
每次迭代时,您都会将 添加'a'
到字符串中,从而增加字符串 的计数"a"
,然后清除字符串,以空 开始下一次迭代word
。您重复 10 次。因此,循环后 的计数"a"
为10
。
下一案例:
word.push_back('a');
++m[word];
每次迭代你都会增加一个'a'
,word
并增加当前单词的计数word
。你这样做了 10 次。循环结束后,你增加了 10 个不同单词的计数,每个单词都比前一个单词长一个字符。
最后一种情况:
word.push_back('a');
++m[move(word)];
的移动构造函数std::string
使移动的字符串处于有效但未指定的状态(word
阅读更多信息)。原则上,从中移动后,的内容可以是任何内容。
您看到的是短字符串优化的效果。短字符串直接存储在 中std::string
。没有进行动态分配。因此,没有任何内容需要移动。移动短字符串实际上是在复制它。只有当字符串太长而无法使用短字符串优化时,移动后的字符串才为空。所有这些都不能指望。如上所述,移动的字符串处于未指定状态。当您仍然需要该值时,您不应该从它移动,当您需要从字符串移动为空时,您必须调用clear
。
我明白为什么它不动——因为变量字正在下一次迭代中使用,并且它的寿命更长。
你的理解在这一点上是错误的。++m[move(word)];
每次迭代都会移动字符串。在下一次迭代中使用该字符串是无关紧要的。通过调用,std::move(word)
你假装word
不再使用该字符串。如果你仍然使用它,你就得自己承担责任。
正如评论中提到的,只有当在地图中找不到++m[std::move(word)];
时才会移动。复制也是如此。只有当它不在地图中时才会复制。当它在地图中时,查找元素并增加它。例如,在第一种情况下,只制作了一个副本。word
++m[word];
word
[]
++
2
-
我明白了,在我的例子中,长度为 1-3 的字符串经过了优化,而长度为 4 的字符串没有,并且完全被移动了。虽然,在这种情况下它将是 4 4 2 2,仍然令人困惑,但这就是 UB 应该的样子 🙂
–
-
1@MaxCury 没有未定义的行为。它只是未指定。区别很重要。未指定仅意味着它取决于实现。未定义意味着它原则上可能取决于月相和水族馆的温度。stackoverflow.com/questions/2397984/
–
|
最后一个让我很困惑。它不会移动值,但也不会在每次迭代时复制它。
这是因为仅当键不在地图中时,地图才会构造一个键。
使用哪个构造函数取决于传入的类型operator[]
。当它是右值引用时,将对键进行移动构造,否则将对键进行复制构造。
因此,word
每次使用后都必须清除,即使可能在映射中移动构造新键。当键已经存在时,该字将不会用于移动构造,并且将保持不变。
作为参考,该映射存储的是(字符串,整数)对的元素:std::pair<std::string, int>
。
如果没有基准,很难说避免复制会有什么改变。但无论如何,让我们放纵一下:
#include <cstdio>
#include <string>
#include <unordered_map>
int main() {
std::string word = "";
std::string s = "pip pop pip som som som";
std::unordered_map<std::string, int> dic;
for (char c : s) {
if ('a' <= c && c <= 'z') { // lower case
word.push_back(c);
} else if ('A' <= c && c <= 'Z') { // upper case
word.push_back(c + 32);
} else if (!word.empty()) { // word ended
++dic[std::move(word)];
word.clear();
}
}
if (!word.empty()) { // word ended
++dic[std::move(word)];
}
for (const auto& pair : dic) {
printf("%s %d\n", pair.first.c_str(), pair.second);
}
}
值得注意的是:
-
std::move
实际上不移动任何东西。它是一种强制类型转换,允许在需要时进行移动构造。单词是否移动到字典键中取决于try_emplace
成功还是失败。当键已经存在时,它会失败。try_emplace
由接受右值引用的重载在内部使用operator[]
。 -
问题中最好有完整的、可用的代码,这样回答问题的人就可以将其粘贴到 IDE 或源文件中。这意味着您需要可用的代码,而不要包含与问题无关的部分,只需将其粘贴到问题中即可。
理想情况下,简短的 C 或 C++ 示例应该可以在 godbolt 上运行 – 这通常是任何人在回答问题时解决它们的最快方法。
,下面是输出:
som 3
pop 1
pip 2
对于基准测试,您应该熟悉。将代码从 godbolt 转移到 quick-bench 只需单击一下即可。
++dic[std::move(word)]
相当于:
const auto itbool = dic.try_emplace(std::move(word), int{});
++ itbool.first->second;
itbool
是std::pair<iterator, bool>
。迭代器对 进行迭代std::pair<key, value>
。因此,为了得到整数,我们首先通过 获得迭代器对itbool.first
,然后增加键值对的值(第二个)元素部分。
4
-
我必须注意,T&& 并不总是意味着右值引用(我在一次面试中犯了这样的错误,哈哈,现在我分享我的发现)
– -
PS:我在 514MB 圣经上进行了测量,是的,速度快了 10% – 平均而言,没有我的优化时为 55 秒,有我的优化时为 50 秒。
–
-
@MaxCury
concrete_type &&
总是表示右值引用。type_parameter &&
表示通用引用。所以你当然是对的,但这与此无关。我正确地使用了该术语。
– -
1@MaxCury 在没有看到代码的其余部分的情况下,我对此无话可说,尤其是您提到了复数优化。我几乎可以向您保证,在您的代码中,优化游戏中有更大的“鱼要炸”。使用使用池分配器的更快的字符串类可能是一个巨大的胜利,因为我想您一定分配了很多字符串。
–
|
if (c - 96u < 27u) { // 'a' <= c <= 'z'
此注释与条件看起来不一致。无效。–
–
–
–
–
|