Походу, у вас никакой не реал-тайм, ибо в реал-тайме вас бы волновали вопросы работы с динамической памятью. Обычно в реал-тайм задачах динамическая память не используется, т.к. поведение аллокаций/деаллокаций плохопредсказуемо. А т.к. std::map со аллокатором по-умолчанию работает именно через динамическую память, то применение std::map в действительно реал-тайме под вопросом именно по этому параметру.
Что до вашего вопроса, то за время, пока вы его обсуждаете на RSDN, уже можно было написать несколько простейших бенчмарков и сравнить поведение std::map, vector (сортированный и несортированный), priority_queue (он же heap), circular_buffer и иже с ними. Ведь никто из форумчан не знает ни объема ваших данных, ни платформы, ни компилятора, ни библиотек, которые у вас в наличии.
