是std :: find和std :: map.find都是O(logN)？

Question

是std::find和std::map.findO(logN)？如果是,那么如何在对数时间内std::find实现搜索std::map？

是否std::find专门针对std::map用例实施？

Answer 1

不,std::find是O(N),无论容器如何.它不知道"容器",没有专业化std::map.std::find仅使用迭代器,它没有关于底层容器的信息.根据cppreference.com,实现相当于:

template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

根据C++标准(强调我的):

25.2.5查找[alg.find]

template<class InputIterator, class T>
  InputIterator find(InputIterator first, InputIterator last,
                     const T& value);
...

1. 返回:以下相应条件i所在范围内的第一个迭代器[first,last):*i == value,....last如果没有找到这样的迭代器,则返回.

2. 复杂性:最后 - 相应谓词的第一个应用程序.