Мне всегда говорили, что векторы бывают быстрыми, и за годы работы в программировании я никогда не видел ничего, что могло бы с этим смириться.Я решил (преждевременно оптимизировать и) написать ассоциативный класс, который представлял собой тонкую оболочку для последовательного контейнера (а именно ::std::vector
и предоставлял тот же интерфейс, что и ::std::map
. Большая часть кода была действительно простой, и я заставил его работать снебольшая сложность.
Однако в моих тестах POD различных размеров (от 4 до 64 байт) и std::strings
, с количеством от восьми до двух тысяч, ::std::map::find
был быстрее, чем мой ::associative::find
, обычно примерно на 15% быстрее, почти для всех тестов. Я сделал Short, Self Contained, Correct (Compilable), Example , который ясно показывает это в ideone Я проверил реализацию MSVC9::std::map::find
и подтвердил, что он очень близко совпадает с моими кодами vecfind
и ::std::lower_bound
, и не может объяснить, почему ::std::map::find
работает быстрее, за исключением обсуждения вопроса о переполнении стека, где люди предположили, что метод двоичного поиска не приносит пользывообще от местоположения вектора до последнего сравнения (что делает его не быстрее), и что требуется указатель arithпримечание, что ::std::map
узлы не требуют, что делает его медленнее.
Сегодня кто-то спросил меня об этом и предоставил этот код на ideone , который, когда я тестировал, показал, что вектор более чем в два раза быстрее.
Хотят ли кодеры StackOverflow разъяснить мне это очевидное несоответствие?Я перебрал оба набора кода, и они кажутся мне эквивалентными, но, может быть, я слепой от того, чтобы так много играть с ними обоими.
(Сноска: это очень близко к одному из моих предыдущих вопросов , но в моем коде было несколько ошибок, которые были устранены. Из-за новой информации / кода я чувствовал, что это достаточно отличается, чтобы оправдать отдельный вопрос. Если нет, я буду работатьпри объединении их.)