std :: lower_bound медленнее для std :: vector, чем std :: map :: find

Я написал класс, который действует как оболочка для последовательного контейнера ( std :: vector / std :: queue / std :: list ), чтобы иметь интерфейс std :: map для повышения производительности при использовании небольшого количества небольших объектов. Кодирование было удивительно простым с учетом уже существующих алгоритмов.Этот код явно сильно урезан из моего полного кода, но показывает проблему.

template ,
          class undertype_ = std::vector >
         >
class associative
{
public:
    typedef traits_ key_compare;
    typedef key_ key_type;
    typedef mapped_ mapped_type;
    typedef std::pair value_type;
    typedef typename undertype_::allocator_type allocator_type;
    typedef typename allocator_type::template rebind::other value_allocator_type;
    typedef typename undertype_::const_iterator const_iterator;

    class value_compare {
        key_compare pred_;
    public:
        inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
        inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
        inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
        inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
        inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
        inline key_compare key_comp( ) const {return pred_;}
    };
    class iterator  {
    public:       
        typedef typename value_allocator_type::difference_type difference_type;
        typedef typename value_allocator_type::value_type value_type;
        typedef typename value_allocator_type::reference reference;
        typedef typename value_allocator_type::pointer pointer;
        typedef std::bidirectional_iterator_tag iterator_category;
        inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
    inline reference operator*() const { return reinterpret_cast(*data);}
        inline pointer operator->() const {return reinterpret_cast(structure_dereference_operator(data));}
        operator const_iterator&() const {return data;}
    protected:
        typename undertype_::iterator data;
    };

    template
    inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
    {if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}

inline iterator find(const key_type& key) {
    iterator i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_);
    return (comp_(key,*i) ? internal_.end() : i);
}

protected:
    undertype_ internal_;
    value_compare comp_;
};

SSCCE на http://ideone.com/Ufn7r , полный код на http://ideone.com/MQr0Z (примечание: время работы IdeOne очень нестабильно, вероятно, из-за нагрузки на сервер и не ясно показывают рассматриваемые результаты)

Я тестировал с std :: string и POD от 4 до 128 байтов, в диапазоне от 8 до 2000 элементов с MSVC10.

Я ожидал более высокой производительности для (1) создания из диапазона для небольших объектов, (2) случайной вставки / стирания для небольшого количества небольших объектов и (3) поиска для всех объектов. Удивительно, но вектор был значительно быстрее для создания из диапазона для всех тестов и быстрее для случайного стирания в зависимости от размера примерно до 2048 байт (512 4-байтовых объектов или 128 16-байтовых объектов и т. Д. ). Однако самым шокирующим было то, что std :: vector с использованием std :: lower_bound был медленнее, чем std :: map :: find для всех ПОД. Разница была минимальной для 4- и 8-байтовых POD, но для 128-байтовых POD std :: vector был на 36% медленнее! Однако для std :: string std :: vector в среднем на 6% быстрее.

Мне кажется, что std :: lower_bound в отсортированном std :: vector должен был превзойти std :: map из-за лучшей локализации кеша / меньшего объема памяти размер, и поскольку карта может быть несовершенно сбалансированной, или в худшем случае она должна соответствовать std :: map , но не может Да здравствует моя мысль, по какой причине std :: map должно быть быстрее. Моя единственная мысль, что предикат как-то замедляет его, но я не могу понять, как это сделать. Итак, вопрос: Как могло случиться так, что std :: lower_bound в отсортированном std :: vector проиграл std :: map (в MSVC10)?

[EDIT] Я подтвердил, что std :: lower_bound на std :: vector > использует меньше сравнений в среднем, чем std :: map :: find (на 0–0,25), но моя реализация все еще на 26% медленнее.

[POST-ANSWER-EDIT] Я сделал SSCCE на http://ideone.com/41iKt , который удаляет весь ненужный мусор и ясно показывает, что find в отсортированном Вектор медленнее, чем у карты , на ~ 15%.