C++相談室 part162

1 名前：sage [2022/10/31(月) 14:29:35.57 ID:J5sgTSch0.net] !extend:checked:vvvvv:1000:512 !extend:checked:vvvvv:1000:512 ↑同じ内容を3行貼り付けること 次スレは>>980が立てること 無理なら細かく安価指定 ※前スレ C++相談室 part161 https://mevius.5ch.net/test/read.cgi/tech/1653135809/ VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured 651 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 8710-bPD3) mailto:sage [2022/12/10(土) 23:34:26.52 ID:lr6mtoK80.net] >>631 jの型はアドレスint*やで iと&iが別実体と解釈されてないとこの処理系の挙動は説明できないよ 652 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 00:20:42.40 ID:Pzj62nR+0.net] >>632 左様かｽﾏﾝｶｯﾀorz 今神のお告げがあったが多分 >iと&iが別実体と解釈されてないとこの処理系の挙動は説明できないよ というのは >変数iとcout << の引数としての定数1が別実体と解釈されてないとこの処理系の挙動は説明できないよ と考えたら>>625と同じ…… 653 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 00:25:27.26 ID:Wb0o85TW0.net] >>633 iが最適化後定数だろうとconst変数だろうと&iについての説明が必要だし >>625を否定してるわけじゃないよ >>625のうえで&iがどう処理系で実装されているのかという話 654 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 00:29:21.03 ID:Wb0o85TW0.net] あーごめん>>634は取り消し 655 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 16:42:27.87 ID:le6rXKgRM.net] 未定義動作ではいおしまいは思考停止では？ コンパイラの実装を考えてみるのも面白い 656 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 17:18:36.24 ID:SgVyrwp80.net] ゴミ捨て場の汚物の配置を面白がる趣味もいいけどそれで宇宙の真理を読み取ったとか言い出されても困るんだわ 657 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 17:28:44.13 ID:B9k8N7vL0.net] 特定のコンパイラの挙動が知りたいなら逆アセしろ 仕様が知りたいなら未定義動作 と言うだけの事だろ 658 名前：デフォルトの名無しさん mailto:sage [2022/12/11(日) 19:27:20.67 ID:vt5XMNwC0.net] 未定義踏んで、たまたま望む動作だった場合に、それを放置するのは危険すぎる 659 名前：はちみつ餃子 mailto:sage [2022/12/11(日) 19:44:01.28 ID:ftKoc+Hh0.net] 前後の状況との組み合わせでも結果が変わったりするから短いコードで試しても そのコンパイラでの挙動を知れたとは言えんし……。 660 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 02:44:59.90 ID:m98xyCFn0.net] 挙動を考えるというか思想とか背景を考えるのが面白いんだよ 組み込みじゃconst領域は物理的に変えられない場合があるからって 余計な事考えちゃったけどたしかに>>625だろうなって 661 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 14:55:49.27 ID:P0mM9QsZM.net] vector<string> v; の vを辞書順でソートした場合、string自体はメモリ上に 連続して並ぶが、肝心の文字列バッファは free store 上でバラバラに離れた 位置になるからキャッシュ・ミスし易くなるね。 stroustrup氏はリンクリストがキャッシュミスし易いと言って馬鹿にしていたが、 実際には動的配列(vector)でも大差は無い。 なお、リンクリストでキャッシュミスし易い典型例がソート後の全巡回ループ。 そしてその場合、vectorでもstringのようなメモリ資源ハンドルの場合は キャッシュミスが免れない。 662 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:09:17.26 ID:P0mM9QsZM.net] >>642 [補足] そもそも、C++はcopyの代わりのmoveによる高速化を自慢しているが、 それが意味を持つのはstringのようにfree storeのメモリをポインタで持っている ようなクラスである。 このご自慢のmoveが良く効くクラスTのvector<T>をソートした場合、 free storeの本当の中味のアドレスはソートされないまま。 なので、vectorを全巡回する時には、アドレスが飛びとびになり、キャッシュミス が起き易い。 663 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:14:58.58 ID:b4gQwKir0.net] >>642 うんうん。リンクリストにするとキャッスミスし易さがもう少し悪化するね。 664 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:21:22.44 ID:P0mM9QsZM.net] >>644 この例の場合、vectorをlistに変えてもあまり悪化しない。 なぜなら、stringとその文字列バッファが近接したアドレスのfree store 上にallocateされていると期待できるから。 665 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:26:03.32 ID:P0mM9QsZM.net] >>645 [補足] list<string> v2; の場合、push_back すると、 p1 = new string; 相当の事が実行されるが、p1 の内部の文字列バッファも、string のコンストラクタ の中で p2 = new char[N]; のようにして free store から確保される。 確率的には、p1 と p2 は非常に隣接したアドレスになっている可能性が非常に 高い。 その結果として、p1をアクセスした直後にp2にアクセスしてもキャッシュミスは起きない。 その結果、vector<string>とlist<string>のソート後の全巡回でのキャッシュミス回数は、 ほぼ同じ。 666 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:33:08.04 ID:b4gQwKir0.net] >>645 そうだね。悪化するのは少しだけだね。 おや？ >>642 ではバラバラに離れてキャッシュミスしやすいと言っていた文字列バッファが リンクリストの話になると近接するのかい？不思議だねぇ。 667 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:34:37.69 ID:s9w5HO4Md.net] 典型的な用途ではsmall-string optimizationで大部分が連続になるでしょ リンクリストにその恩恵はない 668 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:37:07.44 ID:P0mM9QsZM.net] >>647 669 名前： >おや？ >>642 ではバラバラに離れてキャッシュミスしやすいと言っていた文字列バッファが >リンクリストの話になると近接するのかい？不思議だねぇ。 ソートしたときには、stringと対応する文字列バッファは意味論的には くっついている。だから、「対応している」両者は隣接しているんだ。 [] [ここ壊れてます] 670 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:39:41.84 ID:P0mM9QsZM.net] >>649 [補足] vector<string>をソートすると、stringの「箱」が新しく確保されてしまうので、 中身だけがmoveされるので、stringと対応する文字列バッファは「離れ離れになる」 list<string>をソートすると、stringはアドレスは全く変化せず、string同士の リンクのされ方だけが変化するだけだから、stringと対応する文字列バッファは、 メモリー空間上でのアドレスの隣接を維持する。 671 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:40:54.03 ID:P0mM9QsZM.net] >>648 それはstringだけの話。 今回はstringを例にとって話しただけで、一般のTではそんな現象は起きない。 672 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 15:49:40.91 ID:P0mM9QsZM.net] >>650 [補足] vector<string>のソート後の様子: アドレス 0x0000: st100 ---> buf100 (st100とbuf100のアドレスは離れ離れ) 0x0010: st5 ---> buf5 (st5とbuf5のアドレスは離れ離れ) st100とst5は隣接する。 ソート時に中身のアドレスだけがmove。 list<string>のソート後の様子: st100 ---> buf100 (st100とbuf100は隣接したまま) st5 ---> buf5 (st5とbuf5は隣接したまま) st100とst5は隣接しない(但し、元のアドレスを維持したまま)。 ソート時には、一切のmoveもcopyも全く発生せず。 673 名前：デフォルトの名無しさん mailto:sage [2022/12/12(月) 22:25:35.59 ID:1Of7Vyge0.net] いちいちキャッシュのことまで考えて書いたことなんかないですねえ 674 名前：デフォルトの名無しさん [2022/12/12(月) 22:29:51.34 ID:EC98/b6s0.net] 天才ですから 675 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 8710-bPD3) mailto:sage [2022/12/12(月) 22:53:10.09 ID:m98xyCFn0.net] ソート済みならソートの利点を生かしたデータアクセスが主だろうからなあ まあ最悪値を考えるかアベレージを考えるかはプログラム次第か 676 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ df28-GD9R) mailto:sage [2022/12/12(月) 23:33:02.97 ID:OmhP4qQH0.net] キャッシュミスが起きるとか キャッシュに収まりきらない要素数のリンクリストを 全要素まんべんなくアクセスし続ける場合とかの話であって そうなれば区々たるデータ構造などあんま意味を成さなさげ 677 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 06:29:45.20 ID:RVT68Vp10.net] >>656 だからお前のコードは遅いんだな 678 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 07:27:28.93 ID:XemHbbXi0.net] 配列とハッシュの話を蒸し返すけど、キャッシュに退避したデータを取り出す仕組みはハッシュなので、配列も無意識・無自覚のハッシュといえる 679 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 07:49:45.53 ID:HbzfEbfW0.net] トホホｗ 680 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 09:16:15.65 ID:Dz/G0kAxd.net] プログラムのフェッチもハッシュ、ライトもハッシュ、全てはハッシュに収束するのだ 681 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 09:37:04.67 ID:XemHbbXi0.net] ありていにいえば、他のレイヤーのデータを参照する時にハッシュを使わないと処理速度が落ちてしまうので、いたるところに速度対策でハッシュ参照が実装されているってのがFA 682 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 09:54:38.28 ID:6kCyUqZEd.net] 仮にunordered_vectorなるものがあったにしても、それはハッシュではない 683 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 10:16:13.34 ID:3/h11tyKd.net] それunordered_setじゃね 684 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 10:32:20.10 ID:nLXwCo+B0.net] vectorはそもそもunorderdだろ setは同じ値を格納できないのだからvectorとは違う 685 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 11:27:12.09 ID:qMfL3xzXM.net] 全文字列を結合したものを一括で確保して string_view を操作するのが1番パフォーマンス良さそう 686 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ dfad-KKgq) mailto:sage [2022/12/13(火) 11:41:42.04 ID:XemHbbXi0.net] >>665 失礼な言い方になるかもしれませんが、あなた初心者ですね “パフォーマンス”を気にする人はそもそもC++なんて使いませんよ 687 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa6b-SJNI) mailto:sage [2022/12/13(火) 11:47:57.08 ID:QcbajiAMa.net] >>666 そんなに苦手だったんか まあこれから練習したらええよ 688 名前：U) mailto:sage [2022/12/13(火) 12:02:52.82 ID:RxDW3iqvd.net] パフォーマンスを気にする人は何を使うんでしょうか 689 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 12:10:16.41 ID:6kCyUqZEd.net] >>664 意味わからん 気がふれた？ 690 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 14:54:36.88 ID:56FF6Qc2a.net] >>669 え？w 691 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 16:20:37.61 ID:6kCyUqZEd.net] >>670 vectorがunorderedとが頭おかしいのかって 692 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 16:36:06.63 ID:RxDW3iqvd.net] えっ？？？ 693 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 16:50:01.90 ID:nLXwCo+B0.net] >>669 c++のunorderd_は挿入時に挿入要素のキーによるソートが行われず要素の格納順が実装依存なコレクションに付けられている名称だから、vectorがunoreded_かどうかと言えばyesじゃない？ 694 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 16:51:40.89 ID:Dz/G0kAxd.net] vectorがorder性持ってたら逆に困る 695 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 17:09:14.84 ID:Dz/G0kAxd.net] intkeyのorderedmapってことか 696 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 17:26:33.26 ID:nLXwCo+B0.net] >>675 そういう考え方もあるか でもiteratorで途中指定してinsertしたらそれ以降のキーと要素の対応全部ずれるしmapと考えるのはどうなんだ 697 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 17:27:23.47 ID:qOIMmk+U0.net] ランダムアクセスできるデータ構造でordered_だのunordered_だの定義してもこじつけでしかないし意味薄いんでは 698 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:15:32.74 ID:afkUacc60.net] てす 699 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:20:36.37 ID:7X0MJm0+a.net] そんな事を言い出したらページアウトされてるデータの読出しになるかもしれないからディスクアクセスかもしれないだろ 700 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:25:37.11 ID:6kCyUqZEd.net] >>673 格納順を定義しろ 701 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:29:09.49 ID:6kCyUqZEd.net] ふざけたオレ定義はトコトン馬鹿にしてやんよ 702 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:32:26.52 ID:nLXwCo+B0.net] >>680 iterator でたどれる順番 703 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:35:45.77 ID:nLXwCo+B0.net] >>680 ところでこの話の発端のhashでないunorderd vector ってどんなものをイメージしてたの？ 704 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:46:51.67 ID:RVT68Vp10.net] >>681 まずはお前の定義を書け 705 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:50:59.76 ID:6kCyUqZEd.net] >>682 今、屋台で酒飲んでるから後でな 706 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 18:55:09.41 ID:c7PbDuSHM.net] >>673 vectorは連続したメモリ領域に要素を保存し、順番に並ぶことを保証する。 そうやってc配列との互換性を保っているのは常識かと思っていたけど、仕様変わったの？ 707 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 19:04:10.54 ID:nLXwCo+B0.net] >>686 それで正しいと思うよ c++のunorderd_/(ordered_)は要素をキーにしてコレクションがソート済みになるかどうかを意味してると考えれば>>673とも矛盾してないでしょ？ 708 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ a7f0-exKU) mailto:sage [2022/12/13(火) 19:20:14.84 ID:RVT68Vp10.net] ordered_配列 ==> 勝手に中身がソートされる配列 が思い浮かぶ 709 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM8f-5DNi) mailto:sage [2022/12/13(火) 19:23:38.37 ID:LOsLj3+sM.net] >>688 std::multiset なんてのがあるんだな 710 名前：デフォルトの名無しさん (ｵｲｺﾗﾐﾈｵ MM7b-VZV0) mailto:sage [2022/12/13(火) 19:24:14.15 ID:jWNvO27sM.net] そもそも、ordered かどうかは定義の問題。 まず、mapは、(key,value)を持っていて、keyで検索できる。setは、keyだけでvalueが無いが、 keyで検索できる。setは、mapでvalueをkeyにしたようなもの。だから、以下ではmapだけ の話をする。 mapやunorderd_mapは、「検索」機能とbegin(),end() を利用した「巡回機能」の 両方を持っていて、巡回を key の大小関係順に巡れるかどうかで、 ordered かどうかが決まる。 バランス木(赤黒木など)を使う方が 接頭辞なしの map、ハッシュ法を使う方が unorderd_map 前者の場合は、常に自動的に並び替えられた状態で格納される。 一方、そもそも vector は、好きな順序で入れられて決まったキーもなければ 自動的に並び替える機能も持ってないし、orderedかどうかを定義しても 特に意味が無い。そもそも、orderdのvectorが存在し無い。 また、故意に作ってもしょうがない。 711 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ a7f0-exKU) mailto:sage [2022/12/13(火) 19:26:29.60 ID:RVT68Vp10.net] ordered, unordered が書けないヤツが多すぎ問題 712 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ a7f0-exKU) mailto:sage [2022/12/13(火) 19:27:00.39 ID:RVT68Vp10.net] 実は全部同じ人？ 713 名前：デフォルトの名無しさん (ｵｲｺﾗﾐﾈｵ MM7b-VZV0) mailto:sage [2022/12/13(火) 19:28:42.74 ID:jWNvO27sM.net] >>688 それが大体、「set」や「multiset」に相当する。 714 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 675f-k8RX) [2022/12/13(火) 19:28:56.13 ID:sAeHrnUZ0.net] 巡回機能って何 715 名前：デフォルトの名無しさん (ｵｲｺﾗﾐﾈｵ MM7b-VZV0) mailto:sage [2022/12/13(火) 19:37:41.71 ID:jWNvO27sM.net] >>694 まだ使ったことが無いので書き方が間違ってるかも知れないが、 map<T,V> m; に対して、 for ( auto &r : m ) { 　cout << r.first << ":" << r.second << "\n"; } で巡ることができる機能の事を言ったつもり。 for ( auto i = m.begin(); i != m.end(); ++i ) { 　cout << m[i].first << ":" << m[i].second << "\n"; } と等価だと思う。 ただし、一度も使ったことが無い。 716 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 20:16:44.72 ID:RVT68Vp10.net] >>693 全然処理量のオーダーが違う 0点 717 名前：デフォルトの名無しさん [2022/12/13(火) 21:45:11.86 ID:FUi24cxt0.net] keyとしてpointerを指定したmapがpointeeで正しくソートできるように 3番目のテンプレート引数にpointerを剥がして比較するless演算子を 以下のように渡します g++ではm1は-std=c++17では不可ですが-std=c++20だと通ります m1にはcomparatorの型しか情報を渡しておらず m1は実装に関しては何も知らないはずなのですが 正しくpointeeでソートします なぜ? #include <iostream> #include <memory> #include <map> using namespace std; int main () { using Ptr = shared_ptr <int>; auto comparator ([] (const Ptr &lhs, const Ptr &rhs) {return *lhs < *rhs;}); using Map = map <Ptr, int, decltype (comparator)>; // Map m0 (comparator); // -std=c++17と-std=c++20で可 Map m1; // -std=c++17で不可, -std=c++20で可 m1.insert (make_pair (make_shared <int> (2), 2)); m1.insert (make_pair (make_shared <int> (1), 1)); m1.insert (make_pair (make_shared <int> (3), 3)); for (const Map::value_type &key_value: m1) cout << key_value.first << ' ' << key_value.second << '\n'; return 0; } 718 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 22:04:34.09 ID:qOIMmk+U0.net] >>697 C++20でキャプチャ指定のないラムダ式がデフォルトコンストラクタを持つようになったからかな https://ja.cppreference.com/w/cpp/language/lambda 719 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 22:11:52.14 ID:FUi24cxt0.net] >>698 なるほどー! 720 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 22:27:14.40 ID:FUi24cxt0.net] 納得しちゃダメだった ラムダ式の型は実装ごとに異なるみたいですね 以下__cxa_demangleがg++依存だけども #include <iostream> #include <memory> using namespace std; namespace abi { extern "C" {char *__cxa_demangle (const char* __mangled_name, char* __output_buffer, size_t* __length, int* __status);} } string name_of (const type_info &p) { int status (0); char *tmp (abi::__cxa_demangle (p.name (), 0, 0, &status)); string result (tmp); free (tmp); return result; } int main () { using Ptr = shared_ptr <int>; auto c0 ([] (const Ptr &lhs, const Ptr &rhs) {return *lhs < *rhs;}); auto c1 ([] (const Ptr &lhs, const Ptr &rhs) {return *lhs > *rhs;}); cout << (typeid (c0) == typeid (c1)) << '\n'; cout << name_of (typeid (c0)) << '\n' << name_of (typeid (c1)) << '\n'; return 0; } $ g++ -std=c++20 test.cpp $ ./a.out 721 名前： 0 main::{lambda(std::shared_ptr<int> const&, std::shared_ptr<int> const&)#1} main::{lambda(std::shared_ptr<int> const&, std::shared_ptr<int> const&)#2} [] [ここ壊れてます] 722 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 23:32:00.27 ID:vjOTFb3s0.net] >>697 > m1にはcomparatorの型しか情報を渡しておらず > m1は実装に関しては何も知らないはずなのですが ここが思い込みかと。 ラムダ式のクラス型に比較関数が含まれてて、その内容もインスタンスに依存しないし、 比較方法は十分伝わってるから問題ないということで何も不思議じゃないと思う。 723 名前：デフォルトの名無しさん [2022/12/13(火) 23:43:34.19 ID:FUi24cxt0.net] >>701 はい ラムダ式の型というものを理解していませんでした 型で実装を伝えることができるのは 関数ポインタと大きく異なっていて面白い性質ですね 724 名前：デフォルトの名無しさん mailto:sage [2022/12/13(火) 23:48:00.37 ID:FUi24cxt0.net] 関数ポインタと書きましたが 関数オブジェクトとの相似で考えると不思議じゃないですね 関数オブジェクトも型で実装の情報を渡しますから 失礼しました 725 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 08:35:41.62 ID:YVPbaJHSM.net] >>687 c++のunorderd_/(ordered_)は要素をキーにしてコレクションがソート済みになるかどうかを意味してると考えれば 全然違うよ。標準くらい読みなよ。 Associative containersとUnordered associative containerの本質的な違いはキーの定義。 Associative containersのキーは順序で比較可能でなくてはならず、Unordered associative containerは同値で判定可能でなくてはならない。 ついでに言うと、配列は(記憶に間違いなければ)直接メモリ番地で指定できなきゃならなくて、キー(みたいなもの)も(正)整数でなくてはならなかったはず。 726 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 08:45:51.73 ID:MH9vv9Il0.net] 配列の添字がキーだと思ってる人と 配列の中身がキーだと思ってる人 とじゃ会話が成り立たない 実際はどちらもキーではない 727 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 09:11:41.03 ID:F4iAWC8Wd.net] ねえパパ、バカって何？ 簡単なことを難しく言う人のことだよ う～ん、よくわかんないや 728 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 09:19:31.03 ID:0zkFeBrgd.net] 標準の話をするならvectorは連想配列じゃないしorderとか考えるものでもない 729 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 09:39:28.51 ID:iS/QLVofa.net] vectorで添字アクセスするのはなんか違う 730 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 09:55:06.54 ID:fk0KXlHdM.net] >>同値で判定可能 同値「かどうか」判定可能じゃないの？ >>配列は直接メモリ番地で〜 意味不明 731 名前：デフォルトの名無しさん (ｽｯﾌﾟ Sd7f-exKU) mailto:sage [2022/12/14(水) 10:35:37.85 ID:Y6rgBuPWd.net] 定義もせずに真偽を議論しようとするアホ 732 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 11:33:30.37 ID:ZSc/wamY0.net] >>709 >同値「かどうか」判定可能じゃないの？ 意味不明。 厳密に言うなら、Unordered associative containerが要求しているのはa == b a != b。 同値「かどうか」とか曖昧な突っ込みで何やりたいの？ 733 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 12:05:38.08 ID:apgWSyiy0.net] >>704 なるほどだいたい理解した つまり最初の話に戻るなら unordered_multivector というものを考えた場合、格納する要素を a == b と a != b が定義されているものに限定して、 最悪の実装を考えると要素の格納方法は vector そのもので良くて要素のサーチは先頭からリニアに a == b をチェックしていくことになり、 unordered_vector ならば要素格納時に a == b なものを除外すればよいというわけだね 734 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 12:13:00.02 ID:Y6rgBuPWd.net] (使い所が無い)新たなコンテナを考えるスレじゃないと思う 当然Perlのスレでもない 735 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 12:23:38.93 ID:Y6rgBuPWd.net] C++の配列がordered, unorderedどちらの分類に近いかなら キーが配列の添字 ==> ordered キーが配列の中身 ==> unordered 736 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 12:29:53.77 ID:Y6rgBuPWd.net] >>712 同じ値を除外する必要は無い 集合と違って配列は同じ値を許すのが普通 737 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 12:39:11.82 ID:14xvhmEyM.net] >>712 >>705 中身とキー(みたいなもの。インデックス・添字)は別物。 あと、標準だと The elements of a 738 名前：vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size(). だから、vector にunorderとかmultiとか考えても意味がない。混乱の元だからやめたほうがいい。 [] [ここ壊れてます] 739 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 13:40:10.14 ID:Y6rgBuPWd.net] setはキーも中身も同じ 740 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 13:44:24.99 ID:F4iAWC8Wd.net] ハッシュの配列はハッシュではない 741 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 13:52:25.03 ID:Y6rgBuPWd.net] >>716 vectorのキーはuniqueでordered vectorの中身はmultiでunordered 考えるまでもなく自明 742 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 14:28:12.41 ID:0zkFeBrgd.net] vectorにinsertがある 添字はkeyではなくindexでしかない 何にとってorderedであるかはプログラマーに委ねられている 743 名前：デフォルトの名無しさん (ｽｯﾌﾟ Sd7f-exKU) mailto:sage [2022/12/14(水) 16:26:53.57 ID:Y6rgBuPWd.net] 訂正 vectorの添字はuniqueでordered vectorの中身はmultiでunordered 744 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 17:18:36.72 ID:qZt9MbKWM.net] >>711 いや「同値で判定可能」って日本語として意味通ってないじゃん 取れる揚げ足を作った奴が悪いよ 「厳密に言うなら〜が要求しているのは a==b a!=b」も全然厳密じゃないじゃん a, b が何なのかも書いてないし、operator== と operator!= が定義さえされてればいいのか (a==b) ^ (a|=b) が true である必要まであるのかもその書き方だと分からない 745 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 17:36:27.63 ID:Y6rgBuPWd.net] ordered ≠ 全順序 == : 同値関係ではない 746 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 17:42:08.99 ID:Y6rgBuPWd.net] == が同値関係であるとは a == a a == b ⇒ b == a a == b, b == c ⇒ a == c 747 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 17:58:56.90 ID:ekFaWlb/M.net] >>697 >m1は実装に関しては何も知らないはずなのですが >正しくpointeeでソートします なぜ? 結論から言うと、ラムダ式は 関数呼び出し演算子 operator()() を 持った名前なし functor に対応していて、「デフォルト値」で構築 しても機能を果たすから。 [詳細] ラムダ式は、名前なし functor で、関数呼び出し演算子 operator()() を持った クラスに対応している。いまの場合、 auto comparator ([] (const Ptr &lhs, const Ptr &rhs) {return *lhs < *rhs;}); は、 class SomeFunctor { public: 　bool operator()(const Ptr &lhs, const Ptr &rhs) {return *lhs < *rhs;} }; に対応していて、 SomeFunctor cmp{}; で SomeFunctor のオブジェクトを作ってから、 bool b = cmp(lhs, rhs); とすると比較できる。 故に map クラスは SomeFunctor のオブジェクトをデフォルト値で 初期化すればいいことになるから、ユーザーが SomeFunctor の初期値 を渡さなくて良い。 実際に、mapクラスは、デフォルト値で初期化した SomeFunctor のオブジェクトを 基本クラスのメンバ変数に(実質的に)持っている。 748 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 18:01:30.49 ID:ekFaWlb/M.net] >>696 setクラスは常に大小順に順序を整列し続ける集合としては最高レベルに高速。 検索も挿入もO(N・log N) 749 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 18:13:49.08 ID:ekFaWlb/M.net] >>704 いや、ordered_が付かないmapやsetは、順序で並び替えることも定義の一部になっていて、 範囲forで巡ると、挿入した順序ではなく、比較関数で比較した結果に基いてソートされた順序になる。 https://stackoverflow.com/questions/7648756/is-the-order-of-iterating-through-stdmap-known-and-guaranteed-by-the-standard Yes, that's guaranteed. Moreover, *begin() gives you the smallest C++ ・std::map is a sorted associative container https://stackoverflow.com/questions/11274978/are-c-stdmapstring-string-ordered are STL maps ordered? Yes, a std::map<K,V> is ordered based on the key, K, using std::less<K> to compare objects, by default. So if I iterate over it, it will iterate with the first insert string first? No. It will iterate based on the sorted order, not the order that you inserted elements. In the case of std::string, it sorts in lexicographic order (alphabetic order). If you want to iterate based on the insertion order, you're better off using a sequence container, such as a std::vector or a std::list. 750 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 18:15:48.90 ID:ekFaWlb/M.net] >>727 誤: いや、ordered_が付かないmapやsetは、順序で並び替えることも定義の一部になっていて、 正: いや、unordered_が付かないmapやsetは、順序で並び替えることも定義の一部になっていて、 751 名前：デフォルトの名無しさん mailto:sage [2022/12/14(水) 18:16:04.80 ID:Y6rgBuPWd.net] >>726 つまり>>696

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef