C++相談室 part155 - 暇つぶし2ch

C++相談室 part155 at TECH

[前50を表示]
100:デフォルトの名無しさん
21/04/04 18:57:03.43 b5JcZ1t5.net
ここは飛ばしてゲーム作ります(´・ω・`)、、、別に面白さと関係ないしね、、、。

101:デフォルトの名無しさん
21/04/04 19:04:13.20 b5JcZ1t5.net
processingで似たような事できますか？ちょこちょこ練習しようかな
ゲームエンジン使うほどでもないので
URLﾘﾝｸ(processing.org)
これダウンロードできます？寄付しろと言われるんですけども

102:デフォルトの名無しさん
21/04/04 19:10:44.91 b5JcZ1t5.net
できた　すみあｍせん

103:デフォルトの名無しさん
21/04/05 08:59:16.68 8ugS0e8D.net
c++言語をググるとビャーネも必ず出てきて
彼が設計者だとのことですが、コンパイラを作ってるのは彼ではないですよね
具体的に彼は何をしたの？

104:デフォルトの名無しさん
21/04/05 09:24:06.09 YIdyLrea.net
言語仕様の策定だろ
まあ最初のコンパイラー（コンバーターかも）ぐらいは作ってるとは思うけど

105:デフォルトの名無しさん
21/04/05 09:27:14.80 cScuzdm0.net
当初はCのプリプロセッサだから今で言うとTypescriptみたいなものだな

106:デフォルトの名無しさん
21/04/05 11:51:16.82 zIvWtxBS.net
C++標準化委員会は誰が組織したんや？

107:デフォルトの名無しさん
21/04/05 11:53:41.43 zIvWtxBS.net
それとも国際標準化機構（ISO）か何かの配下なの？

108:デフォルトの名無しさん
21/04/05 12:36:06.42 ESZTLEZZ.net
>>105
K&R Cにクラスの概念を取り入れて見よう
ということを思いつきcfrontを実装した
TC++PL及びARMを著しC++を広く世界に知らしめた

109:デフォルトの名無しさん
21/04/05 17:28:39.12 2Tvboykg.net
そして世界は闇と混沌に包まれた……

110:デフォルトの名無しさん
21/04/05 19:55:46.69 rNcivJgw.net
c++はクソだが、プログラマが求めたクソなのだ。

111:デフォルトの名無しさん
21/04/05 22:13:27.34 zIvWtxBS.net
URLﾘﾝｸ(livedoor.blogimg.jp)

112:デフォルトの名無しさん
21/04/05 22:24:25.87 vDuR7coO.net
ビヨーン先生の功績は
ハゲても立派なプログラマになれるという勇気をくれたことだろう

113:デフォルトの名無しさん
21/04/06 06:59:06.97 rUOwZVXJ.net
質問ですが
　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を高速に取得するには
どうづればSTLでやるには良いですのん？

114:デフォルトの名無しさん
21/04/06 06:59:22.44 rUOwZVXJ.net
arrがソートされていれば
　auto cmpFunc2 = [](const SomeBigObject& a, const SomeBigObject &b)->bool{ return (a < b); }
　std::lower_bound(arr.begin(), arr.end(), cmpFunc2);
で済む話なんだども、SomeBigObjectはコピーの手間がかかるので直接std::sortしたくないという、

115:デフォルトの名無しさん
21/04/06 07:00:25.45 rUOwZVXJ.net
また手動で組めということなら明らかに組める
int custom_lower_bound(int bgn, int end, const int N, const SomeBigObject& x) {
　while (bgn < end) {
　　int mid = bgn + (end - bgn) / 2;
　　if (arr[mid] < x) {
　　　bgn = mid;
　　} else if (x < arr[mid]) {
　　　end = mid;
　　} else {
　　　while (mid > 0 && arr[mid - 1] == x) { mid--; }
　　　return mid;
　　}
　}
　while (bgn < N && arr[bgn] < x) {
　　bgn++;
　}
　return bgn;
}
みたいなことをしたら多分逝けるが、しかしこんなもん使う都度書きたくないし、
ライブラリとして展開して責任負いたくもないんじゃー
STLはこういうケースのためにあり、論理的に実現できる以上やり方が考えられていないとおかしいはず……

116:デフォルトの名無しさん
21/04/06 07:42:07.19 w+lldWjr.net
　auto cmpFunc3 = [](int a, int b)->bool{ return (arr[a] < arr[b]); }
　i = std::lower_bound(indices.begin(), indices.end(), cmpFunc3);
arr[i];
じゃいかんのかしら

117:デフォルトの名無しさん
21/04/06 15:08:28.23 rUOwZVXJ.net
>>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:デフォルトの名無しさん
21/04/06 17:08:29.35 mAZMW+WU.net
　auto cmpFunc3 = [&](int idx, const SomeBigObject& xx)->bool{ return arr[idx] < xx; }
　auto i = std::lower_bound(indices.begin(), indices.end(), x, cmpFunc3);
arr[*i];
じゃあこれで

119:デフォルトの名無しさん
21/04/06 18:31:21.10 rUOwZVXJ.net
>>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とみなす。
　　const SomeBigObj& obj1 = (a < 0) ? x : arr[a];
　　const SomeBigObj& obj2 = (b < 0) ? x : arr[b];
　　return (obj1 < obj2);
　};
　// lower_bound()の第3引数(検索キー)を有り得ないindex値にしておく。
　auto found_it = std::lower_bound(indices.begin(), indices.end(), -1, cmpFunc);
　// Indexに変換
　return (int)std::distance(indices.begin(), found_it);
}
動作するサンプル例：
URLﾘﾝｸ(ideone.com)

120:デフォルトの名無しさん
21/04/07 00:39:13.23 C05ugDVV.net
const int lb = std::distance(indices.begin(),std::partition_point(indices.begin(), indices.end(), [&x,&arr](const int i){ return arr[i] < x; }));
これでどうかな？

121:デフォルトの名無しさん
21/04/07 01:13:46.41 B+YGKOyD.net
>>115
エピさんかしらん

122:デフォルトの名無しさん
21/04/07 01:17:07.25 KcAzRCeR.net
>>118
動くってば
URLﾘﾝｸ(ideone.com)

123:デフォルトの名無しさん
21/04/07 05:42:50.50 FlnHFJBF.net
>>121
しらそん
おま環

124:デフォルトの名無しさん
21/04/07 06:26:08.77 hpqJGpH8.net
>>122
動かないのをおま環言うのはよく聞くがその逆を聞いたのはこれが初めてかも

125:デフォルトの名無しさん
21/04/07 07:24:58.99 FlnHFJBF.net
確かに動いているように見えるが（呼び出し回数も2分探索相当に見えるが）
Compにそんな引数渡して委員会？！
錯覚じゃないの；；；

126:デフォルトの名無しさん
21/04/07 08:00:02.53 FlnHFJBF.net
std::lower_bound(first last, value, comp);
という呼び出しにおいて、compはcomp((firstやlastと同じ型のiteratorが指す要素), value)
という呼び出され方しかされないこと、および
valueの型はfirstやlastが指す要素の型とま無関係に好きな型にして良いと規格で決まっている？！

127:デフォルトの名無しさん
21/04/07 09:20:20.01 F9L3hm15.net
チラッと規格見た限り
value は first、last と無関係でいいし
comp の第一引数はfirst、lastのiteratorが指す型で、第二引数はvalueの型に決まっているように見える

128:デフォルトの名無しさん
21/04/07 12:44:59.78 94shRdbf.net
>>51じゃないが、オブジェクト指向で設計する意味が分からなくなった
汎用性の高いフリー関数が沢山あればそれで良いじゃん

129:デフォルトの名無しさん
21/04/07 15:37:37.40 2guWvkPP.net
>>126
> comp の第一引数はfirst、lastのiteratorが指す型で、第二引数はvalueの型に決まっているように見える
そこは決まってないと思う。

130:デフォルトの名無しさん
21/04/07 15:42:26.98 2guWvkPP.net
・・・いや、 lower_bound() 限定なら引数の順番もその想定でいいのか。
upper_bound() だと comp(value, x) になったりするから、交換可能にしとくのがいいけど、
片方だけ使うなら交換可能にする必要はない、と。

131:デフォルトの名無しさん
21/04/07 15:44:08.41 2guWvkPP.net
参照: URLﾘﾝｸ(timsong-cpp.github.io)

132:デフォルトの名無しさん
21/04/07 15:45:24.56 x8RK+cZQ.net
>>128
requiresのとこは見た？

133:デフォルトの名無しさん
21/04/07 17:04:44.94 x8RK+cZQ.net
c++20からprecond

134:itionsって書き方に変わったのか。 >>129 upper_boundのpreconditionsには第一引数がvalueのほうしか書いてないよ

135:デフォルトの名無しさん
21/04/08 06:24:25.70 ByNsu0yr.net
質問者ですレス㌧クス、
>>117の書き方で >>121が正しく動いているように見えるのは未定義動作でなくてSTLの仕様ってことでＦＡ？
>>126や >>129のような巧妙っていやー巧妙だが風が吹いたら桶屋が儲かるみたいなかりにくい仕掛けなのは
ステパノフあたりの発案なんですかね……

136:デフォルトの名無しさん
21/04/08 10:00:06.97 b/WIqkut.net
>>132
あ、ごめん。比較関数の引数順を交換可能にするのは lower_bound, upper_bound 両用にすることを想定しての話。

137:デフォルトの名無しさん
21/04/08 16:09:17.02 uZSkMyuO.net
生魚にあたって、
入院した病院の天井みながらSTL考えてたもんな

138:デフォルトの名無しさん
21/04/08 16:25:55.36 /Z+9yHN3.net
ステパノフ？

139:デフォルトの名無しさん
21/04/08 23:02:01.67 6aXKgzGP.net
ニダーランが終了になるそうだ
もう糞スレは立てにくくなるな
ざまあ

140:デフォルトの名無しさん
21/04/09 01:15:08.43 iqXbiQSS.net
>>135
STLなんてかっこつけたネーミングだけど
やってることはリニアサーチwww

141:デフォルトの名無しさん
21/04/09 11:44:34.26 B1MFSAev.net
C++11でのstd::swapは、次のようなコードになっているそうですが、
仮に、もし(1)が終わった直後にt1の中のポインタ型やshared_ptr<A>のメンバに
nullptr的なものが代入されるんでしょうか。
仮にt1のポインタ的なメンバにnullptr的なものが代入されない場合、
(2)でt1への代入に置いて何が起きるのか心配です。
質問の仕方を変えるならば、
share_ptrは参照カウンタ方式ですのでカウンタのアップ/ダウンは正確でなければ
なりませんが、以下の例では、いったいどの行のどの演算子(またはどの部分)で
カウントアップ/カウントダウンされるんでしょうか。
template<typename T> void swap(T& t1, T& t2) {
　T temp = std::move(t1);　// (1), or T temp(std::move(t1));
　t1 = std::move(t2);　　　// (2)
　t2 = std::move(temp);　　// (3)
}

142:デフォルトの名無しさん
21/04/09 11:45:42.89 B1MFSAev.net
>>139
誤：仮に、もし(1)が終わった直後にt1の中のポインタ型やshared_ptr<A>のメンバに
　　nullptr的なものが代入されるんでしょうか。
正：(1)が終わった直後にt1の中のポインタ型やshared_ptr<A>のメンバに
　　nullptr的なものが代入されるんでしょうか。

143:デフォルトの名無しさん
21/04/09 11:58:14.49 O38yN+C3.net
>>138
C++03にもstd::binary_searchあるぞ

144:はちみつ餃子
21/04/09 12:00:21.75 foJJo5gI.net
>>139
> nullptr的なものが代入されるんでしょうか。
この場合はされる。
ムーブセマンティクス一般においてはムーブ後の抜け殻は「無効なオブジェクト」なのでアクセスに対して保証がないことがあるが、
標準ライブラリのスマートポインタについては所有権を移動させた後にそれが空であり
メンバ関数 get で nullptr が返ることも、 nullptr と == で比較して真であることも保証される。
> いったいどの行のどの演算子(またはどの部分)で
> カウントアップ/カウントダウンされるんでしょうか。
= がその役割を持っている。
ムーブコンストラクタとムーブ代入演算子によってカウントされる。

145:デフォルトの名無しさん
21/04/09 12:02:12.29 B1MFSAev.net
>>140
どうやら、
(1) の中央の = では、TからTへの move-construc

146:torが呼び出され、 (2)や(3) の中央の = では、TからTへの move-assignment operatorが呼び出される、ということのようですが、 Tのmove-contructorやmove-assingment operatorは、ユーザーの実装次第で、ユーザーがそれらを明示的に書かなかった場合の「デフォルトの定義」は現在もまだ論争中で、標準的な仕様が決まってない、ということらしいですね。間違っていれば指摘してください。

147:デフォルトの名無しさん
21/04/09 12:11:46.34 fGHst4+7.net
>>141
そんなのも、ちょっとc\c++をかじったことあるなら
誰でも書けるじゃん
わざわざ誰が書いたかわからないようなものより自作できるなら自作するだろ

148:デフォルトの名無しさん
21/04/09 12:20:57.67 QYkH8yRN.net
>>143
以下のサイトによれば、「標準的な仕様は決まっている」ようです：
drafet C++11 standareのsection 12.8のparagraph 15に
implicitly-defined copy/move constructor は、
「a memberwise copy/move of its bases and members」
であると書いてあるそうですから：
URLﾘﾝｸ(stackoverflow.com)

The implicitly-defined copy/move constructor for a non-union class X performs a memberwise copy/move of its bases and members. [ Note: brace-or-equal-initializers of non-static data members are ignored. See also the example in 12.6.2. —end note ] The order of initialization is the same as the order of initialization of bases and members in a user-defined constructor (see 12.6.2). Let x be either the parameter of the constructor or, for the move constructor, an xvalue referring to the parameter. Each base or non-static data member is copied/moved in the manner appropriate to its type:
if the member is an array, each element is direct-initialized with the corresponding subobject of x;
if a member m has rvalue reference type T&&, it is direct-initialized with static_cast(x.m);
otherwise, the base or member is direct-initialized with the corresponding base or member of x.
Virtual base class subobjects shall be initialized only once by the implicitly-defined copy/move constructor (see 12.6.2).

149:デフォルトの名無しさん
21/04/09 12:39:59.46 QYkH8yRN.net
>>142
>ムーブセマンティクス一般においてはムーブ後の抜け殻は「無効なオブジェクト」なのでアクセスに対して保証がないことがあるが、
>標準ライブラリのスマートポインタについては所有権を移動させた後にそれが空であり
>メンバ関数 get で nullptr が返ることも、 nullptr と == で比較して真であることも保証される。
なるほど。
行(1)の場合、
1. 右辺でstd::move()をt1に行った段階では(実行段階で)マシン語は全く実行されない。
2. 中央の = は、move-constructor と解釈され、Tのmove-constructorが呼び出される。
3. Tの暗黙定義のmove-constructorは、メンバ同士のmove-construcotrなので、
　メンバに shared_ptr<A> a があると、shared_ptr<A>のmoveコンストラクタが呼び出される。
　そして、shared_ptr<A>のmoveコンストラクタは、実行後に「src側(from側)」をnullptr相当の
　状態にしてしまう。
ということのようですね。

150:デフォルトの名無しさん
21/04/09 12:42:08.46 QYkH8yRN.net
>>146
逆に言えば、Tのメンバに、A *pA; のような生ポインタがあると、
Tの暗黙のmoveコンストラクタ/move代入演算子では、恐らく、
「src側(from側)」にはnullptrが代入されない(??)ので、非常に困った
問題を招くかも知れないと？

151:デフォルトの名無しさん
21/04/09 12:44:10.41 QYkH8yRN.net
>>147
Tのデストラクタに
if ( pA != nullptr ) {
　delete pA;
}
などと書いていた場合、問題を生じそうですね。

152:デフォルトの名無しさん
21/04/09 12:45:44.21 iOouO9yu.net
生ポ入りクラスに暗黙move関数定義できたっけ？

153:デフォルトの名無しさん
21/04/09 18:46:49.83 WYvZUx+H.net
c++についてうんちく垂れるやつに限って仕事ができない
そんなうんちくどうでもいいから、さっさと作れよって思われてる先輩いるわ

154:デフォルトの名無しさん
21/04/09 19:06:14.56 PF0aPDJN.net
>>150
プログラマは怠惰であれ、を地で行ってるんだろう

155:デフォルトの名無しさん
21/04/09 19:55:10.43 O38yN+C3.net
>>144
> わざわざ誰が書いたかわからないようなものより自作できるなら自作するだろ
おまえは一生二度とライブラリもOSも使うな
ベアメタルだけで食っていけ
それができたら、おまえに付いてくる者たちが顕れるだろう
できなければ人知れず消えるだけだ
どうなりたいかは、お前の人生だ
俺がどうしろとは言えない

156:デフォルトの名無しさん
21/04/09 20:38:18.09 8YMfBGcF.net
>>150
またお前か。さっさとプログラミング覚えろよ

157:デフォルトの名無しさん
21/04/09 23:03:48.36 mQjFjskh.net
std::binary_search()は戻り値とかなんとboolや
こんなのよかちゃんと位置を返してくれるstd::lower_bound()の方がよっぽど使いでがある
ちなstd::lower_bound()が2分探索か線形探索かは使うイテレータの条件次第

158:デフォルトの名無しさん
21/04/09 23:08:01.53 mQjFjskh.net
std::lower_bound()が線形探索だと断言してくださる香ばしいblogも世の中にはあるが
ｈｔｔｐｓ：／／ｒｓｋ０３１５．ｈａｔｅｎａｂｌｏｇ．ｃｏｍ／ｅｎｔｒｙ／２０１９／０９／１０／１７３７０８
これがまつがいであることは比較関数の中でprintf()でもしたらたちどころにﾜｶﾙ

159:デフォルトの名無しさん
21/04/09 23:29:26.43 mQjFjskh.net
ｺﾞﾒｿリンク先は必ずしも断言はしていなくって、std::set<T>にstd::lower_bound()を適用する例か、
これのイテレータはrandom-access iteratorでないから確かに線形探索になる

160:デフォルトの名無しさん
21/04/10 02:28:09.12 +Yr/nSyJ.net
>>144
こういうのが井の中の蛙ってのだな
蛙くん

161:デフォルトの名無しさん
21/04/10 13:02:03.74 62UJIlpX.net
>>149
生ポインタのメンバ変数がある場合で、デストラクタで >>148のように
書いている場合は、暗黙のmove関数は自動定義されないようです。
なぜなら、暗黙のmove関数は、デストラクタがユーザー定義されている
場合には自動定義されないためです。
他にも、コピーコンストラクタ、コピー代入演算子、move代入演算子
がユーザー定義されている場合も、暗黙のmove関数は自動定義されない
そうです。

162:デフォルトの名無しさん
21/04/10 13:04:24.60 ziRUnSTY.net
>>158
誤：暗黙のmove関数
正：暗黙のmove-コンストラクタ

163:デフォルトの名無しさん
21/04/11 21:20:47.36 aRgjPq06.net
コンパイラはともかくリンカに計算負担をかけるのはバカな設計だなと思うわ。

164:デフォルトの名無しさん
21/04/11 21:31:53.64 X3ahc6YE.net
>>160 何の設計の話？

165:デフォルトの名無しさん
21/04/11 22:03:18.21 oDlLzjRc.net
暗黙のmoveがnullptr代入してくれないとか生ポあるクラスに暗黙のctor定義してくれるのか、とか
学ぶ順番間違えて勘違いしてるやつ上の方にいるけど
そもそも生ポの扱いに言語が介入するんならdtorでdeleteしてくれるのか、とか考えつかないのかね・・

166:デフォルトの名無しさん
21/04/11 22:28:21.28 AbYQFAoI.net
質問者はポインタ型とshared_ptrについて聞いてたのに、shared_ptrのことしか答えなかった餃子が悪い。
謝れ！俺に

167:デフォルトの名無しさん
21/04/12 13:47:17.66 SAslKmLH.net
指定ソフトのFWを許可するAPI教えてくださいよ

168:はちみつ餃子
21/04/12 15:59:50.47 8pnQviW4.net
そうか。

169:デフォルトの名無しさん
21/04/12 18:14:36.03 jbHGiSQO.net
皆さま御機嫌よう、ちょっと質問させてください
class hogeの内部でenum class fugaを定義し、
そのfugaをclass hogehoge でメンバ変数として使用したいのですが、
hogehoge のヘッダーにはなるべくhoge をインクルードさせたくありません。
もちろんfuga変数はヘッダーに置いて使用したいのですが�

170:c… 前方宣言でfugaを宣言してもhoge::fugaと互換？が無いため代入が出来ません。キャストで戻したりして使っているのですがこれならintでもいいかなと…… クラス内クラスの前方宣言は難しいのでしょうか？何か方法がありましたら教えていただきたく…… class hoge{ enum class fuga{ one,two,three,SUM }; }; //ヘッダーはソースにインクルードしたい class hogehoge{ hoge::fuga mfuga; }; こんかかんじで使いたいのですがエラーになってしまいsまずorz

171:デフォルトの名無しさん
21/04/12 18:58:57.80 jbHGiSQO.net
enum classはグローバルに置いた方がいいんでしょうか？
任意のクラス内部で規定したいenumが見た目も便利だと思ったのでなるべく入れ子にしたかったのですが

172:デフォルトの名無しさん
21/04/12 19:30:43.48 e7ZnlCa0.net
>>167
hoge をインクルードしないところで hoge::fuga を使いたいということは
fuga は hoge にそれほど強く結びついていないということで、外に出すのが妥当なのでは？
外に置いたうえで hoge 内で using fuga = outer_fuga とでもすれば、見た目は損なわれないだろうし。

173:デフォルトの名無しさん
21/04/12 19:43:07.58 jbHGiSQO.net
>>168
名前に「ホゲで使うフガ」と名付けるのがいいですかね？
前方宣言で定義したクラスは不完全型みたいでクラス内クラスにアクセスする場合は別途定義が必要みたいです……
難しい感じですかね

174:デフォルトの名無しさん
21/04/12 19:43:19.37 jbHGiSQO.net
ありがとうございました

175:デフォルトの名無しさん
21/04/13 19:17:47.93 CekyfU50.net
std::sortがセーフソートかどうかって決まってないんですね？

176:デフォルトの名無しさん
21/04/13 19:20:46.00 dUpGrFVX.net
セーフソートとは何なのか、決まってないですね。

177:デフォルトの名無しさん
21/04/13 19:49:36.98 3ATJKALM.net
安定ソートのことならstd::stable_sortを使え

178:デフォルトの名無しさん
21/04/13 20:39:25.63 E/HY6RLS.net
std::stable_sort<T>はどうしてもstd::sort<T>より遅い
からstd::stable_sort<T>で安定ソートするテクニックが存在するし需要がある

179:デフォルトの名無しさん
21/04/13 20:57:29.81 E/HY6RLS.net
もちろんタダでというわけにはいかずn個のTのソーティングに対しn個の整数型の配列が別途必要だがとにかくできる

180:デフォルトの名無しさん
21/04/13 20:58:57.72 E/HY6RLS.net
まつがえたorz
誤： std::stable_sort<T>
正： std::sort<T>

181:デフォルトの名無しさん
21/04/13 21:07:31.95 E/HY6RLS.net
計算量の仕様からすると何だかんだ言って
std::stable_sort<T>の中身はマージソートで、
std::sort<T>の中身はイントロソートとクイックセレクトとクイックソートの複合技
ぐらいしかありえない

182:デフォルトの名無しさん
21/04/13 21:10:52.16 CekyfU50.net
みなさんありがとうございます
安定ソートのことでした

183:デフォルトの名無しさん
21/04/14 05:40:12.90 OwJGUJdo.net
> std::stable_sort<T>の中身はマージソートで、
これはまあそんなもうだろうけど
> std::sort<T>の中身はイントロソートとクイックセレクトとクイックソートの複合技
なんでここまで限定するんだ？

184:デフォルトの名無しさん
21/04/14 06:51:50.47 1+2DD+HN.net
URLﾘﾝｸ(cpprefjp.github.io)
>C++11以降: O(N log N) (N == last - first) 計算量での比較
>クイックソートは平均計算量がO(N Log N)だが、最悪計算量がO(n^2)である。そのため、C++03の計算量要件には合致するが、C++11の要件には合致しない

185:デフォルトの名無しさん
21/04/14 06:52:54.28 mDTOVFC3.net
ubuntuでの開発環境って何があるんでしょうか？
openglなのでc++を使うことになると思うんですが、c++はideとしてvscodeでいいですよね
guiは何が一般的なんでしょうか？

186:デフォルトの名無しさん
21/04/14 07:20:31.68 OwJGUJdo.net
> この関数には、特定のアルゴリズムで実装すべきという規定はない

187:デフォルトの名無しさん
21/04/14 07:23:57.67 OwJGUJdo.net
古典的なソート議論はユニプロセッサ前提
今どきの並列化の流れに必ずしも当てはまるとは思えない

188:デフォルトの名無しさん
21/04/14 07:27:25.07 B6LD9tEC.net
boost::sort

189:::pdqsort(), boost::sort::block_indirect_sort() あたりならヘッダーだけで並列ソートできる

190:デフォルトの名無しさん
21/04/14 09:23:48.49 hYFflu6b.net
>>181
GUIなんか使わないのが一般的だよ
開発環境にわざわざC++とLinuxを選ぶような人は自分用アプリにGUIなんて組み込まないだろうし、
他人に使わせるならどうせWindowsでテストしなきゃいけないからLinuxなんて時間の無駄だ
OpenGLだったらOpenGLの描画結果を表示するウィンドウとターミナルでいい

191:デフォルトの名無しさん
21/04/14 10:52:22.55 OwJGUJdo.net
自分用アプリねえ
俺の定規ウインドウなんてGUIだけど

192:デフォルトの名無しさん
21/04/14 11:09:58.93 lMgtIJ1Q.net
定規ww

193:デフォルトの名無しさん
21/04/14 12:59:06.52 mDTOVFC3.net
>>185
qtですか？

194:デフォルトの名無しさん
21/04/14 16:06:34.29 qBzPSYhh.net
定規がとても気になる

195:デフォルトの名無しさん
21/04/14 16:25:09.90 qBzPSYhh.net
ぐぐったら沢山出てきた
頭が悪くて理解出来ないけど需要あるんだね

196:デフォルトの名無しさん
21/04/14 17:07:15.14 X49CrYgb.net
unique_ptr<hoge> 自体が型名なんでしょうか？
class unique_ptr<hoge>で前方宣言してもいいのかな？

197:デフォルトの名無しさん
21/04/14 18:15:29.38 OwJGUJdo.net
明示的な具現のつもりなら構文が違うね

198:デフォルトの名無しさん
21/04/14 18:22:49.87 X49CrYgb.net
素人なんで自分の説明が難あると思うんだけど自分なりに精一杯説明すると、
ヘッダー部の引数にclass unique-ptr<hoge>& uhogeを載せて、
ソース部にhoge.hをインクルードして定義する感じでつかいたんだけども……
試してみたけど動くんだけどなんか怖い
想像ではunique-ptr<class hoge>が前方宣言だと思ってたもので……
どこをどう調べればいいのかだけでも教えていただければ……

199:はちみつ餃子
21/04/14 18:34:21.63 VF/LllcQ.net
>>191
テンプレートのインスタンス化は暗黙にやってくれるので基本的にはする必要がない。
どうしても宣言したいのなら
extern class unique_ptr<hoge>;
と書くことは可能。
ただし、このように宣言した場合には暗黙のインスタンス化は抑制されるので、
別の場所で明示的インスタンス化をしておく必要がある。
テンプレートの展開はその仕組み上、各翻訳単位ごとにやった上でリンク時に統合されるというクソみたいなことになってるので、
コンパイル時間を抑制したいなどの理由でこういった変なことになってる。

200:デフォルトの名無しさん
21/04/14 18:51:48.53 X49CrYgb.net
ユニークポインタ自体の大きさが、ポインタだから4バイトくらいに統一されているのかな？
型テンプレートがどんな型でも、定義部分で明示してあればポインタ長のメモリをアロケートされているから、宣言自体はある程度の許容範囲があるということなのかな？
理解が違ってたらすいません

201:デフォルトの名無しさん
21/04/14 19:01:58.75 IrZTmcl1.net
>>191
1行目yes
2行目はその場合クラステンプレートの明示的実体化になる
前方宣言の場合は
template <class T, class D>
class unique_ptr;
(もちろん名前空間std内
テンプレートは引数与えられてない限りあくまでテンプレートであってコードは生成されないよ
 >>194
え、明示的インスタンス化しておけばコンパイル時間抑制できるの？

202:デフォルトの名無しさん
21/04/14 19:39:51.01 udtyfuhd.net
前方宣言というのはあくまで「こういう名前のこういう奴が（どっかに）いますよ」って言ってるだけ
実体がどんなサイズでどんな値やメンバやなんやかんやを持ってるかとかには関知しない

203:はちみつ餃子
21/04/14 21:35:38.45 VF/LllcQ.net
>>196
> 明示的インスタンス化しておけばコンパイル時間抑制できるの？
ちがうちがう。
extern のほう (宣言) が暗黙のインスタンス化を抑制するからコンパイル時間が短縮されることが期待できる。
でも、インスタンス化を抑制するんだからどこか別の翻訳単位に実体が存在する必要はあって、
それに明示的インスタンス化を使えるようになってるって話。

204:デフォルトの名無しさん
21/04/14 22:23:18.21 IrZTmcl1.net
あーなるほどね、thx

205:デフォルトの名無しさん
21/04/14 22:43:29.65 B6LD9tEC.net
今時コンパイル時間を稼ぐとかどうなの

206:デフォルトの名無しさん
21/04/14 23:07:25.20 IrZTmcl1.net
リッチにテンプレート使いまくって一本ソフト書いてみ
まぁわかりやすいのはspiritとかのET使ったやつ、それを複数のソースファイルで使いまくればわかる
さらに言えば自分でそういうライブラリ書いて少しの変更でほぼフルビルドかかるのを体験すればわかるやろ

207:デフォルトの名無しさん
21/04/15 00:02:44.73 5MHywbxF.net
>>200
今時コンパイル時間を気にしないほうが頭悪いわ。

208:デフォルトの名無しさん
21/04/15 00:26:49.07 daBkAWQM.net
いまいちメタプの必要性が理解できん
コンパイル時に決定してる値しか計算できないんでしょ
3の階乗は計算できるけど、ユーザーから入力された値の階乗は計算出来ないって・・・
だったらはなから6ってハードコーディングしとけ

209:はちみつ餃子
21/04/15 00:38:40.10 FEj8Wx1j.net
>>203
抽象化の手段でもある。
脳内で計算できる程度のものであっても、
ちゃんと名前が付いた関数になってるほうが
読むほうにとってはありがたいもんだよ。

210:デフォルトの名無しさん
21/04/15 00:54:46.36 3EsQmY5s.net
>>203
こういう書き方出来たら便利なのにな、とかを無理矢理実現できるというロマンはある
(マクロと似たようなもんだが
プロパティみたいなことも一応出来るし
ただまぁ・・・労力に見合うか、というと散々だわマジで。
持て囃すようなものでは決してない(他人のふんどしでドヤりたい連中が持て囃してるだけ

211:デフォルトの名無しさん
21/04/15 00:59:45.76 5MHywbxF.net
>>203
まあ実際ビルドシステムを自分で構築するかコンパイラにやらせるかの違いしかない。
フーリエ変換の係数みたいなものを事前に設定するとかは少し便利かもね。
それなりに手計算すると大変だけれどそこまで本格的に計算時間がかからないような
事前計算できて使いまわせるようなものが念頭にあるんだろうが、まあそんなないわな。

212:はちみつ餃子
21/04/15 01:11:57.17 FEj8Wx1j.net
状況に応じてコードジェネレータを用意するよりはマシってくらいか。

213:デフォルトの名無しさん
21/04/15 22:12:02.69 mdNAsIkh.net
>>182
具体的に

214:デフォルトの名無しさん
21/04/16 05:29:55.48 EjuTOEDD.net
>>208
？

215:デフォルトの名無しさん
21/04/16 06:24:07.51 zpAq69hN.net
>>209
？！

216:はちみつ餃子
21/04/16 12:18:05.12 I3AyWR5p.net
ヴィクトル・ユーゴーかよ。

217:デフォルトの名無しさん
21/04/17 08:00:06.17 1dxAtZcl.net
condition_variableってなんでこんなに面倒なんだ
winなら、イベントの方が高速だし楽で懐疑起床も起きないし

218:デフォルトの名無しさん
21/04/17 08:06:00.96 3mxJ/fRx.net
>>212
特定変数に依存しないbool条件式で起床できるのはWindowsのイベントよりも楽で応用が利く
今さらイベントには戻れない便利さがある

219:デフォルトの名無しさん
21/04/17 08:13:31.45 nI8O4VG/.net
>>212
ほんまこれ。せめてspurious無かったらなあ。
めんどいから手っ取り早くspinして待ってまうわ。

220:デフォルトの名無しさん
21/04/17 08:49:19.47 1dxAtZcl.net
>>213
その式を書かなくてもいいイベントを使ってからは
condition_variableには戻れなくなった

221:デフォルトの名無しさん
21/04/17 10:51:59.94 WHLcQryV.net
おすすめ本ってありますか？
C言語のプログラムを、文法などカンニングしながら書けるレベルです。

222:デフォルトの名無しさん
21/04/17 13:30:52.06 l53+7OwH.net
cppreference.comの何が不満かによる

223:デフォルトの名無しさん
21/04/17 14:51:21.11 ohP60UMx.net
それだけ読んで理解した奴なんておらんやろ。

224:デフォルトの名無しさん
21/04/17 17:33:14.75 3mxJ/fRx.net
プログラミングにカンニングという概念はない
常にオンラインヘルプなので正確な仕様を確認しながら作業するのがプログラミングの常なので、
カンニング(仕様確認、他人の書いたコードをチラ見してコーディング規約ぶ追従)は仕事の一部

225:デフォルトの名無しさん
21/04/17 17:41:48.19 3mxJ/fRx.net
訂正
プログラミングにカンニングという概念はない
常にオンラインヘルプなどで正確な仕様を確認しながら作業するのがプログラミングの常なので、
カンニング(仕様確認、他人の書いたコードをチラ見してコーディング規約に追従)は仕事の一部
明確なコーディング規約がない場合にはなおのこと、カンニングが重要になる

226:デフォルトの名無しさん
21/04/17 18:08:39.80 LyWUtAnN.net
RTTIなんかカンニングだろって個人的に思う

227:デフォルトの名無しさん
21/04/17 19:10:13.22 3mxJ/fRx.net
condition_variableに似た関数SleepConditionVariableCS()がWin32APIにも用意されてるけど、直感的で使いやすいのはcondition_variableでしょ
URLﾘﾝｸ(docs.microsoft.com)

228:デフォルトの名無しさん
21/04/18 10:59:46.23 lylRPiha.net
質問なのですが教えてくだちい
Q1. 64 bit符号付整数の積の結果をオーバーフロー無しで（128 bit等で）で得る方法
　　※ 64 bit整数を2^32進数2桁とみなして筆算する処理より速い方法ｷﾎﾞﾝ
　　　　SSE4.1可
Q2. （Q1にうまいやり方が無い場合）64 bit符号付整数の積がオーバーフローしたことを検知する方法
Q3. 多倍長整数（例えば8要素のunsigned longの配列として表された符号無し整数0～2^256-1）
　　を10で割る方法orz

229:デフォルトの名無しさん
21/04/18 11:05:45.65 lylRPiha.net
Q2は現状a*bの前に std::abs(a) <= std::numeric_limit<int64_t>::max / std::abs(b) という判定をやっているのですが
もっと速いやつ（除算不要のやつ）ｷﾎﾞﾝ、

230:デフォルトの名無しさん
21/04/18 13:15:25.56 aOZ5UqSE.net
>>223
参考になるかもしれない
URLﾘﾝｸ(www.slideshare.net)

231:デフォルトの名無しさん
21/04/18 14:35:23.87 HGo0FTuj.net
winならMultiply128、gccやclangなら__int128ってのが使えるみたいだけど

232:デフォルトの名無しさん
21/04/18 15:14:50.22 regwJJSX.net
競技プログラミングではよくある質問

233:デフォルトの名無しさん
21/04/18 17:15:30.07 B2k51TVB.net
>>223
特定の環境ならアセンブラでやっちゃえば？
ちなみに環境は？
昔その辺の演算は良くやった
Q3は10の逆数を求めておいてかけ算命令でやるのが良いけど
多売長は何進数？
10で割るだけの為にバッファスキャンはもったいない
何かの演算とセットに出来ない？
もしやりたいことが2進多倍長の10進数化なら
もっと良い方法がある

234:デフォルトの名無しさん
21/04/18 17:17:36.41 B2k51TVB.net
環境 (CPU, OS)
多倍長の構成 (整数？指数部あり？2進？10進？変則？)
最終的に何がやりたいか
この辺がわかれば色々と教えられる

235:
21/04/18 17:32:50.11 8N2uJcok.net
>>223
>>225 も多倍長演算ですか、じゃ、私も私の多倍長演算を
ｽﾚﾘﾝｸ(tech板:37番)
＞Q3. 多倍長整数を10で割る方法
であれば上のリンク先の line:383 から、std::ostream &operator<<(std::ostream &stream, mpz_base_class c)　にて、ちょこっと工夫したつもりです、剰余は下位から確定する点では普通、ですので順序を逆にするのはアレかもしれませんが

236:デフォルトの名無しさん
21/04/18 18:08:23.13 lylRPiha.net
とりあえず筆算のやつをｺﾞﾘｺﾞﾘ書いてや
った
URLﾘﾝｸ(ideone.com)

237:デフォルトの名無しさん
21/04/18 18:32:04.62 2o2Y05bZ.net
多倍長÷32bitを除算命令を用いてやるのはアホ

238:デフォルトの名無しさん
21/04/18 18:34:03.31 lylRPiha.net
>>232
kwsk

239:デフォルトの名無しさん
21/04/18 19:14:51.87 2o2Y05bZ.net
ヒント
除算は遅い
除算は逆数の乗算
定数の除算のコンパイル結果

240:デフォルトの名無しさん
21/04/18 21:49:11.94 lylRPiha.net
（聞くんじゃなかった…

241:デフォルトの名無しさん
21/04/18 22:02:51.07 lylRPiha.net
ちゅか10で割るのは10の剰余を知りたいからなのだというのは
言ってなかったわｻｰｾﾝ、orz
多倍長整数の10進数表現を得るために、多倍長整数を10で割って剰余を求める必要があった
この目的には誤差の見積や処置が面倒な方法はNGでありかつ
10進数化とかどうせ表示の時しか使わないのでこの割り算自体はそうメチャクチャチューニングする必要は
ありませぬ（と後出し

242:デフォルトの名無しさん
21/04/18 22:16:10.35 lylRPiha.net
もしｶﾞﾁで全く除算を使わずに10進数に変換せよと言われたら
5*10^n、2*10^n、1*10^nを作ってnがデカい順に元の数と比較して引いていく、
ぐらいしかなさげ
知らんけど

243:デフォルトの名無しさん
21/04/19 00:09:37.42 cH3u5yp0.net
>>223
トンチンカンなこと聞いてたらすみませんが、Q1って多倍長整数を文字列で持ってカラツバ法とか高速フーリエ変換で計算するやり方だと「遅い」んですか？

244:
21/04/19 00:24:31.83 6sLSrXGT.net
>>236
であれば >>230 で
まあ多倍長演算を実装するのならアセンブラが最適で、なんといってもキャリーフラグやゼロフラグを触れるのはアセンブラしかないですからね
というか、C/C++ だけで多倍長を実装するなんて馬鹿なことを思いつくのは私くらいですかね‥‥

245:
21/04/19 00:29:31.32 6sLSrXGT.net
>>238
＞カラツバ法とか高速フーリエ変換で計算するやり方だと「遅い」んですか？
これらは、オーダーは O(n^2) より下のクラスなので速いのはそのとおりですが、しかし使えるのは掛け算のときだけですね
まあ逆数を掛けるという意味では割り算も OK かもしれません、そして逆数計算は「単桁 vs 多桁」だから、オーダーは無視できますし
それはそうと、昔バグっていた例のペンティアムの除算アルゴリズムを解説してくれるサイトはないですかね‥‥

246:
21/04/19 00:31:27.00 6sLSrXGT.net
>>236
いいわすれましたが、商が高速に求められれば、剰余は　被除数－商×除数、で求めるものですし、多分高速除算・高速剰余計算は多分そうしているでしょうね

247:デフォルトの名無しさん
21/04/19 00:33:03.64 cH3u5yp0.net
>>240
質問者は掛け算と10で割る (小数点以下は無視する割り算ですよね？) しか聞いてないので、掛け算さえできれば良くないですか？

248:デフォルトの名無しさん
21/04/19 00:37:49.63 cH3u5yp0.net
ああ、10で割るのはあまりを求めたいからって書いてあった
でも10で割った余りって1の位の数字ですよね？
そんな話じゃない？

249:デフォルトの名無しさん
21/04/19 00:39:51.82 cH3u5yp0.net
まあいいや
チューニングする必要はないって話なんで、わり算の話は置いといて、結局やりたいのは整数同士の掛け算ですよね？

250:デフォルトの名無しさん
21/04/19 00:45:58.97 r2ULphPG.net
質問者が情報を後出ししたりしていてイマイチ信用に欠けるので、普通の整数のように何でもできる多倍長整数がほしいのか掛け算さえできればOKなのかは不明

251:
21/04/19 00:46:33.44 6sLSrXGT.net
>>243
そんな話です
でも2進10進変換をやりたいのなら、基本的に 10 で割った剰余を求める以外に手はありませんね

252:デフォルトの名無しさん
21/04/19 00:49:32.73 cH3u5yp0.net
>>246
では、最初から10進数を文字列で持てば2進10進変換をする必要がない、というのが僕の立場の回答になりますね
やりたいことが掛け算だけなら、という条件が付きますが……

253:
21/04/19 01:17:33.43 6sLSrXGT.net
>>247
最初から10進で数値を持つと、加減算ですら速度が低下します
10進化の頻度は各種演算の頻度よりも少ない、というか、演算を何千回・何万回した最後に 10　進に変換する、かもしれない、っていう状況で、最初から 10 進で持つのは無駄以外の何ものでもないかと
それに32bit までは BCD 補正命令がありましたが 64 bit の今は BCD 補正命令（AAA とかね）ですら削除されちゃっていますし

次ページ