Сортировка вектора строк с ведущими числами

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);
}
}
}

Кроме того, я должен даже связать частоту со словом в первую очередь? Я знаю, что это грязно, поэтому я ищу более элегантное решение.

Спасибо!

2

c++file-io sorting word-frequency

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Если я вас понимаю, ваша проблема в том, что вы хотите отсортировать свой частотный вектор, но тогда вы теряете его соответствующее слово. Как и предполагалось, желательно использовать структуру с пользовательской функцией сравнения:

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 список.

0