問題タブ [lower-bound]

私はhttp://www.cplusplus.com/reference/algorithm/upper_bound/std::upper_boundから勉強していましたが、これが非ランダムアクセスイテレータ で線形時間で実行される可能性があるという事実に出くわしました。

これをソート済みベクターに使用する必要があります。現在、非ランダム アクセスイテレータとは何か、およびこれが並べ替えられたベクトルで対数時間で実行されるかどうかはわかりません。

誰でも私のためにこれをクリアできますか？

std::lower_bound() および std::upper_bound() 構文 (まあ、実際には型変換) で矛盾しているように見えるものを見たので、誰かが解明できるかどうか疑問に思っていましたか? コメントによると、2 行目は 1 行目と明らかに類似しているにもかかわらず、コンパイルされません。3行目に示されているフォームを使用する必要があります（少なくともgcc 4.7.3 / ubuntu 64ビットでは-これですべてです）

実装で上限を変更したときに、この奇妙な動作に遭遇しましたが、インターフェイスで変更するのを忘れていました。最後のステートメントはコンパイルすべきではないと思いますが、コンパイルして予期しない結果を返します。

編集

@som-snytt が-Xprint:typerオプションで言及したように、コンパイラが実際に何を推論するかを確認できます。

これは、「インターフェイス ベース」を取得する理由を説明しています。しかし、この場合、型推論がどのように、なぜ機能するのか、まだよくわかりません。

2 つの完全な行列の乗算の下限が Ω(n^2) であることはわかっています。行列乗算

問題変換法を使用して、2 つの下三角行列の乗算の下限を証明しようとしています。

私の最初の考えは、(1) 下三角行列を変換すること、(2) そのような変換の時間の複雑さを推定することです。

ここで、証明するO(lower_triangular_matrix_transformation(n))必要があるだけであり、三角行列を完全な行列にする必要があるため、簡単にするために、この三角行列にそれ自体のバリエーション、たとえば転置を掛けるだけです。

その理由は、下三角行列の 2 乗は依然として下三角行列であり、その転置された変化を乗じた下三角行列は「完全な行列」だからです。

したがって、三角行列に転置されたバリエーションを乗じた複雑さを分析するだけで済みます。

私の考えが「合理的」であるかどうかを誰かが示すことができますか?

値が構造体へのポインターのベクトル内にあるかどうかを調べるために、lower_bound を使用しようとしています。私は使っている

比較関数は次のようになります

上記のIDを持つ要素が見つかったかどうかを確認したい。どうすれば確認できますか？使ってみた

しかし、これはセグメンテーション違反をスローしています。要素が既に存在するかどうかを確認する方法はありますか?

ラムダと組み合わせた lower_bound 関数を使用して、構造体のベクトルを int 値で作成した直後に並べ替えるにはどうすればよいですか? (1回線機能)

構造：