3. Отсортированные списки №2

☰ Теория

Порядок в std::map определяется только сравнением ключей, поэтому “сортировать по значениям” напрямую нельзя.

Обычно алгоритм в похожих задачах такой:

  1. считаем частоты слов в словаре,
  2. затем переносим пары (слово, частота) в вектор
  3. и сортируем вектор компаратором:
    • сначала по частоте по убыванию,
    • а при равенстве — по слову в лексикографическом порядке.

Ассимптотика

подсчет в map — примерно O(nlog⁡m), в unordered_map — амортизированно O(n),
сортировка вектора из m уникальных слов — O(mlogm).
 

Создание вектора пар из словаря

map<string, int> freq;
...
vector< pair<string, int> > items(freq.begin(), freq.end());
Это выражение использует так называемый “диапазонный” конструктор std::vector, который принимает два итератора first и last и создаёт вектор из элементов полуинтервала.
В указанном примерем first = freq.begin(), а last = freq.end(), поэтому создаётся vector<pair<string,int>> items, в который последовательно копируются элементы из указанного диапазона источника без пропусков и дубликатов в пределах этого полуинтервала.

 

Построить алфавитно-частотный словарь отсортированный по частоте слов: список слов, справа от каждого слова должно быть указано, сколько раз оно встречается в исходном файле в порядке убывания. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке. Признаком окончания текста является "END!". 
Примеры
№Входные данныеВыходные данные
1 один
два
три
один
два
END! 
два 2
один 2
три 1
Вставьте недостающие фрагменты кода
C++ 
#include<iostream>
#include<vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;


bool cmp(const pair<string, int>& first,
	const pair<string, int>& second)
{          
}


int main()
{

	map<string, int> mymap;
	string s;
	while (!cin.eof())
	{
		cin>>s;
                 if (s == "END!")
			break;
		mymap[s]++;
	}
	
	vector<pair <string, int> > B( mymap.begin(), mymap.end());
          
	for (int i = 0; i < B.size(); i++)
	{
		cout << B[i].first << " " << B[i].second << endl;

	}
	return 0;
}
     

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!