对具有前导数字的字符串向量进行排序

Question

我正在做一道家庭作业，它要求我从输入文件中读入单词和一个整数 k。该解决方案需要打印出单词及其频率的列表，范围从最频繁到第 k 个最频繁。如果唯一单词的数量小于 k 则只输出该数量的单词。

如果使用像 map 这样的容器，这本来是小菜一碟，但问题限制了我只能使用向量和字符串，而不能使用其他 STL 容器。

我被困在我有一个文件中所有单词及其相应频率的列表的位置。现在我需要根据它们的频率对它们进行排序并输出 k 个单词。

问题是，排序很难。频率可以是不同的数字。如果我使用 string::sort() 通过填充零对它们进行排序，我将无法知道要填充多少个零，因为程序员不知道输入。

这是我的函数代码：

void word_frequencies(ifstream& inf, int k)
{
    vector <string> input;
    string w;
    while (inf >> w)
    {
        remove_punc(w);
        input.push_back(w);
    }
    sort(input.begin(), input.end());

    // initialize frequency vector
    vector <int> freq;
    for (size_t i = 0; i < input.size(); ++i) freq.push_back(1);

    // count actual frequencies
    int count = 0;
    for (size_t i = 0; i < input.size()-1; ++i)
    {
        if (input[i] == input[i+1])
        {
            ++count;
        } else
        {
            freq[i] += count;
            count = 0;
        }
    }

    // words+frequencies
    vector <string> wf;
    for (size_t i = 0; i < freq.size()-1; ++i)
    {

        if (freq[i] > 1 || is_unique(input, input[i]))
        {
            string s = to_string(freq[i]) + " " + input[i];
            wf.push_back(s);
        }
    }
}

此外，我是否应该首先将频率与单词结合起来？我知道这很麻烦，所以我正在寻找更优雅的解决方案。

谢谢！

Answer 1

如果我理解你的话，你的问题是你想对你的频率向量进行排序，但是你会忘记它们对应的词。正如建议的那样，使用带有自定义比较函数的结构可能是可取的：

struct word_freq {
    int freq;
    std::string word;
};

bool operator<(const word_freq& a, const word_freq& b) {
    return a.freq < b.freq;
}

现在，拥有 std::vector<word_freq> wf; 并应用 std::sort(wf.begin(), wf.end()) 应该可以让您的列表最小 -> 最大。要以最高频率打印 k 个单词，您可以从 wf 列表的后面打印。

对具有前导数字的字符串向量进行排序

Sorting vector of strings with leading numbers

c++

sorting

file-io

word-frequency