質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

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

退会済みユーザー

退会済みユーザー

総合スコア0

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

2回答

1グッド

0クリップ

375閲覧

投稿2022/10/17 16:49

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となり、例文にあるソースコードは要件を満たしていないように見えます。実際のところ、当リファレンスの例は正しいのでしょうか。

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

該当のソースコード

c++

1#include <bits/stdc++.h> 2 3struct X { 4 int id; 5 std::string name; 6}; 7 8int main(){ 9 // 要素は複数のメンバ変数をもつ 10 std::vector<X> v = { 11 {1, "Carol"}, 12 {3, "Alice"}, 13 {4, "Bob"}, 14 {5, "Eve"}, 15 {6, "Dave"} 16 }; 17 18 const std::string key = "Bob"; 19 20 // X::nameメンバ変数をキーにして、 21 // X::name == "Bob"となる要素を二分探索で見つける 22 decltype(v)::iterator it = std::lower_bound( 23 v.begin(), 24 v.end(), 25 X{-1, key}, // nameのみを比較するので、idの値はなんでもよい 26 [](const X& a, const X& b) { return a.name < b.name; } 27 ); 28 29 if (it != v.end() && it->name == key) { 30 std::size_t pos = std::distance(v.begin(), it); 31 std::cout << "id=" << it->id 32 << " name=" << it->name 33 << " pos=" << pos 34 << std::endl; 35 } 36 return 0; 37}
fanaを押しています

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答2

14

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

投稿2022/10/17 17:25

退会済みユーザー

退会済みユーザー

総合スコア0

退会済みユーザー😄を押しています
退会済みユーザー👍を押しています
退会済みユーザー❤️を押しています
退会済みユーザー😍を押しています
退会済みユーザー👏を押しています
退会済みユーザー🎉を押しています
退会済みユーザーを押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

2022/10/18 23:46

こちらの回答が他のユーザーから「説明が不足している回答」という指摘を受けました。

2022/10/18 11:33

こちらの回答が複数のユーザーから「質問に対する回答となっていない投稿」という指摘を受けました。

回答へのコメント

退会済みユーザー

退会済みユーザー

2022/10/17 17:38

同じページの例で、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 以上の物がその順に並んで」いないのではないでしょうか。
退会済みユーザー

退会済みユーザー

2022/10/17 19:18

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

2

ベストアンサー

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

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

投稿2022/10/17 22:17

int32_t

総合スコア17085

退会済みユーザー😍を押しています
fanaを押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

2022/10/18 18:04

こちらの回答が他のユーザーから「情報が古くなった回答」という指摘を受けました。

回答へのコメント

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。