我编写了一个类来充当顺序容器（std::vector/ std::queue/
std::list）的包装，以具有a的接口std::map，以在使用少量小对象时提高性能。考虑到已经存在的算法，编码都非常简单。此代码显然是
高度 从我的全码修剪，但显示的问题。

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的生成时间非常不稳定，可能是由于服务器负载所致，并且没有清楚地显示有问题的结果）

我使用进行了测试std::string，并使用MSVC10对POD从4到128字节（范围从8到2000个元素）进行了测试。

我期望在（1）从一定范围内为小对象创建，（2）对少量小对象进行随机插入/擦除以及（3）对所有对象进行查找方面具有更高的性能。出乎意料的是，根据在所有测试范围内创建的向量，向量
显着
更快，而对于最大约2048个字节（512个4字节对象或128个16字节对象等）的大小的随机擦除，向量的创建速度则更快。但是，最令人震惊的是，std::vector使用std::lower_bound速度比std::map::find所有POD
都要慢。对于4字节和8字节的POD，差异很小，但是对于128字节的POD，差异std::vector要慢36％！但是，对于std::string，std::vector平均速度要快6％。

我感觉由于更好的缓存局部性/较小的内存大小，std::lower_bound排序后的std::vector表现应该会跑赢大盘std::map，而且由于map可能无法完美平衡，或者在
最坏的情况下 它应该 匹配
std::map，但我一生都无法想到std::map应该更快。我唯一的想法是谓词会以某种方式降低它的速度，但是我不知道怎么做。所以，问题是：
这怎么可能是std::lower_bound在一个排序std::vector可以通过跑赢std::map（在MSVC10）？

[编辑]我已经证实，std::lower_bound在std::vector<std::pair<4BYTEPOD,4BYTEPOD>>使用较少的
比较 平均比std::map<4BYTEPOD,4BYTEPOD>::find（由0-0.25），但我实现仍然高达26％速度较慢。

[POST-ANSWER-
EDIT]我在http://ideone.com/41iKt上创建了SSCCE，该SSCCE
删除了所有不需要的绒毛，并清楚地表明，find排序后的绒毛vector比慢map，约15％。