C++標準ライブラリにはlower_bound、upper_boundというアルゴリズム関数が用意されています。
そしてsetやmultisetなどの一部のコンテナクラスにも同じ名前のメンバー関数が用意されています。
これらはいずれも「ソートされた範囲から二分探索を行って指定された条件を満たすイテレータを取得する」という役割を持っており、ほぼ同じように使用できます。
「同じように使用できる」といっても、コンテナクラスに同名のメンバー関数が用意されている場合は、コンテナの要素に対してアルゴリズムを適用する際に、素直にメンバー関数を使用する方がおすすめです。
それはなぜなのかを説明する前に、以下のサンプルコードを、Visual Studio 2022のC++コンパイラでコンパイルして実行した結果を示します。
１つはstd::setのメンバー関数であるlower_boundを呼び出し、もう１つはstd::lower_boundを呼び出したものです。
#include <algorithm>
#include <chrono>
#include <iostream>
#include <set>
template <typename T>
void Test(const char* msg, T func)
{
auto start = std::chrono::system_clock::now();
func();
auto end = std::chrono::system_clock::now();
std::cout << msg << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << std::endl;
}
int main()
{
std::set<int> s;
const int dataSize = 1024 * 1024 * 30;
for (int i = 0; i < dataSize; ++i) {
s.insert(i);
}
const int num = 123;
Test("std::set::lower_bound 経過時間（ミリ秒）：", [&]() {
std::set<int>::const_iterator it = s.lower_bound(num);
});
Test("std::lower_bound 経過時間（ミリ秒）：", [&]() {
std::set<int>::const_iterator it = std::lower_bound(s.begin(), s.end(), num);
});
}
結果はこのようになりました。
std::set::lower_bound 経過時間（ミリ秒）：0
std::lower_bound 経過時間（ミリ秒）：573
実行環境によって多少の差は生まれるかと思いますが、注目すべき点は、同じ操作をしているように見えても、std::set::lower_boundは一瞬で終わり、std::lower_boundは少し時間がかかることです。
なぜこのような違いが生まれるのかというと、std::set::lower_boundの方はstd::setのメンバー関数なので、自分（std::set）のデータ構造が分かっています。
std::setは一般的に二分木で作られているので、二分木をたどって効率よく二分探索が行われます。
std::lower_boundも二分探索を行うため、一見するとパフォーマンスも同じようになると思われがちですが、std::lower_boundは引数で渡されたイテレータだけではデータ構造を把握できません。
std::lower_boundが二分探索を行うには、渡された２つのイテレータの範囲を分割して絞り込んでいく必要があります。
つまり、範囲の開始イテレータがfirst、範囲の終了イテレータがlastという変数名だとしたら、分割するイテレータの位置を求めるには
auto mid = (last - first) / 2;
というようなコードになるかと思います。
（上記コードは疑似的なものです。実際に動作するコードではありません。）
しかし、これができるのはランダムアクセスできるイテレータ、つまりはvectorやdequeの場合に限定されます。
std::setはランダムアクセスができないため、(last - first) / 2の位置に到達するまでひたすらoperator++を呼び出すことになります。
これは効率が悪い処理です。
これが同じ二分探索でもパフォーマンスに違いが出る理由です。
このように同じ名前、同じアルゴリズムが使用されていてもパフォーマンスに違いが発生する場合があります。
アルゴリズムと同名の関数がコンテナクラスのメンバー関数として定義されている場合、何らかの要因でアルゴリズムの関数よりもメンバー関数の方が適切と判断されたため用意されたものです。
したがって、メンバー関数を使う方がおすすめです。
