2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сортировка multimap
Сообщение18.01.2006, 16:54 
Аватара пользователя


09/10/05
22
Код:

struct zap{
   int myfirst;
   string mysecond;
};

multimap<string, zap> mymap;
multimap<string, zap>::iterator myiterator; 

Подскажите, пожалуйста, как отсортировать такой ассоциативный массив по myfirst.

 Профиль  
                  
 
 
Сообщение18.01.2006, 18:39 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
Есть средства, что бы получить элемент массива и присвоить значение элементу массива (насколько я понял, итератор - т.н. "безопасный массив" или safe array)? Лучше, если бы Вы привели тут заодно объявление шаблонного класса multimap.

 Профиль  
                  
 
 
Сообщение18.01.2006, 23:30 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Простите, а что Вы имеете в виду, говоря "отсортировать"? Контейнеры типа multimap обычно не гарантируют никакого порядка перебора элементов. Если Вам нужен контейнер, имеющий и порядок, и свойства multimap, его обычно строят из двух. Если же Вам нужен однократный перебор, то данные выкачиваются из multimap в vector, и vector сортируется.

 Профиль  
                  
 
 
Сообщение19.01.2006, 01:30 
Модератор
Аватара пользователя


11/01/06
5660
Безотносительно сортировки, я бы посоветовал zap определить как
Код:
typedef std::pair<int,std::string> zap;

Такое определение хорошо тем, что автоматически позволяет сравнивать элементы типа zap. Кстати, порядок на pair определен лексикографический, то есть прежде всего по первому элементу, как вы и хотели.

Sanyok писал(а):
Лучше, если бы Вы привели тут заодно объявление шаблонного класса multimap.

Дык это же стандартный тип.

 Профиль  
                  
 
 
Сообщение19.01.2006, 08:28 
Заслуженный участник
Аватара пользователя


12/10/05
478
Казань
maxal писал(а):
Дык это же стандартный тип.


:oops: Черт, не знал... Сейчас поглядел его интерфейс - и в самом деле, непонятно как его сортировать... Произвольного доступа к элементам вроде нету... :roll:

 Профиль  
                  
 
 
Сообщение19.01.2006, 16:38 


13/09/05
153
Москва
Полностью согласен с Незванный Гость:
Map это map, а если нужно вывести содержимое в упорядоченном порядке, то тут нужно по map сделать vector и его уж std::sort'ом отсортировать по нужной переменной.

 Профиль  
                  
 
 
Сообщение19.01.2006, 16:46 
Модератор
Аватара пользователя


11/01/06
5660
VLarin писал(а):
Map это map, а если нужно вывести содержимое в упорядоченном порядке, то тут нужно по map сделать vector и его уж std::sort'ом отсортировать по нужной переменной.

С map проблем бы не было - он всегда отсортирован по ключу. Вопрос же был именно про multimap, который хотя и отсортирован по ключу, тем не менее не гарантирует никакого порядка на элементах с равными ключами (equal_range).

 Профиль  
                  
 
 
Сообщение19.01.2006, 18:46 


13/09/05
153
Москва
map или multimap - в любом случае, самое простое, что можно сделать - это использовать std::vector с пользовательской предикатой для сортировки:))

 Профиль  
                  
 
 
Сообщение19.01.2006, 18:55 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
maxal писал(а):
С map проблем бы не было - он всегда отсортирован по ключу. Вопрос же был именно про multimap, который хотя и отсортирован по ключу, тем не менее не гарантирует никакого порядка на элементах с равными ключами (equal_range).

Я был немного некорректен :oops:, в С++ multimap отсортирован по ключу. Замечу только, что этот ключ не обязан совпадать ни с myfirst, ни с mysecond. Ключ суть сущность внешняя по отношению к хранимому объекту.

Если Вам надо отстортировать по mysecond, потом по myfirst, проще всего генерировать составной ключ (хотя не всегда приемлемо, поелику тогда myfirst при выборке надобен). Это, правда, предполагает разделитель, меньший любого mysecond. Коли Ваш ключ с mysecond не связан, придется Вам пользоваться vector'ом. В связи с чем вопрос -- что дороже -- сортировать vector иттераторов, или проще сами структуры? Альтернатива -- скомбинировать новый "sortedmultimap" из двух контейнеров. Тут Ваш главный вопрос -- как определить новый find(). Что Вам нужно -- найти первый попавшийся, или с наименьшим myfirst?

 Профиль  
                  
 
 
Сообщение19.01.2006, 22:16 
Модератор
Аватара пользователя


11/01/06
5660
Кстати, можно обойтись и одним контейнером, если занести myfirst так же и в ключ.
Код:
map<pair<string,int>, zap> mymap2;

Работать с таким контейнером ничуть не сложнее чем с исходным mymap, только есть некоторые тонкости с доступом к элементам по ключу. Например,
Код:
it = mymap.find(key);
if( it!=mymap.end() ) { ... }

заменяется на
Код:
it = mymap2.lower_bound(make_pair(key,INT_MIN));
if( it!=mymap2.end() && it->first.first==key ) { ... }

и т.д. и т.п.

 Профиль  
                  
 
 
Сообщение19.01.2006, 22:30 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
2 maxal: никогда не пробовал. Здорово!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group