C++相談室 part162

**sage** (ﾜｯﾁｮｲ fbf0-ofdD) · 2022/10/31(月) 14:29:35.57

!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

2022/12/10(土) 23:34:26.52

>>631
jの型はアドレスint*やで

iと&iが別実体と解釈されてないとこの処理系の挙動は説明できないよ

2022/12/11(日) 00:20:42.40

>>632
左様かｽﾏﾝｶｯﾀorz

今神のお告げがあったが多分
>iと&iが別実体と解釈されてないとこの処理系の挙動は説明できないよ
というのは
>変数iとcout << の引数としての定数1が別実体と解釈されてないとこの処理系の挙動は説明できないよ
と考えたら>>625と同じ……

2022/12/11(日) 00:25:27.26

>>633
iが最適化後定数だろうとconst変数だろうと&iについての説明が必要だし
>>625を否定してるわけじゃないよ
>>625のうえで&iがどう処理系で実装されているのかという話

2022/12/11(日) 00:29:21.03

あーごめん>>634は取り消し

2022/12/11(日) 16:42:27.87

未定義動作ではいおしまいは思考停止では？
コンパイラの実装を考えてみるのも面白い

2022/12/11(日) 17:18:36.24

ゴミ捨て場の汚物の配置を面白がる趣味もいいけどそれで宇宙の真理を読み取ったとか言い出されても困るんだわ

2022/12/11(日) 17:28:44.13

特定のコンパイラの挙動が知りたいなら逆アセしろ
仕様が知りたいなら未定義動作

と言うだけの事だろ

2022/12/11(日) 19:27:20.67

未定義踏んで、たまたま望む動作だった場合に、それを放置するのは危険すぎる

2022/12/11(日) 19:44:01.28

前後の状況との組み合わせでも結果が変わったりするから短いコードで試しても
そのコンパイラでの挙動を知れたとは言えんし……。

2022/12/12(月) 02:44:59.90

挙動を考えるというか思想とか背景を考えるのが面白いんだよ
組み込みじゃconst領域は物理的に変えられない場合があるからって
余計な事考えちゃったけどたしかに>>625だろうなって

2022/12/12(月) 14:55:49.27

vector<string> v; の vを辞書順でソートした場合、string自体はメモリ上に
連続して並ぶが、肝心の文字列バッファは free store 上でバラバラに離れた
位置になるからキャッシュ・ミスし易くなるね。
stroustrup氏はリンクリストがキャッシュミスし易いと言って馬鹿にしていたが、
実際には動的配列(vector)でも大差は無い。
なお、リンクリストでキャッシュミスし易い典型例がソート後の全巡回ループ。
そしてその場合、vectorでもstringのようなメモリ資源ハンドルの場合は
キャッシュミスが免れない。

2022/12/12(月) 15:09:17.26

>>642
[補足]
そもそも、C++はcopyの代わりのmoveによる高速化を自慢しているが、
それが意味を持つのはstringのようにfree storeのメモリをポインタで持っている
ようなクラスである。
このご自慢のmoveが良く効くクラスTのvector<T>をソートした場合、
free storeの本当の中味のアドレスはソートされないまま。
なので、vectorを全巡回する時には、アドレスが飛びとびになり、キャッシュミス
が起き易い。

2022/12/12(月) 15:14:58.58

>>642 うんうん。リンクリストにするとキャッスミスし易さがもう少し悪化するね。

2022/12/12(月) 15:21:22.44

>>644
この例の場合、vectorをlistに変えてもあまり悪化しない。
なぜなら、stringとその文字列バッファが近接したアドレスのfree store
上にallocateされていると期待できるから。

2022/12/12(月) 15:26:03.32

>>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>のソート後の全巡回でのキャッシュミス回数は、
ほぼ同じ。

2022/12/12(月) 15:33:08.04

>>645 そうだね。悪化するのは少しだけだね。
おや？ >>642 ではバラバラに離れてキャッシュミスしやすいと言っていた文字列バッファが
リンクリストの話になると近接するのかい？不思議だねぇ。

2022/12/12(月) 15:34:37.69

典型的な用途ではsmall-string optimizationで大部分が連続になるでしょ
リンクリストにその恩恵はない

2022/12/12(月) 15:37:07.44

>>647
>おや？ >>642 ではバラバラに離れてキャッシュミスしやすいと言っていた文字列バッファが
>リンクリストの話になると近接するのかい？不思議だねぇ。
ソートしたときには、stringと対応する文字列バッファは意味論的には
くっついている。だから、「対応している」両者は隣接しているんだ。

2022/12/12(月) 15:39:41.84

>>649
[補足]
vector<string>をソートすると、stringの「箱」が新しく確保されてしまうので、
中身だけがmoveされるので、stringと対応する文字列バッファは「離れ離れになる」
list<string>をソートすると、stringはアドレスは全く変化せず、string同士の
リンクのされ方だけが変化するだけだから、stringと対応する文字列バッファは、
メモリー空間上でのアドレスの隣接を維持する。

2022/12/12(月) 15:40:54.03

>>648
それはstringだけの話。
今回はstringを例にとって話しただけで、一般のTではそんな現象は起きない。

2022/12/12(月) 15:49:40.91

>>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も全く発生せず。

2022/12/12(月) 22:25:35.59

いちいちキャッシュのことまで考えて書いたことなんかないですねえ

2022/12/12(月) 22:29:51.34

天才ですから

2022/12/12(月) 22:53:10.09

ソート済みならソートの利点を生かしたデータアクセスが主だろうからなあ
まあ最悪値を考えるかアベレージを考えるかはプログラム次第か

2022/12/12(月) 23:33:02.97

キャッシュミスが起きるとか
キャッシュに収まりきらない要素数のリンクリストを
全要素まんべんなくアクセスし続ける場合とかの話であって
そうなれば区々たるデータ構造などあんま意味を成さなさげ

2022/12/13(火) 06:29:45.20

>>656
だからお前のコードは遅いんだな

2022/12/13(火) 07:27:28.93

配列とハッシュの話を蒸し返すけど、キャッシュに退避したデータを取り出す仕組みはハッシュなので、配列も無意識・無自覚のハッシュといえる

2022/12/13(火) 07:49:45.53

トホホｗ

2022/12/13(火) 09:16:15.65

プログラムのフェッチもハッシュ、ライトもハッシュ、全てはハッシュに収束するのだ

2022/12/13(火) 09:37:04.67

ありていにいえば、他のレイヤーのデータを参照する時にハッシュを使わないと処理速度が落ちてしまうので、いたるところに速度対策でハッシュ参照が実装されているってのがFA

2022/12/13(火) 09:54:38.28

仮にunordered_vectorなるものがあったにしても、それはハッシュではない

2022/12/13(火) 10:16:13.34

それunordered_setじゃね

2022/12/13(火) 10:32:20.10

vectorはそもそもunorderdだろ
setは同じ値を格納できないのだからvectorとは違う

2022/12/13(火) 11:27:12.09

全文字列を結合したものを一括で確保して string_view を操作するのが1番パフォーマンス良さそう

2022/12/13(火) 11:41:42.04

>>665
失礼な言い方になるかもしれませんが、あなた初心者ですね
“パフォーマンス”を気にする人はそもそもC++なんて使いませんよ

2022/12/13(火) 11:47:57.08

>>666
そんなに苦手だったんか
まあこれから練習したらええよ

2022/12/13(火) 12:02:52.82

パフォーマンスを気にする人は何を使うんでしょうか

2022/12/13(火) 12:10:16.41

>>664
意味わからん
気がふれた？

2022/12/13(火) 14:54:36.88

>>669
え？w

2022/12/13(火) 16:20:37.61

>>670
vectorがunorderedとが頭おかしいのかって

2022/12/13(火) 16:36:06.63

えっ？？？

2022/12/13(火) 16:50:01.90

>>669
c++のunorderd_は挿入時に挿入要素のキーによるソートが行われず要素の格納順が実装依存なコレクションに付けられている名称だから、vectorがunoreded_かどうかと言えばyesじゃない？

2022/12/13(火) 16:51:40.89

vectorがorder性持ってたら逆に困る

2022/12/13(火) 17:09:14.84

intkeyのorderedmapってことか

2022/12/13(火) 17:26:33.26

>>675
そういう考え方もあるか
でもiteratorで途中指定してinsertしたらそれ以降のキーと要素の対応全部ずれるしmapと考えるのはどうなんだ

2022/12/13(火) 17:27:23.47

ランダムアクセスできるデータ構造でordered_だのunordered_だの定義してもこじつけでしかないし意味薄いんでは

2022/12/13(火) 18:15:32.74

てす

2022/12/13(火) 18:20:36.37

そんな事を言い出したらページアウトされてるデータの読出しになるかもしれないからディスクアクセスかもしれないだろ

2022/12/13(火) 18:25:37.11

>>673
格納順を定義しろ

2022/12/13(火) 18:29:09.49

ふざけたオレ定義はトコトン馬鹿にしてやんよ

2022/12/13(火) 18:32:26.52

>>680
iterator でたどれる順番

2022/12/13(火) 18:35:45.77

>>680
ところでこの話の発端のhashでないunorderd vector ってどんなものをイメージしてたの？

2022/12/13(火) 18:46:51.67

>>681
まずはお前の定義を書け

2022/12/13(火) 18:50:59.76

>>682
今、屋台で酒飲んでるから後でな

2022/12/13(火) 18:55:09.41

>>673
vectorは連続したメモリ領域に要素を保存し、順番に並ぶことを保証する。

そうやってc配列との互換性を保っているのは常識かと思っていたけど、仕様変わったの？

2022/12/13(火) 19:04:10.54

>>686
それで正しいと思うよ
c++のunorderd_/(ordered_)は要素をキーにしてコレクションがソート済みになるかどうかを意味してると考えれば>>673とも矛盾してないでしょ？

2022/12/13(火) 19:20:14.84

ordered_配列 ==> 勝手に中身がソートされる配列
が思い浮かぶ

2022/12/13(火) 19:23:38.37

>>688
std::multiset なんてのがあるんだな

2022/12/13(火) 19:24:14.15

そもそも、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が存在し無い。
また、故意に作ってもしょうがない。

2022/12/13(火) 19:26:29.60

ordered, unordered
が書けないヤツが多すぎ問題

2022/12/13(火) 19:27:00.39

実は全部同じ人？

2022/12/13(火) 19:28:42.74

>>688
それが大体、「set」や「multiset」に相当する。

2022/12/13(火) 19:28:56.13

巡回機能って何

2022/12/13(火) 19:37:41.71

>>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";
}
と等価だと思う。
ただし、一度も使ったことが無い。

2022/12/13(火) 20:16:44.72

>>693
全然処理量のオーダーが違う
0点

2022/12/13(火) 21:45:11.86

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;
}

2022/12/13(火) 22:04:34.09

>>697
C++20でキャプチャ指定のないラムダ式がデフォルトコンストラクタを持つようになったからかな
https://ja.cppreference.com/w/cpp/language/lambda

2022/12/13(火) 22:11:52.14

>>698
なるほどー!

2022/12/13(火) 22:27:14.40

納得しちゃダメだった
ラムダ式の型は実装ごとに異なるみたいですね
以下__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
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}

2022/12/13(火) 23:32:00.27

>>697
> m1にはcomparatorの型しか情報を渡しておらず
> m1は実装に関しては何も知らないはずなのですが
ここが思い込みかと。
ラムダ式のクラス型に比較関数が含まれてて、その内容もインスタンスに依存しないし、
比較方法は十分伝わってるから問題ないということで何も不思議じゃないと思う。

2022/12/13(火) 23:43:34.19

>>701
はい
ラムダ式の型というものを理解していませんでした
型で実装を伝えることができるのは
関数ポインタと大きく異なっていて面白い性質ですね

2022/12/13(火) 23:48:00.37

関数ポインタと書きましたが
関数オブジェクトとの相似で考えると不思議じゃないですね
関数オブジェクトも型で実装の情報を渡しますから
失礼しました

2022/12/14(水) 08:35:41.62

>>687
c++のunorderd_/(ordered_)は要素をキーにしてコレクションがソート済みになるかどうかを意味してると考えれば

全然違うよ。標準くらい読みなよ。

Associative containersとUnordered associative containerの本質的な違いはキーの定義。
Associative containersのキーは順序で比較可能でなくてはならず、Unordered associative containerは同値で判定可能でなくてはならない。
ついでに言うと、配列は(記憶に間違いなければ)直接メモリ番地で指定できなきゃならなくて、キー(みたいなもの)も(正)整数でなくてはならなかったはず。

2022/12/14(水) 08:45:51.73

配列の添字がキーだと思ってる人と
配列の中身がキーだと思ってる人
とじゃ会話が成り立たない

実際はどちらもキーではない

2022/12/14(水) 09:11:41.03

ねえパパ、バカって何？
簡単なことを難しく言う人のことだよ
う～ん、よくわかんないや

2022/12/14(水) 09:19:31.03

標準の話をするならvectorは連想配列じゃないしorderとか考えるものでもない

2022/12/14(水) 09:39:28.51

vectorで添字アクセスするのはなんか違う

2022/12/14(水) 09:55:06.54

>>同値で判定可能
同値「かどうか」判定可能じゃないの？
>>配列は直接メモリ番地で～
意味不明

2022/12/14(水) 10:35:37.85

定義もせずに真偽を議論しようとするアホ

2022/12/14(水) 11:33:30.37

>>709
>同値「かどうか」判定可能じゃないの？

意味不明。

厳密に言うなら、Unordered associative containerが要求しているのはa == b a != b。
同値「かどうか」とか曖昧な突っ込みで何やりたいの？

2022/12/14(水) 12:05:38.08

>>704
なるほどだいたい理解した
つまり最初の話に戻るなら unordered_multivector というものを考えた場合、格納する要素を a == b と a != b が定義されているものに限定して、
最悪の実装を考えると要素の格納方法は vector そのもので良くて要素のサーチは先頭からリニアに a == b をチェックしていくことになり、
unordered_vector ならば要素格納時に a == b なものを除外すればよいというわけだね

2022/12/14(水) 12:13:00.02

(使い所が無い)新たなコンテナを考えるスレじゃないと思う
当然Perlのスレでもない

2022/12/14(水) 12:23:38.93

C++の配列がordered, unorderedどちらの分類に近いかなら
キーが配列の添字 ==> ordered
キーが配列の中身 ==> unordered

2022/12/14(水) 12:29:53.77

>>712
同じ値を除外する必要は無い
集合と違って配列は同じ値を許すのが普通

2022/12/14(水) 12:39:11.82

>>712
>>705

中身とキー(みたいなもの。インデックス・添字)は別物。

あと、標準だと
The elements of a
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とか考えても意味がない。混乱の元だからやめたほうがいい。

2022/12/14(水) 13:40:10.14

setはキーも中身も同じ

2022/12/14(水) 13:44:24.99

ハッシュの配列はハッシュではない

2022/12/14(水) 13:52:25.03

>>716
vectorのキーはuniqueでordered
vectorの中身はmultiでunordered
考えるまでもなく自明

2022/12/14(水) 14:28:12.41

vectorにinsertがある
添字はkeyではなくindexでしかない
何にとってorderedであるかはプログラマーに委ねられている

2022/12/14(水) 16:26:53.57

訂正

vectorの添字はuniqueでordered
vectorの中身はmultiでunordered

2022/12/14(水) 17:18:36.72

>>711
いや「同値で判定可能」って日本語として意味通ってないじゃん
取れる揚げ足を作った奴が悪いよ
「厳密に言うなら～が要求しているのは a==b a!=b」も全然厳密じゃないじゃん
a, b が何なのかも書いてないし、operator== と operator!= が定義さえされてればいいのか (a==b) ^ (a|=b) が true である必要まであるのかもその書き方だと分からない

2022/12/14(水) 17:36:27.63

ordered ≠ 全順序
== : 同値関係ではない

2022/12/14(水) 17:42:08.99

== が同値関係であるとは

a == a
a == b ⇒ b == a
a == b, b == c ⇒ a == c

2022/12/14(水) 17:58:56.90

>>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 のオブジェクトを
基本クラスのメンバ変数に(実質的に)持っている。

2022/12/14(水) 18:01:30.49

>>696
setクラスは常に大小順に順序を整列し続ける集合としては最高レベルに高速。
検索も挿入もO(N・log N)

2022/12/14(水) 18:13:49.08

>>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.

2022/12/14(水) 18:15:48.90

>>727
誤: いや、ordered_が付かないmapやsetは、順序で並び替えることも定義の一部になっていて、
正: いや、unordered_が付かないmapやsetは、順序で並び替えることも定義の一部になっていて、

2022/12/14(水) 18:16:04.80

>>726
つまり>>696

2022/12/14(水) 18:20:54.42

>>702, 703
そういうことやね。
ラムダ式は、関数呼び出し演算子 operator()()を持ったクラスに対応していて、
その演算子が、ラムダ式の中身になっているから、テンプレート引数に
クラスの型を渡すだけで関数を渡せる。
ローカル変数をキャプチャしている場合は、どうなっているか良く知らないけども、

2022/12/14(水) 18:31:09.04

>>726
なんかさらっとオーダー間違ってるし
見逃した

最高レベルでもない
検索も挿入もO(1)なのが存在する