Быстрая сортировка слов из текста

[matrosken]

Язык C++ ;Задача такая : Дан файл 1.txt (в нем содержится текс романа “Война и мир”). Необходимо в файл 2.txt выписать все встречающиеся слова (по одному в строке) с сортировкой по уменьшению частоты появления этого слова (слова учитываются без знаков препинания и длиной не менее 4х символов). Необходимо вывести на экран время работы программы.

Вопрос в том что здесь лучше использовать чтобы время было минимальным ( VS 2008 )

[sabbathist]

Используете map, где храните по ключу типа "стринг" значение типа "инт", которое будет показывать, сколько раз встречается слово. Потом закидываете в массив из мэпа пары "стринг-инт" и вызываете встроенную сортировку с компаратором по частоте встречания. Сложность будет
O(nlogn+t+klogk)=O(max(t,klogk)), где n - количество уникальных слов, t-количество символов в тексте, k- количество всех слов.

Для замера времени есть встроенные функции (названия не помню). Посмотрите на cplusplus.com/reference

[matrosken]

Какой массив стринг-инт? и какая встроенная сортировка?

[sabbathist]

массив лучше всего реализовывать как вектор пар. встроенную сортировку вызываете так:
sort(v.begin(),v.end(),comp), где v - ваш вектор пар ,а comp - компаратор (его напишете сами) булевского типа.


В начале программы не забудьте

 #include <algorithm>

- там лежит sort

[matrosken]

bool my_greater(pair<string, int> const& x, pair<string, int> const& y)
{
    return x.second > y.second;
}

 . . .

    typedef map<string, int> my_map_t;
    my_map_t my_map;
    // fill my_map here
    typedef vector<pair<string, int> > my_vector_t;
    my_vector_t my_vector;
    copy(my_map.begin(), my_map.end(), back_inserter(my_vector));
    sort(my_vector.begin(), my_vector.end(), my_greater);

надо бы так, только почему то когда пишу map<string,int> откудато появляются 17 ошибок зато если написать const char* вместо string то они исчезают и вроде как работает

[sabbathist]

Хм. Интересно. Возможно, вы чего-то не договариваете). Но если работает - думаю, вы не в обиде.

[matrosken]

не знаю
правда не const char* а char*
string не работает не знаю почему

[matrosken]

какую функцию из fstream мне нужно взять для того чтоб слова выбирать нормально?
и вопрос еще уменьшится ли в данном случае время если подключить два потока ( правда я сам не знаю как это сделать)
как вывести такой вектор в файл?

[sabbathist]

Ну, я слова выбирал след. образом: читал весь текст, а потом парсил руками. два потока через fopen (как им пользоваться - на cplusplus.com/reference а сам я не помню : ). при выводе пишете не сout имя подгруженного потока (вроде бы). если поток вывода перегружать через freope, то можно и cout.

[matrosken]

Спасибо за помощь