[過去ﾛｸﾞ] C++相談室 part155 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

112: 2021/04/06(火)06:59 ID:rUOwZVXJ(1/5) AAS
質問ですが
　std::vector<SomeBigObject> arr;
　std::vector<int> indices;
というデータがあり、
SomeBigObjectは大小比較可能だがarr自体は未ソートで、
　for (int i = 0; i < N; i++) { indices[i] = i; }
　auto cmpFunc = [](int a, int b)->bool{ return (arr[a] < arr[b]); }
　std::sort(indices.begin(), indices.end(), cmpFunc);
としてindices上で間接的にソートされているとき、
指定されたSomeBigObject x以上の値が現れるarr[i]の最小のiを高速に取得するには
省1

---

113(1): 2021/04/06(火)06:59 ID:rUOwZVXJ(2/5) AAS
arrがソートされていれば
　auto cmpFunc2 = [](const SomeBigObject& a, const SomeBigObject &b)->bool{ return (a < b); }
　std::lower_bound(arr.begin(), arr.end(), cmpFunc2);
で済む話なんだども、SomeBigObjectはコピーの手間がかかるので直接std::sortしたくないという、

---

114: 2021/04/06(火)07:00 ID:rUOwZVXJ(3/5) AAS
AA省

---

116: 2021/04/06(火)15:08 ID:rUOwZVXJ(4/5) AAS
>>115
lower_bound()の第3引数に検索キーxを指定する必要があるから
>>115では解決しないっていうかビルドエラーなﾖｶﾝ、

ここで気づいたが>>113のlower_bound()の例は間違ってたわｽﾏﾝ、orz
↓これに訂正
　auto cmpFunc2 = [](const SomeBigObject& a, const SomeBigObject &b)->bool{ return (a < b); }
　std::lower_bound(arr.begin(), arr.end(), x, cmpFunc2); // 3番目の引数は検索キーx

ところがソートされているindices上の検索キーは、検索したい実際のオブジェクトxから
ただちには求められない（普通にやったら線形探索の手間がかかる、｡n_

---

118(1): 2021/04/06(火)18:31 ID:rUOwZVXJ(5/5) AAS
>>117
ﾑﾘｽ、

つか次のように死ぬほど腐った書き方をしたらとりあえずできるた、
/// 間接ソート版lower_bound
int custom_lower_bound(const std::vector<SomeBigObj>& arr, std::vector<int>& indices, const SomeBigObj& x)
{
　// SomeBigObjの間接ソート用比較関数
　// xのコピーを避けるため[&](a, b)とする。
　auto cmpFunc = [&](const int a, const int b)->bool {
　　// 有り得ないindex値が渡ってきたらxとみなす。
省11

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.038s