Сортировка multimap

[Jilian]

 
struct zap{
   int myfirst;
   string mysecond;
};

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

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

[Sanyok]

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

[незваный гость]

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

[maxal]

Безотносительно сортировки, я бы посоветовал zap определить как

typedef std::pair<int,std::string> zap;

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

Sanyok писал(а):

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

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

[Sanyok]

maxal писал(а):

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

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

[VLarin]

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

[maxal]

VLarin писал(а):

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

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

[VLarin]

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

[незваный гость]

maxal писал(а):

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

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

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

[maxal]

Кстати, можно обойтись и одним контейнером, если занести 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 ) { ... }

и т.д. и т.п.

[незваный гость]

2 maxal: никогда не пробовал. Здорово!