Здравствуйте, Кодт, Вы писали:

К>    map<int,string> dataset; // сортировать будем прямо в момент вставки

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