std::lower_bound 对于 std::vector 比 std::map::find 慢

I wrote a class to act as a wrapper around a sequential container (std::vector/std::queue/std::list) to have the interface of a std::map, for performance when using small numbers of small objects. The coding was all remarkably simple given the algorithms that already existed. This code is obviously highly trimmed from my full code, but shows the problem.

template <class key_, 
          class mapped_, 
          class traits_ = std::less<key_>,
          class undertype_ = std::vector<std::pair<key_,mapped_> >
         >
class associative
{
public:
    typedef traits_ key_compare;
    typedef key_ key_type;
    typedef mapped_ mapped_type;
    typedef std::pair<const key_type, mapped_type> value_type;
    typedef typename undertype_::allocator_type allocator_type;
    typedef typename allocator_type::template rebind<value_type>::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<reference>(*data);}
        inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
        operator const_iterator&() const {return data;}
    protected:
        typename undertype_::iterator data;
    };

    template<class input_iterator>
    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 的结果时间非常不稳定，可能是由于服务器负载，并且不清楚显示有问题的结果)

auto rc = std::lower_bound(this->internal_.begin(), this->internal_.end(), key, this->comp_);
return rc != this->internal_.end() && !this->comp_(key, rc->first)? rc: this->internal_.end();

template <typename>               struct is_pair                  { enum { value = false }; };
template <typename F, typename S> struct is_pair<std::pair<F, S>> { enum { value = true }; };

class value_compare {
    key_compare pred_;
public:
    inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
    template <typename L, typename R>
    inline typename std::enable_if<is_pair<L>::value && is_pair<R>::value, bool>::type
    operator()(L const& left, R const& right) const {
        return pred_(left.first,right.first);
    }
    template <typename L, typename R>
    inline typename std::enable_if<is_pair<L>::value && !is_pair<R>::value, bool>::type
    operator()(L const& left, R const& right) const {
        return pred_(left.first,right);
    }
    template <typename L, typename R>
    inline typename std::enable_if<!is_pair<L>::value && is_pair<R>::value, bool>::type
    operator()(L const& left, R const& right) const {
        return pred_(left,right.first);
    }
    template <typename L, typename R>
    inline typename std::enable_if<!is_pair<L>::value && !is_pair<R>::value, bool>::type
    operator()(L const& left, R const& right) const {
        return pred_(left,right);
    }
    inline key_compare key_comp( ) const {return pred_;}
};

template <typename Key>
Key const& get_key(Key const& value)                  { return value; }
template <typename Key,  typename Value>
Key const& get_key(std::pair<Key, Value> const& pair) { return pair.first; }

template <typename L, typename R>
bool operator()(L const& l, R const& r)
{
    return this->pred_(get_key<key_type>(l), get_key<key_type>(r));
}