1

我一直在玩一个使用 C++11 和一些标准算法的简单示例，我不确定是否std::accumulate使用std::for_each. 问题是计算单词中的字母，例如，对于“abracadabra”的输入，您会得到

'a' => 5
'b' => 2
'c' => 1
'd' => 1
'r' => 2

我的第一个削减是使用std::accumulate. 这看起来很自然的原因是我们实际上是在累积一个值（一组频率）。此外，我最近一直在做一些函数式编程，accumulate似乎是折叠列表的自然翻译。

vector<int> charsInWord(const string& text)
{
    return 
        std::accumulate(text.begin(), text.end(), vector<int>(256),
            [] (const vector<int>&v, char c)
            { 
                vector<int> v2(v);
                v2[c]++;
                return v2;
            } );
}

然而，这个解决方案似乎相当麻烦，需要一段时间才能正确。此外，即使有了新的move语义，我也不能完全说服自己不会有任何不必要的复制。

所以我去了for_each。

vector<int> charsInWord2(const string& text)
{
    vector<int> charCounts(256);
    std::for_each(text.begin(), text.end(),
        [&] (char c)
        {
            charCounts[c]++;
        } );
    return charCounts;
}

这可能更容易编写和理解，而且我当然对它的效率感到更满意（尽管我怀念 的声明式、函数式风格accumulate）。

在这样的例子中，有什么好的理由更喜欢其中一个吗？从到目前为止的评论和答案来看，如果我正在积累的价值不是微不足道的，比如一个stl容器而不是一个int，我应该总是更喜欢for_each，即使我真的在“积累”。

为了完整起见，编译和测试的其余代码如下

#include <string>
#include <vector>
#include <numeric> // accumulate
#include <algorithm> // for_each 

using std::string;
using std::vector;

#include <iostream>

// ... insert code above ...

int main(int argc, char* argv[])
{
    const vector<int> charCounts = charsInWord("abracadabra");
    for(size_t c=0; c<charCounts.size(); ++c) {
        const int count = charCounts[c];
        if (count > 0) {
            std::cout << "'" << static_cast<char>(c) << "'" << " => " << count << "\n";
        }
    }
    return 0;
}
4

1 回答 1

2

就我个人而言，我不会这样写累积：

vector<int> charsInWord(const string& text)
{
    std::vector<int> result(256); // One version never copied.

    int count = std::accumulate(text.begin(), text.end(), 0,
            [&result] (int count, char c)
         // ^^^^^^^^^ capture
            { 
                result[c]++;
                return count+1;
            } );
    // Might use count in the log file.
    return result;
}

但是如果我这样做，它似乎很容易使用 for_each()

vector<int> charsInWord2(const string& text)
{
    vector<int> result(256);
    std::for_each(text.begin(), text.end(),
        [&result] (char c)
        {
            result[c]++;
        } );
    return result;
}

我认为 for_each 版本没有任何问题。

但是为什么不使用一个简单的for()循环呢？

vector<int> charsInWord2(const string& text)
{
    vector<int> result(256);
    for(char c : text) {result[c]++;}
    return result;
}

在评论中有一些关于使用 std::map 的讨论（然后在一些已删除的问题中）。只是为了在这里捕捉并扩展。

我们可以使用std::map<char,int>而不是vector<int>. 区别在于：

From: @Davestd::map 的查找时间为 O(ln(n))，而向量为 O(1)。所以有性能方面的考虑。另请注意，地图的固定成本将高于矢量。虽然这很小但值得注意。

From: @Davestd::vector 的固定大小约为 256*4 (1024)，而 map 的大小约为 12* 唯一字符数（最小 12 最大 3072）。所以在现代机器中没有真正的空间考虑。但可能值得在手机等上进行优化。

From: @POW第三点是 std::map 使打印结果更容易，因为您不需要检查空值。

矢量打印

for(size_t c=0; c<charCounts.size(); ++c) {
    if (count > 0) {
        std::cout << "'" << static_cast<char>(c) << "' => " << charCounts[c] << "\n";
    }
}

地图打印

for(auto loop: charCounts) {
    std::cout << "'" << loop.first << "' => " << loop.second << "\n";
}
于 2013-09-15T17:38:14.533 回答