c++ - 如何优化 vector 的二分查找？

Question

我正在尝试在已排序的键值对 vector 上实现一个查找方法。现在它的执行速度比 map.find(key) 慢。理论上它应该更快，因为 vector 由于其连续内存可以更好地利用 CPU 缓存。我只是想知道这个实现是否有明显的错误，是否有任何方法可以优化它？我不认为在这里使用标准算法是一个选项，因为最接近的可能选项是 lower_bound 并且这将导致我必须执行的检查的额外开销以验证它是否找到任何东西。除此之外，lower_bound 需要我构造一对(加上我放在它周围的包装器)以将其作为我正在搜索的值，从而产生更多不必要的开销。

FlatMap<KEY, VALUE, COMPARATOR>::findImp(const key_type &key)
{
    typename VectorType::iterator lower = d_elements.begin();
    typename VectorType::iterator upper = d_elements.end();
    typename VectorType::iterator middle;
    while(lower < upper) {
        middle = lower + (upper-lower)/2;
        if(d_comparator(middle->data().first, key)){
            lower = middle;
            ++lower;
        } else if(d_comparator(key, middle->data().first)){
            upper = middle;
        } else {
            return middle;
        }
    }
    return d_elements.end();
}

请注意，d_elements 是对的 vector (对在包装器中):

vector<FlatMap_Element<KEY, VALUE> >  d_elements;

包装器本身只是将对作为数据成员保存，并在不影响搜索的情况下进行一些神奇的赋值:

template <class KEY, class VALUE>
class FlatMap_Element {
    bsl::pair<const KEY, VALUE> d_data;
    ...
    pair<const KEY, VALUE>& data();
    pair<const KEY, VALUE> const& data() const;
};

我知道使用包装器的业务不是减速的根源，因为我已经在没有包装器的 vector 或对上测试了该算法并且具有相同的性能。

欢迎提出任何调整建议。

Answer 1

您的版本通过循环使用两次 m_comparator 结果，而 std::lower_bound 仅使用一次比较。

所以你可以使用类似的东西:(C++03)

template <typename Key, typename Value, typename KeyComparator>
struct helper_comp
{
    bool operator (const std::pair<const Key, Value>& lhs, const Key& rhs) const {
        return comp(lhs.first, rhs);
    }
    KeyComparator comp;
};

template <typename Key, typename Value, typename KeyComparator>
typename std::vector<std::pair<const Key, Value>>::const_iterator
my_find(const std::vector<std::pair<const Key, Value>>& v, const Key& key)
{
    auto it = std::lower_bound(v.begin(), v.end(), key, helper_comp<Key, Value, KeyComparator>());
    if (it != v.end() && it->first == key) {
        return it;
    }
    return v.end();
}

或使用 lambda 而不是外部 struct helper_comp(C++11) ( https://ideone.com/snZTRu )