c++ - ソートされたリストで upper_bound を使用する場合、O(N) 回のルックアップと O(log(N)) 回の比較

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は二分探索を実行するためです。