c++ - std::map::upper_bound 与 std::upper_bound 性能

Question

在一些 CP 竞赛中(这很重要)，我使用了 2 个版本的 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秒)但(2)在 0.5/4.0 秒内完成工作。
我查看了文档algorithm/upper_bound和 map/upper_bound并且两者都有 O(c log(n)) 复杂度(我认为在这两种情况下 c 应该是相似的。
所以问题是 - 是什么导致了这种情况区别？

Answer 1

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

However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

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