std::lower_boundのリファレンスの例の解説について

Question

c++日本語リファレンスstd::lower_bound
https://cpprefjp.github.io/reference/algorithm/lower_bound.html
の内容についての質問です。

要件に、

[first,last) の要素 e は e < value または comp(e, value) によって区分化されていること。 つまり、e < value または comp(e, value) が true となる全ての要素 e は、false となる全ての要素よりも左側（first に近い方）になければならない。

とありますが、"Calrol" < "Bob" はFalseで "Alice" < "Bob"はTrueとなり、例文にあるソースコードは要件を満たしていないように見えます。実際のところ、当リファレンスの例は正しいのでしょうか。

よろしくおねがいします。

該当のソースコード

#include <bits/stdc++.h>

struct X {
    int id;
    std::string name;
};

int main(){
    // 要素は複数のメンバ変数をもつ
    std::vector<X> v = {
      {1, "Carol"},
      {3, "Alice"},
      {4, "Bob"},
      {5, "Eve"},
      {6, "Dave"}
    };

    const std::string key = "Bob";

    // X::nameメンバ変数をキーにして、
    // X::name == "Bob"となる要素を二分探索で見つける
    decltype(v)::iterator it = std::lower_bound(
      v.begin(),
      v.end(),
      X{-1, key}, // nameのみを比較するので、idの値はなんでもよい
      [](const X& a, const X& b) { return a.name < b.name; }
    );

    if (it != v.end() && it->name == key) {
      std::size_t pos = std::distance(v.begin(), it);
      std::cout << "id=" << it->id
                << " name=" << it->name
                << " pos=" << pos
                << std::endl;
    }
    return 0;
}

Answer 1

lower_bound で 探索したい要素 x 以上の要素の位置を検索する場合、x より小さい物と x 以上の物がその順に並んでいれば、必ずしもソートされている必要はない。

Comments

[退会済みユーザー]

同じページの例で、vector<int> v = {3, 1, 4, 6, 5} で4を検索するときは、1 < 3 < 4 < 5 < 6 なので、理解できます。ただ、vector<string> v = {"Carol", "Alice", "Bob", "Eve", "Dave"} としたときに"Bob"を検索するならば、"Alice" < "Bob" < "Carol" < "Dave" < "Eve" なので「 x より小さい物と x 以上の物がその順に並んで」いないのではないでしょうか。

[退会済みユーザー]

"Bob"は中央にある。
よって、この関数は最初に"Bob"を発見し、探索を終了する。

Answer 2

サンプルコードの間違いのように見えます。
(もし前提を満たしていない入力の例だとすれば、そう明記すべき)

サイトは github で管理されているようなので、修正する pull request を送ると歓迎されるのではないでしょうか。

Comments

[int32_t]

https://github.com/cpprefjp/site/pull/1002
PR で修正されたようですね。