Что выбрать: std::map, std::vector или boost::unordered_map?

На практике столкнулся со следующей задачей. Имеется последовательность токенов (числовых или строковых). Необходимо подсчитать количество вхождения каждого токена в последовательность. Какие именно токены входят в последовательность - заранее не известно, однако известно, что общее количество разных токенов не превосходит заданной величины и что длина последовательности гораздо больше количества разных токенов.

Как решать? Возможный алгоритм: создать ассоциативный контейнер, в котором будем хранить пару "токен - количество вхождений", перебрать всю последовательность и подсчитать количество вхождений каждого токена. Нам придется многократно пополнять ассоциативный контейнер в процессе перебора последовательности и на каждом шаге проводить в нем поиск очередного токена.

"Стандартных" контейнера, которые подойдут в данном случае, как минимум три: std::map, сортированный std::vector и boost::unordered_map, который уже вошел в TR1. Вопрос, какой из них лучше подойдет для данной задачи?

Чтобы определить, какой вариант лучше, написал небольшое тестовое приложение. В нем содержатся три класса, реализующие варианты подсчета токенов с помощью разных ассоциативных контейнеров, два класса для генерации случайной последовательности токенов (int и string) и тестовая функций, выполняющая тестовый перебор последовательности несколько раз и определяющая среднее время, затрачиваемое на его выполнение. У программы два параметра: максимальное количество токенов и длина последовательности. Программа тестировалась на VS2005 с родной реализацией STL.

Результаты тестирования для последовательности из 1e5 целочисленных токенов

Кол-во токенов:	10	1e2	1e3	1e4	1e5
std::map, int	37	35	31	464	716
std::vector, int	40	37	31	51	1446
boost::unordered_map, int	35	31	23	40	427

Результаты тестирования для последовательности из 1e5 строковых токенов

Кол-во токенов:	10	1e2	1e3	1e4	1e5
std::map, string	55	62	70	493	391
std::vector, string	71	74	87	1071	-
boost::unordered_map, string	47	46	38	93	437

Вектор работает плохо, но это и следовало ожидать. boost::unorderd_map демонстрирует лучшую производительность, чем std::map, однако если по началу их результаты примерно одинаковы, то потом следует резкий перекос (производительность boost::unorderd_map в 5-10 раз лучше), а затем маятник качается в обратную сторону, так что производительность std::map становится даже лучше. Посмотрим, как ведет себя производительность при других соотношениях длины последовательноси и количества токенов.

Кол-во токенов/длина последовательности:	1e5/1e6	1e5/1e7	1e6/1e7
std::map, int	625	5031	13875
boost::unorderd_map, int	984	2578	6062
std::map, string	1796	15343	28875
boost::unorderd_map, string	1328	6375	1125

Выводы

Сортированный вектор в данной задаче показывает худшие результаты - при большом количестве токенов ему становится совсем плохо, что вообщем-то не удивительно - ведь производится много операций вставок в произвольное место вектора, а такие операции для вектора очень дорогие.

boost::unordered_map работает быстрее std::map при условии, что длина последовательности гораздо больше количества токенов, т.е. каждый токен в среднем входит в последовательность множество раз.

Если же длина последовательности и количество токенов примерно совпадают (т.е. все токены входят в последовательность один-несколько раз ), то std::map может оказаться быстрее, но в редких случаях..

Итог - для моей задачи boost::unordered_map предпочтителен. И как хорошо, что это теперь стандартный контейнер :)

Исходные коды тестового проекта можно взять здесь.