C ++ разница между std :: lower_bound и std :: set :: lower_bound? ⇐ C++

[Anonymous]

Недавно, работая над проблемой программирования в C ++, я наткнулся на что -то интересное. Мой алгоритм использовал действительно большой набор и использовал бы std :: lower_bound на нем много раз. Однако, после того, как я подал решение, вопреки математике, которую я сделал на бумаге, чтобы доказать, что мой код был достаточно быстрым, он оказался слишком медленным. Код выглядел примерно так: < /p>

using namespace std;

set s;
int x;

//code code code

set::iterator it = lower_bound(s.begin(),s.end(),x);
< /code>

Однако, получив подсказку от приятеля, чтобы использовать Set :: lower_bound, рассматриваемый алгоритм, о котором идет речь быстрее, чем раньше, и он последовал за моей математикой. Бинарный поиск после изменения: < /p>

set::iterator it = s.lower_bound(x);
< /code>

Мой вопрос: в чем разница между этими двумя? Почему один работает намного, намного быстрее, чем другой? Разве Lower_bound не должна быть бинарной функцией поиска, которая имеет сложность O (log2 (n))? В моем коде это оказалось намного медленнее, чем это.

Подробнее здесь: https://stackoverflow.com/questions/318 ... ower-bound