std::find
和std::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/