Auto-sorted vector + Александреску = ?

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

История, вкратце, простая - в системе имелся map, отображающий географический регион на имя карты.
В процессе работы некоторого алгоритма, осуществлявшего сбор данных с карты обратил внимание, что в процессе профилирования как-то слишком часто встречается работа с этим map'ом.
Тут же как-то сам собой вспомнился AssocVector из состава Loki (А.Александреску "Современное проектирование на Си++") - идея в том, что вместо использования map, применяется обычный vector, но отсортированный, при этом значения ищутся с помощью lower_bound.
Главное условие для такой оптимизации - изменение состояния контейнера должно происходить очень редко, а поиск по ключу - часто.
В нашем же случае (с известным натягом, не представляющим в рамках обсуждения особого интереса) содержимое вектора не меняется вообще НИКОГДА.
Таки да - эффект налицо (не в 10**0 раз, но все же)...
Насколько я понимаю ситуацию, в основном он обусловлен тем, что изменился memory layout для контейнера, и теперь процессор в состоянии осуществлять эффективную предвыборку данных в кэш, которые хранятся по факту теперь непрерывным блоком (для этого я даже имя карты занес в фиксированный массив, а не поместил в string).
Из того, что требуется сделать - объявить pair и реализовать операцию сравнения (для сортировки и поиска).