我创建了一个小型解析器,并希望使循环部分尽可能快。因此,我想避免使用移动语义进行复制。但我不明白如何将移动语义和循环结合起来。我的循环看起来类似于此:

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

  • 1
    if (c - 96u < 27u) { // 'a' <= c <= 'z'此注释与条件看起来不一致。无效。


    – 


  • 1
    我建议你了解一下。不需要那些检查。


    – 

  • 阅读,仅当键不存在时,移动才会起作用。对于你的情况,由于短字符串优化,移动永远不会起作用。


    – 


  • 2
    OT:移动字符串不会给你带来太多好处,因为在下一次迭代中你又需要填充一个字符串。你需要付出代价。要么是复制,要么是逐个向空字符串添加字符。


    – 


  • 2
    您的问题的第一行是最突出的。它是人们首先阅读的内容,并且显示在问题列表中(标题下)。这是您推销问题的机会,但您却浪费了它。您没有使用移动语义,而是在问题开头提到了线程,这不仅与您的问题无关,而且后面也没有提到。这是个坏主意。好问题通常不需要您讲述如何遇到它们的故事。在上下文可能很重要的情况下,上下文应该放在问题的末尾。


    – 


最佳答案
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);
    }
}

值得注意的是:

  1. std::move实际上不移动任何东西。它是一种强制类型转换,允许在需要时进行移动构造。单词是否移动到字典键中取决于try_emplace成功还是失败。当键已经存在时,它会失败。try_emplace由接受右值引用的重载在内部使用operator[]

  2. 问题中最好有完整的、可用的代码,这样回答问题的人就可以将其粘贴到 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;

itboolstd::pair<iterator, bool>。迭代器对 进行迭代std::pair<key, value>。因此,为了得到整数,我们首先通过 获得迭代器对itbool.first,然后增加键值对的值(第二个)元素部分。

4

  • 我必须注意,T&& 并不总是意味着右值引用(我在一次面试中犯了这样的错误,哈哈,现在我分享我的发现)


    – 

  • PS:我在 514MB 圣经上进行了测量,是的,速度快了 10% – 平均而言,没有我的优化时为 55 秒,有我的优化时为 50 秒。


    – 


  • @MaxCuryconcrete_type &&总是表示右值引用。type_parameter &&表示通用引用。所以你当然是对的,但这与此无关。我正确地使用了该术语。


    – 

  • 1
    @MaxCury 在没有看到代码的其余部分的情况下,我对此无话可说,尤其是您提到了复数优化。我几乎可以向您保证,在您的代码中,优化游戏中有更大的“鱼要炸”。使用使用池分配器的更快的字符串类可能是一个巨大的胜利,因为我想您一定分配了很多字符串。


    –