[pva]

Код:

#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main()
{
// контейнер для подсчёта
  map<int,unsigned> sym_count;
// контейнер для сортировки
  map<unsigned,int> sym_sorted;


// 1. берём числа из потока и считаем их повторения
  for(istream_iterator<int,char> first(cin), last; first!=last; ++first)
  {
     ++sym_count[*first];
  }

// 2. сортируем (пользуемся тем, что map всегда содержит сортированный список)
  for(map<int,unsigned>::iterator first(sym_count.begin()), last(sym_count.end()); first!=last; ++first)
  {
    sym_sorted[first->second] = first->first;
  }

// 3. выводим на экран
  for(map<unsigned,int>::reverse_iterator first(sym_sorted.rbegin()), last(sym_sorted.rend()); first!=last; ++first)
  {
    cout << first->second << ": " << first->first << "\n";
  }
}

Есть ещё варианты с явной сортировкой, то есть скопировать загруженный map в list и отсортировать его по критерию.
Пример с использованием шаблонов перебора

Код:

// достоинство - модульность (причём иерархическая)
string output_format(const pair<unsigned,int>& a);

struct calc_sym_count_t
{
  map<int,unsigned> _count;

  void operator()(const int& n)
  {
    ++_count[n];
  }
};

struct sort_sym_t
{
  map<unsigned,int> _sorted;

  void operator()(const pair<int,unsigned>& _count)
  {
    _sorted[_count.second] = _count.first;
  }
};

string output_format(const pair<unsigned,int>& a)
{
  ostringstream os;
  os << setw(10) << a.second << ": " << a.first;
  return os.str();
}

int main()
{
  calc_sym_count_t calc_sym_count;
  sort_sym_t sort_sym;

  // достоинство - лёгкость чтения:
  // для каждого от начала до конца посчитать кол-во символов
  for_each(istream_iterator<int,char>(cin), istream_iterator<int,char>(), calc_sym_count);
  // для каждого от начала до конца кол-ва символов сортировать
  for_each(calc_sym_count._count.begin(), calc_sym_count._count.end(), sort_sym);
  // преобразовать сортированные символы в поток вывода с использованием формата
  transform(sort_sym._sorted.rbegin(), sort_sym._sorted.rend(), ostream_iterator<string,char>(cout, "\n"), output_format_t);
}