std :: map :: upper_bound与std :: upper_bound性能

Question

[在某些CP竞赛中（重要的是，我已经使用了upper_bound的两个版本来在我的std::map中找到上限）：

算法上限（（1）：

auto itr = std::upper_bound(s.begin(),s.end(), somenumber);

if(itr == s.end() || *itr > somenumber2)
{
//dosth
} else
//dosth2
}

std :: map :: upper_bound （（2） ::

auto itr = s.upper_bound(somenumber);

if(itr == s.end() || *itr > somenumber2)
{
//dosth
} else
//dosth2
}

这两个版本都可以，只要我手动输入少量内容即可。但是当涉及到~500.000时，输入[[（1）超过了时间限制（4 seconds），但是（2）在0.5/4.0 second中完成了工作。我在文档algorithm/upper_bound和map/upper_bound处进行了检查，并且都具有O(c log(n))的复杂度（我认为在两种情况下c应该都相似。所以问题是-是什么导致了这种差异？

Answer 1

cppreference page for std::upper_bound表示完成的比较数是对数，但它仍在继续：

但是，对于非LegacyRandomAccessIterators，迭代器增量的数量是线性的。

std::upper_bound没有随机访问迭代器，因此由于增量，std::map将被允许在迭代器距离中具有线性时间复杂度，而std::upper_bound需要在容器大小上具有对数时间复杂度。