Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.62
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
#1

Отсортировать контейнер map по значению элементов - C++

08.04.2011, 00:31. Просмотров 4969. Ответов 14
Метки нет (Все метки)

Есть заполненный контейнер unordered_map (ну или просто map)
Нужно отсортировать его по значению или сделать сортированный по значению вывод (в случае с map возможен только сортированный вывод, т.к. он сам сортируется по ключу)
Вот накатал код заполения и вывода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
    {
      std::unordered_map<int, int> Employees;
      Employees[5234] = 1;
      Employees[3374] = 2;
      Employees[1923] = 3;
      Employees[7582] = 5;
      Employees[5328] = 6;
 
      std::cout << "Employees[3374]=" << Employees[3374] << std::endl << std::endl;
      std::cout << "Map size: " << Employees.size() << std::endl;
 
      for( std::unordered_map<int,int>::iterator ii=Employees.begin(); ii!=Employees.end(); ++ii)
       {
            std::cout << (*ii).first << ": " << (*ii).second << std::endl;
       }
      return 0;
}
Выводит:
Map size: 5
7582: 5
5328: 6
3374: 2
1923: 3
5234: 1
Нужно получить такой результат:
Map size: 5
5328: 6
7582: 5
1923: 3
3374: 2
5234: 1
Т.е. отсортированный по убыванию.
Подскажите как это сделать
Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2011, 00:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Отсортировать контейнер map по значению элементов (C++):

Контейнер map с сохранением порядка вставки элементов - C++
Можно ли в контейнере расположить ключи так, чтобы они не были отсортированы в порядке убывания или возрастания. Например я ложу в...

Контейнер map. Осуществить ввод элементов и поиск по ключу - C++
Поиск работает, но как сделать чтобы чтобы можно было вводить элементы с клавиатуры и искать по ключу вводом с клавиатуры? #include...

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map? - C++
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std map? Например: std::map...

Контейнер map - C++
в программе используется ассоциативный массив, идентификатором которого являются символы проблема в том что появляется элемент с...

Контейнер map - C++
Здравствуйте, работаю с контейнером map, анализирую текст, получаю записи типа &quot;слово: число его появлений в тексте&quot;. Хотелось бы вывести...

Контейнер map - C++
Стоит задача реализовать контейнер map. Вопрос возникает при реализации итератора для этого контейнера. В итераторе должны быть реализованы...

14
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
08.04.2011, 01:07 #2
Union, Саму мапу отсортировать по значению анриал - ибо мап есть красно-черное дерево.
Проще всего по-моему поменять ключ и значение местами при заполнении.
Или же перекинуть значения в какой-нибудь вектор пар.
0
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
09.04.2011, 21:03  [ТС] #3
Саму мапу отсортировать по значению анриал
Признаю, тему назвал некорректно... но вы всеравно плохо прочитали, я про это написал вверху.
Отсортировать нельзя, а сделать отсортированный вывод можно.
А вот unordered_map можно и отсортировать.
Только вот как это сделать правильнее?

Добавлено через 5 часов 32 минуты
Не нашел на просторах интернета решения, хотя казалось бы необходимость в решении подобной задачи встречается очень часто, например при выводе самых частоповторяющихсе букв или слов в тексте т.д. в любой статистике.
Есть идея, сделать второй multimap, скопировать в него все элементы из unordered map, только наоборот, т.е. ключ -> значение, значение -> ключ, а дальше они получатся отсортированными.
Но полагаю это будет очень медленно...
подскажите как решить задачу правильно, а не через велосипед
0
Ma3a
Эксперт С++
618 / 462 / 31
Регистрация: 28.01.2011
Сообщений: 605
09.04.2011, 21:11 #4
Цитата Сообщение от Union Посмотреть сообщение
Есть идея, сделать второй multimap, скопировать в него все элементы из unordered map, только наоборот, т.е. ключ -> значение, значение -> ключ, а дальше они получатся отсортированными.
Но полагаю это будет очень медленно...
Да, будет медленно, но кроме как перекидывать в другой контейнер особо-то способа и не подберешь, а вообще я бы рассмотрел возможность замены unordered_map в данном случае просто сортированным вектором пар, если нужно время от времени сортировать. С другой стороны, если предполагается частый поиск или изменение размеров, то вектор отпадает. А чем вообще вызван выбор конкретно unordered_map, соображениями производительности или чем-то другим? если не особо критичен выбор именно этого контейнера, то возможно стоит отказаться в пользу либо просто map, либо , как уже упоминал ранее, сортированных векторов.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
09.04.2011, 21:29 #5
не использовать map, а использовать deque c сортировкой, вставкой и поиском
0
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
09.04.2011, 23:23  [ТС] #6
Опишу подробнее что мне нужно от контейнера.
Я загружаю текст, и далее считываю его по словам и добавляю эти слова в контейнер со значением 0. Если слово уже есть, то инкрементирую значение, т.е. увеличиваю счетчик на 1.
В итоге после всего я получу контейнер, где ключ уникален - это слово и значение - количество раз, которое это слово встречается в тексте.
После мне нужно сохранить это в файл или базу, но в осортированном виде, чтобы вверху было наиболее частовстречаемое слово, а внизу наиболее редковстречаемое, ну и сбоку выводить сколько именно раз слово встретилось в тексте. Вот в общем-то и всё, никаких других операций я над контейнером проводить не собираюсь.

Контейнер выбираю чисто из соображений функций.
Вставлять буду очень часто, всего около 600000 слов, а выводить всего 1 раз, после того, как приложение отработает.
Насчёт вектора думал, но опять же я не так хорошо знаком с stl, чтобы разобраться как отсортировать его по значению,.. да и заполнять,... и как-то не рекомендуют его использовать для хранения пары ключ <-> значение... в общем у меня нет представления как это организовать

Добавлено через 41 минуту
Напишите пожалуйста реализации операции вставки, поиска по ключу, инкремент ключа и сортировку по ключу у вектора:
std::vector<pair<int, char[39]> > wave;
я вообще не представляю себе как это сделать...
может быть даже вместо pair стоит использовать структуру?

Добавлено через 1 час 6 минут
Вот попробовал сделать вставку:
C++
1
2
      std::vector<std::pair<int, char[39]> > wave;
      wave.insert(std::make_pair<int, char[39]>(10, "wwer"));
не работает, что я сделал неправильно?
0
Ma3a
Эксперт С++
618 / 462 / 31
Регистрация: 28.01.2011
Сообщений: 605
09.04.2011, 23:28 #7
Union, лучше использовать push_back например, тогда должно работать. Не работает потому что insert нужен еще как минимум один параметр - итератор, куда надо вставлять.
0
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
09.04.2011, 23:36  [ТС] #8
Да, точно. Пытаюсь разобратся по аналогии с map и другими контейнерами...
Вот так тоже не вышло
C++
1
2
      std::vector<std::pair<int, char[39]> > waves;
      waves.push_back(std::make_pair<int, char[39]>(10, 'w'))
Также попробовал вместо pair использовать структуру, и тоже не вышло. В инете нет примеров вообще....
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
09.04.2011, 23:41 #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <deque>
#include <utility>
#include <algorithm>
#include <cstring>
#include <vector>
#include <functional>
#include <boost/format.hpp>
#include <iostream>
 
typedef char*                       Element;
typedef std::pair<int, Element>     Pair;
typedef std::deque<Pair>            Container;
 
std::vector<Element> arr
                  = { 
                      "hello",
                      "world",
                      "where",
                      "are",
                      "hello",
                      "you",
                      "are", "you" 
                    };     
 
bool comp_pair( const Pair& first, const Pair& second )
{
   
   int res = strcmp( first.second, second.second );
   return res <= 0; 
}
 
int insert( Container& container, const Element& element )
{
   
   Pair pair = { 1, element };
   Container::iterator it = 
      std::upper_bound( container.begin(), container.end(), pair,
                        comp_pair );
   if( it == container.end() ||
       0 != strcmp( it->second, element ) )
   {
      container.insert( it, pair );
   } 
   else
   {
      ++it->first;
   }   
   return it->first;
}
 
int main()
{
    Container dict;
    std::for_each( arr.begin(), arr.end(), [&dict](const Element el)
    {
       insert( dict, el );
    });
    std::for_each( dict.begin(), dict.end(), [](const Pair& pair)
    {
       std::cout << boost::format( "[%3d] - %s" )
                 % pair.first % pair.second
                 << std::endl;    
    });    
}
http://liveworkspace.org/code/649bd1e90fbb054c9718c2ec66ac4980

время поиска элемента - log(N), так же как и у мапа
1
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
10.04.2011, 00:22  [ТС] #10
Воспользуюсь вашим вариантом, спасибо
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
10.04.2011, 00:38 #11
А еще юзать бы string раз юзается STL...
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
10.04.2011, 00:50 #12
Ну, если вставка критична по времени, то лучше ассоциативный контейнер использовать:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                       T_str;
typedef std::map       <T_str,  size_t >  T_word_counter;
typedef std::multimap  <size_t, T_str  >  T_word_of_counter;
/////////////////////////////////////////////////////////////////////////////////////////
T_str  get_random_text()
{
    const char  SIMB_MIN     = 'a';
    const char  SIMB_MAX     = 'b';
    const int   WORD_LEN     = 3;
    const int   WORDS_TOTAL  = 10; 
 
    T_str       text;
    for(int word_ind = 0; word_ind < WORDS_TOTAL; ++word_ind)
    {
        T_str  word;
        for(int  symb_ind = 0; symb_ind < WORD_LEN; ++symb_ind)
        {
            word += rand() %  (SIMB_MAX - SIMB_MIN + 1) + SIMB_MIN;            
        }
        text += word + ' ';
    }
    return  text;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_word_counter  count_text_words(const T_str&  text)
{    
    struct  T_words_count
    {
        T_word_counter  word_counter_;
        //--------------------------------------------------------------------------------
        void  operator() (const T_str&  word)
        {
            ++word_counter_[word];
        }
        //--------------------------------------------------------------------------------
        operator  T_word_counter()
        {
            return  word_counter_;
        }
    };
 
    std::istringstream  ssin(text);
    return  std::for_each(std::istream_iterator<T_str>(ssin),
                          std::istream_iterator<T_str>(),
                          T_words_count());      
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_sorted_by_frequency_words_list(const T_word_counter  word_counter)
{    
    struct  T_get_word_of_counter
    {
        T_word_of_counter  word_of_counter_;
        //-------------------------------------------------------------------------------
        void  operator() (const T_word_counter::value_type&  word_counter_val)
        {
            word_of_counter_.insert(std::make_pair(word_counter_val.second,
                                                   word_counter_val.first));
        }
        //-------------------------------------------------------------------------------
        operator  T_word_of_counter()
        {
            return  word_of_counter_;
        }
    };
 
    T_word_of_counter  word_of_counter 
        = std::for_each(word_counter.begin(), word_counter.end(), T_get_word_of_counter());
 
    for(T_word_of_counter::const_reverse_iterator  word_of_counter_it = word_of_counter.rbegin();
        word_of_counter_it != word_of_counter.rend(); ++word_of_counter_it)
    {
        std::cout << word_of_counter_it->first
                  << '\t'
                  << word_of_counter_it->second
                  << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));   
    srand(static_cast<unsigned>(time(0)));
 
    T_str           text          = get_random_text   ();
    T_word_counter  word_counter  = count_text_words  (text);
    print_sorted_by_frequency_words_list(word_counter);   
}
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
10.04.2011, 00:52 #13
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, если вставка критична по времени, то лучше ассоциативный контейнер использовать:
вопрос неоднозначный
в сортированный дек вставка тоже быстро происходит
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
10.04.2011, 01:19 #14
Цитата Сообщение от alex_x_x Посмотреть сообщение
вопрос неоднозначный
в сортированный дек вставка тоже быстро происходит
Сведения неверные. В дек вставка за постоянное время происходит только в начало и в конец.
Время вставки в середину пропорционально расстоянию от места вставки до ближайшего конца.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
10.04.2011, 01:29 #15
да, и правда, можно поменять на list, но тогда потеряется преимущество в поиске
0
10.04.2011, 01:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2011, 01:29
Привет! Вот еще темы с ответами:

контейнер map - C++
Помогите, пожалуйста дописать программу. Определите карту, в которой ключом является фамилия семьи, а значением вектор, который содержит...

Контейнер map - C++
Cоздать ассоциативный список имен (ключей), телефонов. Осуществить поиск по именам. Дополнить его данным адрес. Добавить возможности...

Контейнер map ? - C++
Не совсем удается разобраться Не удается разобраться с ассоциативными контейнерами ! Как выглядит объявление функции в псевдокоде? Что...

Перевернуть контейнер map? - C++
Здравствуйте. Нужно отсортировать map по убыванию. Сделать что-то вроде прохода от map.end() до map.begin Спасибо.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru