std::findstd::map.find都是O(logN)吗?
如果是,std::find如何实现对数时间内通过std::map进行搜索?
std::find的实现是否专门针对std::map用例?

最佳答案

不,不管容器如何,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);
...
  • 返回:i范围内的第一个迭代器[first,last),其符合以下条件:*i == value,。 。 。 。如果找不到这样的迭代器,则返回last
  • 复杂度:最多-相应谓词的第一个应用程序。
  • 关于c++ - std::find和std::map.find是否都为O(logN)?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30496499/

    10-11 23:14
    查看更多