STL, упорядочить карту по value.

Создать вторую карту, в котором ключами будут значения первой карты.

Значения первой -- довольно толстые структуры, и по одному из полей этих структур нужно пробежаться по возрастанию, а потом и по убыванию. Варианты есть, но они у*бищные какие-то получаются. Неизящно... То ли я плюсы так хреново знаю (99% правда), то ли это действительно без костылей невозможно сделать.

завести индексную таблицу

boost::multi_index ?

Не засоряйте русский язык. Из-за подобных грамотеев теперь говорят "видеокарта" вместо "видеоплата" :(

чиво чиво?