c++ - O(N) 查找但 O(log(N)) 比较在排序列表上使用 upper_bound 时

Question

list<Person> lp;
...
lp.sort(PersonNameLess());

Person newPerson;
...
lp.insert(upper_bound(lp.begin(), lp.end(), 
          newPerson, PersonNameLess()), newPerson);

在有效的 c++ 第 3 版，第 198 页，第 45 项中，它说如下：

查找需要线性时间，但它只执行对数比较

问题：为什么它只执行对数比较？

Answer 1

为什么它只执行对数比较？

因为列表已排序并且upper_bound执行二分查找。