更好的计数方式？

Question

在我的一个学校程序中，我使用以下函数来计算字符串中标识符的频率，以换行符和 # 分隔：

输入：

dog
cat
mouse
#
rabbit
snake
#

函数：

//assume I have the proper includes, and am using namespace std
vector< pair<string,int> > getFreqcounts(string input) {
    vector<string> items = splitString(input,"\n");
    map<string,int> counts;

    for (int i=0; i<items.size(); i++) {
        if (items[i] == "#") continue;
        counts[items[i]] = 0;
    }
    for (int i=0; i<items.size(); i++) {
        if (items[i] == "#") continue;
        counts[items[i]]++;
    }

    return vector< pair<string,int> > (counts.begin(),counts.end());
}

我想至少

• 删除双 for 循环，
• 找到更好的方法得到一个向量对<字符串，整数> >

有什么想法吗？

顺便说一句，这不是家庭作业。真正的作业会使用这个功能，但这纯粹是出于我自己的好奇心和渴望拥有“更好”的代码。

Answer 1

我对 std::map 的理解是，整个第一个循环可以简单地消除。第一次尝试访问不存在的节点时，map 将为您默认创建它，并将初始计数设置为零（内置类型的默认构造函数行为）。是您需要对代码进行的所有更改，并且行为应该是相同的。

更新：在您提供的代码中的旁注中，counts 将根据为 std::string 定义的 operator< 进行排序 （地图的键类型），它将按字典顺序对 map 节点进行排序。无需通过向量抽取结果并对向量进行排序 - 地图会自动为您处理此操作。

Answer 2

您可以通过简单地删除第一个 for 循环来摆脱它。它没有完成任何有用的事情。当/如果映射中的下标创建一个新项目时，该项目将具有所选的键，并且关联的 int 将自动初始化为零。

就我个人而言，我可能会做一些不同的事情，使用 stringstream 而不是 SplitString()。我对发布代码犹豫不决，但我想我会相信你...

typedef vector<pair<string, int> > count_vec;

count_vec GetFreqCounts(string const &input) { 
    istringstream in(input);
    string line;
    map<string, int> counts;

    while (getline(in, line))
        if (line != "#")
            ++counts[line];
    return count_vec(counts.begin(), counts.end());
}

编辑：老实说，在我写这篇文章时，我并没有过多关注效率，但我认为 Steve Jessop 对此的评论非常漂亮准确的。只要输入很小，就不会产生任何真正的差异。如果输入确实很大，那么一次仅使用一个单词的额外副本这一事实可以节省足够的内存，从而变得有意义。

史蒂夫在回复中给出的解决方案看起来也很不错。由于它还会在生成单词时对其进行处理，因此我希望它具有与上面的代码类似的特征。如果您可以比 stringstream 更快地将字符串分解为单词，那么毫无疑问会更快。考虑到妨碍 iostream 的虚拟函数的数量，出现这种情况的可能性相当大——但除非您处理大量文本，否则产生重大影响的可能性不大。当然，究竟什么才是重要的，还有待商榷。为了正确地看待它，我在手边的单词列表中运行了一些类似的代码。使用与上面非常接近的代码，它以每秒 10 兆多一点的速度处理文本。

Answer 3

在对杰里回答的评论中，我提到使用函子。这就是我的意思（未经测试的代码）：

struct StringCounter {
    std::map<std::string, int> counts;
    void operator()(const std::string &s) {
        ++counts[s];
    }
};

template <typename Output>
void splitString(const string &input, const string &separator, Output &out) {
    // do whatever you currently do to get each string, call it "s"...
    out(s);
    // lather, rinse, repeat
}

vector< pair<string,int> > getFreqcounts(const string &input) {
    StringCounter sc;
    splitString(input,"\n",sc);
    return vector< pair<string,int> > (sc.counts.begin(),sc.counts.end());
}

Answer 4

如果您想保留当前逻辑但将所有逻辑包含在一个循环中，您可以使用 find()，如下所示：

map<string,int> counts;
loop on curr ..
map<string,int>::iterator it = counts.find(curr);
if (it != counts.end())
  ++it->second;
else
  counts[curr] = 1;

但这不是我会做的。第一次不需要显式初始化映射条目，因为它无论如何都会默认为零，所以您可以使用：

map<string,int> counts;
loop on curr ..
  if (..
    ++map[curr];

我要做的另一件事是使用 std::getline() 以 '\n' 和 '#' 为分隔符。