如何仅用C++ STL库实现字符串向量的频率映射？

我有一个std::vector<std::string>，想要统计其中每个单词的出现次数并存入std::map。已经试过std::count，但它只能统计单个单词的次数，不清楚怎么统计所有单词，有人提到可以用std::count_if配合lambda函数。

示例代码：

std::vector<string> words = {"the", "domestic", "cat", "has", "a", "smaller", "skull", "and", "shorter", "bones", "than", "the", "european", "cat", "males", "are", "larger", "than", "females", "a"};
std::cout << std::count (words.begin(), words.end(), "cat") << endl; //outputs 2

方法一：用std::for_each直接统计（最直观高效） #

这是最直接的实现方式，遍历整个vector，借助map的operator[]自动初始化计数并累加：

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::string> words = {"the", "domestic", "cat", "has", "a", "smaller", "skull", "and", "shorter", "bones", "than", "the", "european", "cat", "males", "are", "larger", "than", "females", "a"};
    std::map<std::string, int> count_map;

    std::for_each(words.begin(), words.end(), [&count_map](const std::string& word) {
        ++count_map[word];
    });

    // 输出统计结果
    for (const auto& pair : count_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

该方法的时间复杂度为O(n log n)，其中n为vector的元素总数——每次map插入/更新操作的时间是O(log k)（k为当前map中的不同元素数量），这是使用std::map时的最优复杂度。

方法二：先排序再用std::equal_range统计（内存局部性更优） #

如果vector元素数量极大，可先排序利用内存局部性提升实际运行效率，再通过std::equal_range批量统计每个单词的出现次数：

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::string> words = {"the", "domestic", "cat", "has", "a", "smaller", "skull", "and", "shorter", "bones", "than", "the", "european", "cat", "males", "are", "larger", "than", "females", "a"};
    std::map<std::string, int> count_map;

    // 先对vector排序
    std::sort(words.begin(), words.end());

    auto it = words.begin();
    while (it != words.end()) {
        // 找到当前单词的连续出现范围
        auto range = std::equal_range(it, words.end(), *it);
        // 统计次数并存入map
        count_map[*it] = std::distance(range.first, range.second);
        // 跳转到下一个不同的单词
        it = range.second;
    }

    // 输出统计结果
    for (const auto& pair : count_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

该方法的时间复杂度同样为O(n log n)，排序阶段耗时O(n log n)，后续遍历统计耗时O(n)，整体复杂度与方法一一致，但排序后连续访问元素的内存局部性更好，大数量级场景下可能有性能优势。

不推荐用std::count_if遍历统计的原因 #

若用std::count_if配合lambda逐个统计每个单词，需要先提取所有唯一单词，再对每个单词调用一次std::count_if，时间复杂度会达到O(n²)——每个唯一单词都要遍历整个vector，元素较多时效率极低，仅适用于极小规模数据集。

示例低效写法：

// 不推荐！效率低下
std::vector<std::string> unique_words = words;
std::sort(unique_words.begin(), unique_words.end());
auto last = std::unique(unique_words.begin(), unique_words.end());
unique_words.erase(last, unique_words.end());

std::map<std::string, int> count_map;
for (const auto& word : unique_words) {
    count_map[word] = std::count_if(words.begin(), words.end(), [&word](const std::string& w) {
        return w == word;
    });
}

内容的提问来源于stack exchange，提问作者hekk_tech