Пара векторов вместо вектора & lt; pair & gt ;?

Я ищу библиотеку, которая будет реализовывать что-то похожее на std :: map и multimap, но без дерева, но вместо векторов, как pair<vector<key>,vector<value>>, Библиотека должна будет синхронизировать и отсортировать векторы.

Я хотел бы сравнить производительность карт, vector<pair<key,value>> и такая библиотека. Я не собираюсь пытаться сделать общий тест, я только хочу, что быстрее для моего приложения.

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

На самом деле, если бы я должен был написать код, я бы сделал это с двумя классами. Несортированная версия с разрешенными только быстрыми вставками push_back, затем преобразование в отсортированную версию, которая будет принимать несортированную версию, сортировать ее, возможно проверять на двойственность, а затем разрешать быстрый поиск и более медленные сортированные вставки. На самом деле это пункт 23 «Эффективного STL» Скотта Мейерса: «Рассмотрите возможность замены ассоциативных контейнеров отсортированными векторами».

Редактировать: Как указано в документации Boost о flat_ (мульти) отображение / набор, Мэтт Остерн, а не Скотт Мейерс первым предложил заменить карты и наборы векторами: http://lafstern.org/matt/col1.pdf