【C++】STL（Standard Template Library）相談室 8

【C++】STL（Standard ..

654:デフォルトの名無しさん
08/02/09 19:50:38
>>653
TemplateならあるがSTLの本なんて書いてたっけ？

655:デフォルトの名無しさん
08/02/09 20:56:21
お前ら日本語でしゃべれ

656:デフォルトの名無しさん
08/02/10 02:11:51
よし今回だけだぞ

657:デフォルトの名無しさん
08/02/11 07:54:08
>643 の方法だとstd::stringには効果無いのですが、
stringの場合は明示的にメモリ解放する手段て無いのでしょうか？

658:657
08/02/11 08:06:11
すみません、VC2005のstd::stringだと、作成した
直後の状態である程度のバッファが確保されてるだけでした。

659:デフォルトの名無しさん
08/02/14 09:50:34
STLにTStringListみたいなのありましたっけ？

やっぱ、
＞std::vector <std::string>
ですか？

660:デフォルトの名無しさん
08/02/14 09:53:14
>>659
うん。 TStringList という名前だけ見ると、どちらかといえば std::list<std::string> かと。

661:デフォルトの名無しさん
08/02/14 10:03:11
有難う。

実は、vectorしか使ったことないのです。listとvectorの違いを知りたいです。

662:デフォルトの名無しさん
08/02/14 10:06:33
事故解決しました。
記述は大差ないみたいですね。
実行効率とメモリの違いみたいな。

URLﾘﾝｸ(ml.tietew.jp)

663:デフォルトの名無しさん
08/02/14 13:05:03
大差ある。

664:デフォルトの名無しさん
08/02/14 17:07:51
vector
ランダムアクセス可能。
メモリが連続している。

list
ランダムアクセスできない。
当該要素のerase以外で参照・イテレータが無効化されない。（個人的にはこれが一番重要）
任意位置への挿入・削除が定数時間。
独特な操作（spliceなど）がある。

選択する上で気をつけるのはこんなとこか？

665:デフォルトの名無しさん
08/02/14 17:20:05
なるほど、どうも有難うございます。

選択って意味では、
vector と list を間違えるより、
vector と map（←これもまだ使ったこと無いｗ）を間違えたら大変な気がしました。

666:デフォルトの名無しさん
08/02/14 18:24:34
いや、vector使うつもりでlistつかうよりmap使った方が多分マシだぞ

667:デフォルトの名無しさん
08/02/14 19:46:00
そもそもコンテナに何を求めているかによる。
連続性が重要ならlistもmapも同じくらい散々な目に遭うし、一応コンパイルが通ればいいだけなら
vectorでもmapでも問題ない。

668:デフォルトの名無しさん
08/02/14 21:59:15
ポインタつなげて線形リンクリスト作らされたことってないの？

669:デフォルトの名無しさん
08/02/14 22:17:35
>>668
標準ではないがstd::slistってのがある。

670:デフォルトの名無しさん
08/02/14 22:56:57
>>669
std::listだって線形リンクリストでしょ。双方向であるというだけで。

671:デフォルトの名無しさん
08/02/15 01:50:44
std::list って単方向じゃなかったけか？

672:デフォルトの名無しさん
08/02/15 01:53:08
いいえ。

673:デフォルトの名無しさん
08/02/15 01:53:10
あ、ごめ。双方向だった・・・
よく考えたら reverse_iterator 使えるもんね。

674:デフォルトの名無しさん
08/02/15 02:14:36
連続性が要らないなら、vectorよりdequeつかっとけって誰かえらいひとが
言ってた気がする

675:デフォルトの名無しさん
08/02/15 02:36:37
要素数が万単位にならなければlistよりvectorつかっとけって誰かえらいひとが
言ってた気がする

676:デフォルトの名無しさん
08/02/15 02:41:25
つ URLﾘﾝｸ(www.codeproject.com)

677:デフォルトの名無しさん
08/02/15 03:13:20
>>676
dequeメチャメチャ速いやん

678:デフォルトの名無しさん
08/02/15 03:35:20
むしろvectorがいらない子だろう

679:デフォルトの名無しさん
08/02/15 07:49:19
オブジェクトのサイズ/要素数が大きくない場合
listはvectorに比べてアロケーションの多さと断片化が弱点になりそうだよね

680:666
08/02/15 08:45:44
なるほど、今までvectorのみ使ってましたがmapにトライしてみます。

というより、実はネットで拾ったライブラリがmap使ってて、初期化宣言見ただけで”えっ”と思ってもう理解するの必須。

vectorの連続性って、普通の変数配列みたいにメモリがばっとコピーしても大丈夫なんですよね？
何度も文献とかで確認しましたが、結局怖くて１つ１つイテレーター参照してますが。

ところで、map使うとプライマリキーみたいなのが必須ですよね？
キーがいる場合にはピッタリですが、開発途中でやっぱキーいらね、とかなったら、
とりあえず連番で埋めとけば良いわけですかね。
その時点でvectorかlistに差し替えかな。

>>668
線形リスト勉強しました。その頃C++どころかC初心者だったため、氏にました。
で、STLって何て便利なんだろう（これで使い方さえもう少し簡単であれば）って思ってまつ。

681:デフォルトの名無しさん
08/02/15 08:46:35
　↑
＞666

は間違いで、665です。

682:デフォルトの名無しさん
08/02/15 09:04:18
mapについてそんなふうに思ってる人は始めて見たｗ
データベースみたいな複雑なものじゃなくてただの写像ですよ。
電話帳みたいな何かと何かの対応表だと思えばいい。
パフォーマンスに関してはそれを理解してからでいいと思う。

>vectorの連続性って、普通の変数配列みたいにメモリがばっとコピーしても大丈夫なんですよね？
多分大丈夫だけどやる必要ないならやらないに越したものはない。

>その時点でvectorかlistに差し替えかな。
パフォーマンス以前に用途が違うのでそのとおり。

>で、STLって何て便利なんだろう（これで使い方さえもう少し簡単であれば）って思ってまつ。
便利さを追求した結果こうなったんだろう。
ただしその上で、できるだけ簡単にはなってると思う。

683:デフォルトの名無しさん
08/02/15 09:56:51
mapなんて連想配列ですよ。awk使いの私が言うんだから間違いありません。

＞>vectorの連続性って、普通の変数配列みたいにメモリがばっとコピーしても大丈夫なんですよね？
多分じゃなくて大丈夫だけど、memcpy()などを自分で使うのはお勧めしない。潜在的なバグの原因になりかねない。
APIに渡すなどのように、必要に迫られたときに限定した方がいい。

684:デフォルトの名無しさん
08/02/15 10:18:40
boostとかにTStringListに近いものがあったりしないでしょうかね？

685:デフォルトの名無しさん
08/02/15 10:38:33
そんな無駄なものはない

686:デフォルトの名無しさん
08/02/15 10:39:27
ま、StringListクラス宣言して、中の人にmultimapすれば、自分でメソッド作るだけですか。
車輪の再開発とか言われたら嫌だから、既にあるものをなるべく使いたいです。

687:デフォルトの名無しさん
08/02/15 10:40:46
コンテナに使われている例えば連想コンテナのデータ構造（平衡二分木）とか
に詳しい人いる？

688:デフォルトの名無しさん
08/02/15 10:42:54
>686
どんなことがやりたいの？

689:686
08/02/15 10:55:33
どちらかというと、やりたいことがあるのでなくて、移植作業のためにTStringListメソッド実装。

CommaTextの入出力、iniファイルの１行処理のためのValues/Namesプロパティ、IndexOf、ファイル入出力メソッド、要素文字連結 etc..

690:デフォルトの名無しさん
08/02/15 11:11:00
>>687
ここにそれなりに詳しく書かれてるよ
Wikipedia項目ﾘﾝｸ

691:デフォルトの名無しさん
08/02/15 11:29:40
>>689
組み合わせて使えばできそうな気がする。

boost.lambda
boost.string_algo
boost.tokenizer

ファイル入出力はfstreamとalgorithm使えばよし。

692:デフォルトの名無しさん
08/02/15 12:48:59
typedef vector<int> vector_int;
を
typedef deque<int> vector_int;

に書き換えただけで、うちのソフトの体感速度が上がったｗ
処理速度アップ！ってバージョンアップ唄えるお( ^ω^)

693:デフォルトの名無しさん
08/02/15 13:02:15
＞typedef vector<int> vector_int;
＞typedef deque<int> vector_int;

kwsk
何が違うのか教えれ！

694:デフォルトの名無しさん
08/02/15 13:09:15
vectorに数万とかpush_backして再アロケートが発生しまくったんじゃないかと予想

695:デフォルトの名無しさん
08/02/15 13:11:54
その２つはメソッドは同じなの？

696:デフォルトの名無しさん
08/02/15 13:13:34
バッファの連続性が必要なくて、
確保すべきメモリ量が事前によく分からないなら、
vector より deque の方が圧倒的に効率的。

697:デフォルトの名無しさん
08/02/15 14:07:45
いままでboost::shared_ptrのコンテナにstd::listを使ってたけど
std::dequeにしたら速くなるのかな
でもスマポのコピーは時間かかりそうだな...

698:デフォルトの名無しさん
08/02/15 14:11:04
push_back のコストは list より deque の方が平均的には少ないはずだが

699:デフォルトの名無しさん
08/02/15 14:16:41
mapってシーケンシャルアクセス、かつ、入れた順番に取り出す、もできますか？

700:デフォルトの名無しさん
08/02/15 14:18:42
もっと詳しく

701:デフォルトの名無しさん
08/02/15 14:20:57
mapをbeginからendまで参照した場合、
順番は、mapに登録した順番になっててくれますか？

702:デフォルトの名無しさん
08/02/15 14:23:46
>>699
入れた順番は失われる

703:デフォルトの名無しさん
08/02/15 14:24:29
>>701
Sort Criterionによる

704:699
08/02/15 14:27:50
＞Sort Criterionによる

kwsk
ググっても出ません。

705:デフォルトの名無しさん
08/02/15 14:30:43
map<string, int> m;
m["foo"] = 0;
m["bar"] = 1;

と、

map<string, int> m;
m["bar"] = 1;
m["foo"] = 0;

で異なる挙動になるようにしたいって事だろ？
標準のmapではどうやっても不可能だと思う

706:699
08/02/15 14:35:07
え”～ショック。

つまり、並び順が保障されるのは、vectorとdequeだけですかぁ。

707:デフォルトの名無しさん
08/02/15 14:37:31
だってmapはシーケンスコンテナじゃないし

708:デフォルトの名無しさん
08/02/15 14:42:34
>>704
テンプレートパラメータかオブジェクトととして渡す
ソート基準による。

709:699
08/02/15 14:47:40
じゃ、mapはやめて、vectorします。

vectorのヘルプ見てると、pos番目の要素をとるには[pos]ではなくて、at(pos)を使えと書いてありますね。

atを使わずに[]を使ってると、dequeに置き換えが出来なくなるわけでしょうか？

710:デフォルトの名無しさん
08/02/15 14:48:47
operator[]は範囲チェックをしないけどatはする
違いはそれだけ

dequeにもoperator[]はあるから、その心配は要らない

711:デフォルトの名無しさん
08/02/15 16:19:32
ごめん。未だに
「Associative Containerじゃ駄目なんですか。じゃあSequenceにします」
が簡単に出来る場面というのが想像できない

712:デフォルトの名無しさん
08/02/15 16:29:56
線形探索しても痛くないときとか

713:デフォルトの名無しさん
08/02/15 17:07:05
>>695 >>709
>>676のリンク先にも書いてあるけど、vectorとdequeのメンバ関数の違いは
・vectorにだけある……capacity() reserve()
・dequeにだけある……push_front() pop_front()
だけ。

いずれもメモリの連続性に関わるもので、前者が「あらかじめ確保しておく」系（dequeには要らない）、
後者が「先頭要素を出し入れする」系（vectorには高コスト過ぎ）。

714:695
08/02/15 17:11:30
ｻﾝｸｽ。

STLってｷﾓｶﾜｲｲね。

715:デフォルトの名無しさん
08/02/15 17:31:49
個人的にはlistがいらない子のようなきがしてます

716:デフォルトの名無しさん
08/02/15 17:40:48
dequeにはspliceが無いだろ？

717:デフォルトの名無しさん
08/02/15 17:46:29
listはアロケータさえちゃんと作れば、本当はやれば出来る子

718:デフォルトの名無しさん
08/02/15 17:54:59
vectorはお金がかかる子。

vector（笑）

719:デフォルトの名無しさん
08/02/15 18:11:05
vectorとdequeの最大の違いは、stackコンテナでdequeがデフォルト
コンテナとして使われてることを見ればわかるね。メモリ構造の違い
によってvectorは要素を削除した場合に絶対にメモリを解放しないが
dequeはチャンクの集まりだから不要なチャンクは解放されることが多い。
（これはstandardでは求められていないらしいが）
また、reallocateの際、vectorは全ての要素を移動する必要があるが
dequeは必ずしもそうはならない。同じ要素へのアクセスではvectorの
ほうが理論的には高速。dequeはメモリ構造上indirect accessとなるから。

このくらいしか気にしてないけど、結局は要素数と実測で決めることにしてる。

720:デフォルトの名無しさん
08/02/15 23:04:47
>>706
次期C++ではinsert(iterator, value)の意味が変わって、
同順の要素の間で好きな場所に値を挿入できるようになる。
それまではstd::map<Key, std::deque<T> >でも使うしかないね。

721:デフォルトの名無しさん
08/02/15 23:27:40
>>720
へぇ。知らなかった。

これか。
URLﾘﾝｸ(www.open-std.org)

722:デフォルトの名無しさん
08/02/16 00:04:14
メタプログラミングをゴリゴリやってる奴いないの？
STLを専ら使うだけ？

723:デフォルトの名無しさん
08/02/16 00:18:21
>>722
それはboostスレで。

724:デフォルトの名無しさん
08/02/16 12:16:37
C++/TemplateMetaProgramming専用スレってないの？

725:デフォルトの名無しさん
08/02/16 12:27:05
ないね。
欲しければ立てれば？

726:デフォルトの名無しさん
08/02/16 12:42:44
過疎りそうだけどな
TMPと言ったって大概はSTL、Boostの範疇だし

727:デフォルトの名無しさん
08/02/16 12:45:39
　　　　　　　　　　　　　ｒ､ﾉVV＾ｰ八
　　　　　　　　　　　　､^':::::::::::::::::::::::＾vｨ　　　　　　　､ヽ l / ,
　　　　　　　　　　　　　 l..:.::::::::::::::::::::::::::::ｲ　　　　　　= 　　　　=
　　　　　　　　　　　 |.:::::::::::::::::::::::::::::: |　　　　　ﾆ= 724そ　-=
　　　　　　　　　　　　　 |:r￢‐--─勹:::::|　　　　　ﾆ=　なれ　=ﾆ
　　　　　　　　　　　　　　 |:} _＿　､.＿｀}f'〉ｎ＿　　 =-　らで　-=
　　、､ l | /, ,　　　　　　 ,ﾍ}´`'｀｀　`´`　|ﾉ:::|.|　　ヽ　ﾆ　.：. も　ﾆ
　.ヽ　　　　　´´, 　　　　　,ゝ|、　､, 　　 l|ヽ:ヽヽ　　}　´r　　　ヽ｀
.ヽげき 724　ﾆ. 　　／|｛/ :ヽ　-=-　./| |.|:::::| |　　|　　´/小ヽ｀
=　てっ　な　 =ﾆ　／:.:.::ヽ､　　＼二／ :| |.|:::::| |　 /
ﾆ　く. と　ら　　-=　ヽ､:.:::::::ヽ､.＿､　　＿,ﾉ/.:::::| | /|
= 　れ.盛　　　-= 　ヽ､:::::::::＼､＿＿／::.z:::::.:| |' :|
ﾆ　るり　　　=ﾆ　　　| |:::::::::::::::::::::::::::::::::::.|'.:Y′ﾄ､
/,　：　上　　ヽ､　　 | |::::::::::::::::::::::::::::::::::::_:::::_::|　 'ﾞ, .＼
　/　　　　　ヽ、　　　 | |:::::::::::::::::::::::::::::::::::.|:::::::|.ﾄ､　　　＼
　 / / 小＼　　　 r￢|ﾉ::::::::::::::::::::::::::::::::::::::::::::::::|　＼

728:デフォルトの名無しさん
08/02/16 12:46:16
724だけど、立てたぞ。
ｽﾚﾘﾝｸ(tech板)

729:デフォルトの名無しさん
08/02/16 14:03:50
>>726
甘いな

730:デフォルトの名無しさん
08/02/16 18:04:09
TMPとSTLって全然ちがくね？

731:デフォルトの名無しさん
08/02/16 18:10:33
どっちかっつーと、非 STL 部分の方が TMP っぽいな。
char_traits とか。

732:デフォルトの名無しさん
08/02/16 20:53:06
iterator_traits

733:デフォルトの名無しさん
08/02/16 22:54:48
numeric_limits

734:デフォルトの名無しさん
08/02/16 22:55:47
std::advanceもTMPっていっていいの？

735:デフォルトの名無しさん
08/02/16 23:00:21
いいんじゃね？

736:デフォルトの名無しさん
08/02/17 13:45:21
vectorやdequeってさ、変更せず読み込みだけなら複数スレッドからアクセスしても
大丈夫ですか？

737:デフォルトの名無しさん
08/02/17 13:49:27
volatileつけとけ

738:デフォルトの名無しさん
08/02/17 14:49:07
誰も書かないならvolatileいらない

739:デフォルトの名無しさん
08/02/17 15:05:58
例えばVisual C++ならここに書いてある。ほかは知らないけど。
URLﾘﾝｸ(msdn2.microsoft.com)(VS.80).aspx

740:デフォルトの名無しさん
08/02/18 14:53:30
MFCやVCLにある、StringOfChar って無いですか？
ある文字を指定個数分返してくれるメソッド。

741:デフォルトの名無しさん
08/02/18 15:08:12
string s(10, 'A');

742:デフォルトの名無しさん
08/02/18 15:09:32
thx!　>>741

あやうくfor文で回すところですた。

743:デフォルトの名無しさん
08/02/18 18:28:13
>>731
STLの中でメタプログラミングの要素があるのは
iterator_traitsとiterator_tagを使ったディスパッチくらいかな。

744:デフォルトの名無しさん
08/02/18 18:33:37
>>743
関数テンプレートのオーバーロードを利用した
ランダムアクセスとその他の振り分けか。
でもほとんど使ったことないなあ。

745:デフォルトの名無しさん
08/02/18 19:36:19
Vectorで、５番目の要素の次にデータを挿入したいときは、どう書きますか？

746:デフォルトの名無しさん
08/02/18 19:43:45
直接は使わなくても、advance とかで間接的には使ってる事ない？

747:745
08/02/18 19:44:02
既存の要素が４の場合と５の場合と、場合分けして、記述する必要があるのでしょうか？

748:デフォルトの名無しさん
08/02/18 19:46:41
既存の要素が１とかの時どうすんの？

749:デフォルトの名無しさん
08/02/18 20:07:40
>>745
std::vector なら v.insert(v.begin() + 5, value);
とかかな。要素数が最低5個は存在してないとマズイから。
v.size()で要素数調べる必要はあるか。

>>746
そういう意味では使うこともあるなあ。
本では読んだけど自分で書いたことはないな。

750:745
08/02/19 08:35:45
＞v.begin() + 5

あ、イテレーターって足し算できるんですね。
勉強になりました。

751:デフォルトの名無しさん
08/02/19 11:13:44
vectorのイテレータはランダムアクセス可能だからな。

752:745
08/02/19 11:15:48
では、vectorのイテレータだけが、＋－演算子定義されてるってことですか？
（dequeは無理と）

753:デフォルトの名無しさん
08/02/19 11:35:47
dequeもランダムアクセスイテレータなので+ - は定義されているよ

754:745
08/02/19 11:42:15
え”～、自分vectorのみ使ってるのに、それじゃvectorはやっぱり要らない子じゃん。

755:デフォルトの名無しさん
08/02/19 11:46:41
+や-ができないのは、たとえばlistとかsetの双方向イテレータ。
こいつらでは、インクリメントやデクリメントを繰り返す必要がある。
そんなときはstd::advanceなんていう関数が既に用意されている、もちろんO(N)。

vectorは、要素のメモリアドレスの連続が保障されているので、
組込の配列やmallocなんかで確保したメモリと同じように使えるという点が決定的にほかと違う。
例えばC用のAPIに渡すバッファなんかにも使える。

756:745
08/02/19 11:53:08
＞vectorは、要素のメモリアドレスの連続が保障されているので、

その通りなんですが、上レス読むと、やっぱふつーはイテレーター使えって逝われてるじゃん。

757:デフォルトの名無しさん
08/02/19 12:00:24
>>745-750

std::vector<int> v;
if (v.begin() + 5 > v.end()) v.resize(5);

を実行したら、VS2008 では Debug Assertion Failed! で落ちた。

v.end() を越えるような vector::itrator::opearator+() の結果に対して、
_SCL_SECURE_VALIDATE_RANGEマクロが範囲外を検出して例外を起こしている。
言いたいことはわかるが、融通利かせてほしい。

758:デフォルトの名無しさん
08/02/19 12:03:22
じゃ malloc的な使い方する時は、あえて
vector<int>って直書きしないとちょっと恐いな。

759:デフォルトの名無しさん
08/02/19 12:05:37
>>756
そうだから、vectorで要素へのポインタを使うのはchar*な引数に渡すなんて使い方くらいだね。

760:デフォルトの名無しさん
08/02/19 12:06:05
すまん、char*に限らず任意のT*でいいんだ。

761:デフォルトの名無しさん
08/02/19 12:13:51
>>757
組み込み配列だって要素数超える足し算は未定義動作なんだぜ。 assert() が
入ってる分ありがたいぐらいだ。

762:デフォルトの名無しさん
08/02/19 12:32:11
イテレータについて質問です。
イテレータをインクリメントするコストはコンテナによって違うと思うのですが、
STL解説サイトなどで、そのことについて触れているのをみかけません。
速度を知りたければ、実装毎にテストして計るしかないのでしょうか？

763:デフォルトの名無しさん
08/02/19 13:08:30
>>762
実際の速度(具体的な処理時間)を知りたいのならそれでいいんじゃね？
ソースやアセンブル結果を見て見当をつけても良いけど。

764:デフォルトの名無しさん
08/02/19 13:08:44
VC++2005で、
std::map<std::string,int> mp;
mp["key000"]=0;
とすると、「stringに>演算子がない」ってエラーが出るんだが、これって標準C++準拠の正しいエラーなのかな？
それともVC++2005のstringの方がおかしいのかな？

ネットで検索した時に普通にstd::stringをキーにしてるソースあったんで、問題ない書き方だとは思うんだが。

765:デフォルトの名無しさん
08/02/19 13:13:37
>>762
折角ソースがあるんだから読めばいいんじゃね?

766:デフォルトの名無しさん
08/02/19 13:18:50
>>764
標準準拠である確信は無いけど、g++-4.2.3では普通に使えた

767:デフォルトの名無しさん
08/02/19 13:31:04
>>764
VS2005でその二行を今書いているコードにペーストしてビルドしたけど、普通に通ったよ。

768:デフォルトの名無しさん
08/02/19 13:32:00
>>764
エラーメッセージを変に略さずに、そのまま晒したり Google に放り込むと、
なにか余計なことをしているのが見つかるかもしれない。

769:デフォルトの名無しさん
08/02/19 13:38:22
ヘッダincludeしてない時に出るメッセージに似てる…

770:デフォルトの名無しさん
08/02/19 13:38:42
>>764 ヘッダのincludeが足りてないのでは？

#include "stdafx.h"
#include <map>
#include <string>　←これをコメントアウトすると、「stringに>演算子がない」ってエラーが出る

int _tmain(int argc, _TCHAR* argv[])
{
std::map<std::string,int> mp;
mp["key000"]=0;

return 0;
}

771:764
08/02/19 13:45:41
早いレス㌧。
#include <string>が抜けてただけでした。
お騒がせして申し訳ないです。

772:762
08/02/19 14:07:09
>>763,765
どうもです。
ソース見て見当つけるの難しいですね(if文のコストとポインタ代入のコストの比率がどのぐらいになるのかとかさっぱりです)。
c++の制御文や演算のコストについて、本などでほとんど目にしないのですが、皆さんはどうやって勉強されました？

773:デフォルトの名無しさん
08/02/19 14:20:26
>>772
環境によって違うんだから、ある程度一般化せざるをえない本なんかで「勉強」するのは
無理だろ。

速度が要るプログラム組むときに、いろんなコードに対応するアセンブリを見て経験的に
身に付けるのがいいんじゃね？

環境が変われば結果が変わるということにも気をつけないといけない。

774:762
08/02/19 14:47:14
>>773
なるほど。
経験的に身につけていくしかないですか。
速度見積もるのに技術がいる上、環境で変わることを考えると、
速度はあまり気にせず、プロファイリングしてからボトルネックとなっている部分だけ考えるのがいいんでしょうね。

775:デフォルトの名無しさん
08/02/19 14:55:08
ばかすぎる

776:デフォルトの名無しさん
08/02/19 15:00:48
自己卑下ですか？

777:デフォルトの名無しさん
08/02/19 16:31:26
スパコンやx86-64のSSE2最適化の場合はvectorを使って、ベクトル化させたい場所はポインタに変換してる。
iteratorなんか使うと最適化してくれないし。

778:デフォルトの名無しさん
08/02/19 16:34:19
>>772
まあ、こういう細かい部分を気にするのは悪いことじゃないよね。
でもそれはC++の勉強ではなくて、ターゲット環境のしくみを先に勉強した方が良いよ。
CPUがC++で作ったコードをどう処理するのか、とかさ。
昔みたいにクロック数を数えれば分かるような簡単な時代じゃないけど、
その疑問に答えるためには、結局そのあたりの知識が必要だから。

779:デフォルトの名無しさん
08/02/19 17:38:29
スパコンでどんなソフト作ってんの？

780:デフォルトの名無しさん
08/02/19 17:59:00
>>777
やっぱり、本物の数値演算には valarray は使い物になりませんか？

781:デフォルトの名無しさん
08/02/19 18:00:28
下手にC++で書くよりMatlabで書いた方が早い

782:デフォルトの名無しさん
08/02/19 19:57:54
>>774
理論的な計算量のオーダーだけは気にしておいた方がいい。
O(N^2)の処理をやっている場所やO(N)の処理を繰り返す場所があったら
適切なコンテナやアルゴリズムを選定することを考えるべき。
結果的にはmapやsetを使うよりvectorを毎回検索、ソートした方が
速いというケースはあるけど、チューニングする以前のエイヤッと決める段階では、
理論的に速いアルゴリズムを選んでおいた方が無難。

783:デフォルトの名無しさん
08/02/19 21:41:57
>>780
つーか、C++自体が使い物にならなったりする。
ヌパコン屋はFortranしか本気でコンパイラを使ってない。

784:デフォルトの名無しさん
08/02/19 21:42:40
>>783
×使ってない
○作ってない

785:デフォルトの名無しさん
08/02/19 21:45:54
スパコンは並列化がキモだから、
並列化コンパイラの作りやすい Fortran を作りたがるのかもね。
言語仕様も単純で作りやすいし。

786:デフォルトの名無しさん
08/02/19 22:00:50
質問です。
vectorのイテレータが有効なイテレータかどうか調べる方法を教えてください。

787:デフォルトの名無しさん
08/02/19 22:04:23
質問です。
ポインタが有効なポインタかどうか調べる方法を教えてください。

と同じく、ありません。

788:785
08/02/19 22:30:42
>>787
わかりました。
ありがとうございます。

789:デフォルトの名無しさん
08/02/19 22:34:26
有効なポインタの全てと等しくならなければ有効・・・かも。
大小比較演算子使えるなら簡単になる。
当然、親となる配列が固定されていないと無理だが。
でも、こういうことしていいのかは微妙。
有効に見えるけど、指してる所が違うとかありうるし。

790:786
08/02/19 22:40:03
vec.begin() < itr && itr < vec.end()

こんな感じでやっていたのですがこれでいいのか不安でした。

791:デフォルトの名無しさん
08/02/19 22:42:01
やるなら vec.begin() <= itr かと。

それで一応どこか有効な要素は指してるかもしれないが、
「元々指していた箇所から決して動いていない」
ということまでは保証してくれない。

792:デフォルトの名無しさん
08/02/19 23:00:47
非常に厳密に言えば>>790のコードは全く意味がない
そのコードを実行してよい事前条件が、まさに itr が有効なイテレータであることなので

793:デフォルトの名無しさん
08/02/19 23:43:39
>>790
reallocateされた場合どうすんのよ？

794:デフォルトの名無しさん
08/02/19 23:55:31
なんだかんだいっても、あれだよあれ。

795:デフォルトの名無しさん
08/02/20 00:12:26
メジャーリーグに興味持ち始めた頃、STL vs ATLってのがあって何かと思ったら
セントルイス・カージナルス対アトランタ・ブレーブスだった。

796:デフォルトの名無しさん
08/02/20 09:16:18
＞vectorのイテレータが有効なイテレータかどうか調べる方法を教えてください。
＞vec.begin() < itr && itr < vec.end()

自分もこれに関する情報欲しい。
良い記述があれば教えてｷﾎﾞﾝ!

797:デフォルトの名無しさん
08/02/20 09:26:21
しかしイテレータをそんな長く持ってるのって
プログラムを考え直した方がよいような

798:デフォルトの名無しさん
08/02/20 09:35:17
いや、長く持つんじゃなくて、取得した直後に調べたいんだけど。

799:デフォルトの名無しさん
08/02/20 09:36:58
*itr
で対象をproxyにしてis_valid()でも持たせたら？

800:デフォルトの名無しさん
08/02/20 09:44:22
そのis_validの実装をどうするかの話をしてるんだろ…

801:デフォルトの名無しさん
08/02/20 10:16:45
盛り上がってきますたｗ

802:デフォルトの名無しさん
08/02/20 10:25:13
>>798
本当に「取得した直後」なら、i != vec.end()でいいのでは。

803:デフォルトの名無しさん
08/02/20 10:35:54
ｻﾝｸｽ>>802
絶対あってる？保障してくれる？

804:デフォルトの名無しさん
08/02/20 11:09:57
>>803
どんな手段で取得した直後を想定しているの?

805:デフォルトの名無しさん
08/02/20 11:10:48
どれだけ力強く保証したって、しょせん名無しのレスだぜ。

806:デフォルトの名無しさん
08/02/20 11:12:20
こんなに調べる気ゼロな奴だと知ってたら、大嘘教えたのにな。

807:803
08/02/20 11:14:32
>>804
　>>745- のような使い方です。

808:デフォルトの名無しさん
08/02/20 11:16:06
>>806
本人からすると、ここで質問することだって調べる気でしょ。
そういう破壊的なことするのは良くないお( ＾ω＾)

809:デフォルトの名無しさん
08/02/20 11:20:42
答になってないぞ。
>>745に書いてあるのは「取得したあとにやりたいこと」。
質問は「どんな手段で取得した直後を想定しているのか」だ。

810:803
08/02/20 11:30:31
>>809

ですから、

vector::insertするためにはイテレーターが要りますよね？

で、item[6] としてイテレーターを取得したときに、そのイテレーターは有効なのか無効なのか、という判定。

811:デフォルトの名無しさん
08/02/20 11:51:08
>>810
イテレータを取得する前に検査すべき。
例えば、std::vector<int> foo(5); std::vector<int>::iterator it = foo + 6;の結果は鼻から悪魔。

812:デフォルトの名無しさん
08/02/20 11:54:57
>>810
item[6] ではイテレータを取得できないと思うよ
item.begin() + 6 のことか？
itemの6番目の要素が存在するなら、当然有効だし、
存在しないなら、何が返ってこようかくるまいが item.begin() + 6 を実行した時点でアウト

813:デフォルトの名無しさん
08/02/20 11:58:27
>>810

よくわからんが、こういうことか？

void foo(vector<int>& v, int index) {
vector::iterator iｔer = v.begin() + index; // この iter は有効か判断したい.
v.insert(iter, 5);
}

ならば、こう書けば良い

void foo1(vector<int>& v, int index) {
if (v.size() < index) v.resize(index); // iterが必ず有効になるように、事前にvectorを拡大する.
vector::iterator iｔer = v.begin() + index;
v.insert(iter, 5);
}

void foo2(vector<int>& v, int index) {
if (v.size() < index) throw std::invalid_argument("index が大き杉"); // 範囲外なら例外を投げる.
vector::iterator iｔer = v.begin() + index;
v.insert(iter, 5);
}

814:デフォルトの名無しさん
08/02/20 12:15:16
作った直後で無効なイテレータってあるのか？
作ること自体が違法だったり、作った後に無効になったりするのなら分かるんだが・

815:810
08/02/20 12:20:17
>>813
やりたいことは、
ある行の後に１行追加したい、
だから、foo1でできるのはできます。

でも、ある行の後に１行追加するメソッドくらい、std::vectorとかが標準で持ってて欲しいと思うお。

816:デフォルトの名無しさん
08/02/20 12:33:35
>>815
却下だな。
- 勝手に resize() するなら、途中の要素を何で埋めるか指定しないといけない。
- 挿入位置は iterator で指定するのが標準コンテナの流儀なのに、この場合だけ
インデックスで指定するのはおかしい。
- vector のメンバにしてもユーザーが実装しても効率などは変わらない。
標準で持っていたほうがいい理由が何も思いつかない。

817:デフォルトの名無しさん
08/02/20 12:35:35
>>814
作った直後のイテレータは、コンテナの中身を指しているか、end()と等値か、だよな。
だからこっちは「本当に作った直後なら、!= vector.end()との比較でいい」って言ってるのに、
この質問者、「自分の訊きたいこと」と「自分の訊いていること」を一致させられないんだよ。

818:デフォルトの名無しさん
08/02/20 12:57:08
おまえら頑張ってるが、実行効率も考えろ。
結果的に再取得したほうが良かったりして。

819:786
08/02/20 13:51:57
いろいろ勘違いしていました。
実際はイテレータじゃなくてただのインデックスでした。
0<=index<vec.size()
で十分でした。

イテレータの場合は持ってる間vectorを変更しないようにしています。

820:デフォルトの名無しさん
08/02/20 13:53:28
ｴｴｪｪｪ

821:デフォルトの名無しさん
08/02/20 14:18:16
>>819
う゛ーう゛ー

822:デフォルトの名無しさん
08/02/20 14:20:36
これは酷い釣りだ…

823:デフォルトの名無しさん
08/02/20 16:22:14
結論としてイテレーターは役立たずでOk?

824:デフォルトの名無しさん
08/02/20 16:30:10
list をイテレータなしでというのはちょっと
vector にはいらないけどさ

825:デフォルトの名無しさん
08/02/20 16:37:03
listの返したイテレータが無効になるタイミングって、
list本体が破棄された場合と、イテレータ先がeraseされた
時だけでしょうか？

826:デフォルトの名無しさん
08/02/20 16:46:18
元からC++にあった下位概念（ポインタ）が要求するメモリ構造を持っているvectorは、
後から加わった上位概念（イテレータ）を使わずとも、下位概念のやり方で各要素を見ていける、
だから「必須ではない」・・・という意味では、無くてもいいかもね。

実際には、stringやlistがbegin() end()してる中、vectorだけ&vec[0]とか使ってポインタでいじるのは
えらく不自然だから、vectorもイテレータで扱ってしまうけれども。

827:デフォルトの名無しさん
08/02/20 18:04:53
>>825
合ってる(要素を消す関数はerase()以外にもあるけど)。あと標準には
list1.splice(list2);
するとlist2へのイテレータが全部無効になる、と書いてあるけど、
実際にはほぼ間違いなくlist1への有効なイテレータになる。
これは標準の方が訂正される可能性が高い。

828:デフォルトの名無しさん
08/02/20 19:40:59
>>827
返答ありがとうございます。
listに要素追加したときイテレータを保存しておいて、
それを別なコンテナでインデックス化するってな使い方を
しても大丈夫そうですね。

spliceの
＞実際にはほぼ間違いなく
ってところはちと怖いので、使用は避けときます。

829:デフォルトの名無しさん
08/02/20 21:01:56
>>827
最新のドラフトだと「移動した要素を指し続ける」と書いてあるね。

830:デフォルトの名無しさん
08/02/20 21:36:58
250. splicing invalidates iterators
Section: 23.2.3.4 [list.ops] Status: WP Submitter: Brian Parker Date: 2000-07-14

void splice(iterator position, list<T, Allocator>& x);
invalidates all iterators and references to list x.

This is unnecessary and defeats an important feature of splice. In fact, the SGI STL guarantees that iterators to x remain valid after splice.

WPってWorking Paperってなってるけど一度却下されてるんだよね。
で、最新のドラフトだとC++0xで修正されることは決定？

WP　The proposed resolution has not been accepted as a Technical Corrigendum, but the full WG21 committee has voted to apply the Defect Report's Proposed Resolution to the working paper.

831:デフォルトの名無しさん
08/02/20 21:44:24
N2461 だと次のように書いてある。

23.2.3.4 list operations

void splice(const_iterator position, list<T, Allocator>&& x);

4 Effects: Inserts the contents of x before position and x becomes empty.
Pointers and references to the moved elements of x now refer to those same elements
but as members of *this.
Iterators referring to the moved elements will continue to refer to their elements,　　　← ここ
but they now behave as iterators into *this, not into x.

832:デフォルトの名無しさん
08/02/20 21:49:02
moveの導入による影響おそるべし

833:デフォルトの名無しさん
08/02/20 21:53:24
>>831
Working Draftか。
そうなりそうだね。

834:デフォルトの名無しさん
08/02/20 22:02:47
>>832
list の splice は，標準ライブラリへの move の本格導入以前から，
auto_ptr と並ぶ標準ライブラリにおける move の代名詞だったような？
現行の規格が不必要に制限が強すぎた
(iterator の stability を保証しなかった) だけで，
move 導入とは直接関係ないんじゃないですかね？

>>831の splice の第2引数が右辺値参照型に変更されたのも
単に一時変数を渡すことができるようにしただけでしょうし．

835:デフォルトの名無しさん
08/02/20 22:05:17
rvalue reference うぜえな。。　基本仕様としては
これが一番インパクトでかいかな。

836:デフォルトの名無しさん
08/02/20 22:07:39
concept 周りが間に合えばあれも相当インパクト大きいのでは

837:デフォルトの名無しさん
08/02/20 22:07:54
今まで
const Widget operator+(Widget, Widget)
とかしてたものが
Widget&& operator+(Widget, Widget)
になるのか。

838:デフォルトの名無しさん
08/02/20 22:08:37
テンポラリオブジェクトを渡せるようになるのはいいのだが、
そのせいで左辺値参照でいい状況でもムーブが発生するのが微妙だな。

839:デフォルトの名無しさん
08/02/20 22:26:14
以下は C++0x を前提にしたレスです．スレ違いですいません．

>>837
Widget の実装と operator+ の機能によりますけれど
値で返すのと参照で返すのでは基本的に意味が違ってしまうのでは？
で， move の恩恵を受けたければ Widget を move 可能にした上で
Widget operator+(Widget, Widget)
となるのが一般的かと思います．

>>838
＞そのせいで左辺値参照でいい状況でもムーブが発生するのが微妙だな。
その微妙になる具体例ってどんなのがありますかね？

840:デフォルトの名無しさん
08/02/20 22:37:12
l1.splice(it, l2);

右辺値参照の場合
1. l2 -> x のムーブ
2. x のノードを l1 に付け替える

左辺値参照の場合
1. l2 のノードを l1 に付け替える

841:デフォルトの名無しさん
08/02/20 22:42:46
>>839
戻り値をWidgetにしてしまうと代入できてしまうので
constをつけてるんだけど、

①const Widget operator+(const Widget&, const Widget&);

②Widget&& operator+(const Widget&, const Widget&);

現在は①のようにしてるけど、C++0xからは②でいいかなと思った。
どちらも
Widget w1, w2, w3;
if( (w1 = w2) = w3 )
のようなケアレスミスをコンパイルエラーにしてくれると思ったけど、
②だと (w1 = w2) = w3 はOKになってしまうか。右辺値参照に左辺値
は代入できるか。

842:デフォルトの名無しさん
08/02/20 22:44:44
const Widget operator+(const Widget&, const Widget&);

と書いた場合、const Widget はムーブできるのか？

843:デフォルトの名無しさん
08/02/20 22:44:56
>839
>838 じゃないけど。
値渡しにした段階でコピーが発生しちゃうから、

Widget&& operator+(Widget&&, Widget&&);
Widget&& operator+(Widget&&, const Widget&);
Widget&& operator+(const Widget&, Widget&&);
Widget operator+(const Widget&, const Widget&);

頑張るんならこうなるんじゃないの？
std::string の operator+() はこうなってるが。

あと、微妙ってのは左辺値参照なら単純にアドレス渡すだけで済んだものが、ムーブ処理が発生しちゃうのが嫌ってことなんじゃないかと。
で、↑はそのためにオーバーロードしてるけど。

844:デフォルトの名無しさん
08/02/20 22:46:52
>>840
引数のl2は右辺値という前提だよね。そうするとmoveの分だけ効率が
悪くなるということかな。

845:デフォルトの名無しさん
08/02/20 22:51:32
>>842
ん？メイヤーズの本で推奨されてたから従ってる。

>>843
ドラフト見たところでは、例えば
Widget&& operator+(Widget&& lhs, const Widget&& rhs);
の場合、両方の実引数にWidgetの一時オブジェクトを
渡すとlhsとrhsは右辺値になって、両方に左辺値を渡すとlhsとrhsは
左辺値になるという理解でいい？

846:デフォルトの名無しさん
08/02/20 22:55:53
>>840
現行の list の splice の意味からすると，
splice という名前に前者の操作を overload させると混乱するのでは？
前者は最新の working draft に従えば，例えば
l1.splice(it,decltype(l2)(move_iterator(l2.begin()),move_iterator(l2.end())));
と書けると思いますけれど，これではダメなのですか？

あと，「左辺値参照の場合……」「右辺値参照の場合……」という書き方を
されていますけれど， l2 の型が右辺値参照型か左辺値参照型か，ということですか？
もしそうだとすると，l2 はそのままでは常に左辺値として扱われるので，
void splice(iterator, list<T,A>&);
と
void splice(iterator, list<T,A>&&);
があった場合には， l2 が右辺値参照型か左辺値参照型かに関わらず
常に前者が呼ばれると思います．

847:デフォルトの名無しさん
08/02/20 23:00:25
しかし void splice iterator, list<T,A>&); は存在しない

848:デフォルトの名無しさん
08/02/20 23:03:20
>>841
一時オブジェクトに対するメンバ関数呼び出しの overload は
右辺値参照型の *this への拡張が対応するかと思います．

URLﾘﾝｸ(www.open-std.org)

例えば，右辺値に対して Widget::operator=(const Widget&) を禁止したければ

class Widget{
Widget& operator=(const Widget&) & { ... }
Widget& operator=(const Widget&) && = delete;
...
}

上記のようになるかと思います．従って Effective C++ にある>>845の記述は
C++0x では deprecated になるかと思います．

849:デフォルトの名無しさん
08/02/20 23:06:33
>>842
move はそのソース (move 元) に対して破壊的操作を行うことになるので
戻り値に対して const を指定しているとその戻り値に対して
move を行うことはできなくなると思います．
Widget& Widget::operator=(const Wideget&); // copy assignment
と
Widget& Widget::operator=(Wideget&&&); // move assignment
があった場合，>>842の operator+ の戻り値に対しては
オーバーロードの優先順位を解決した結果， copy assignment が呼ばれるかと．

850:デフォルトの名無しさん
08/02/20 23:06:55
dequeとvectorの速さ比べをしてみた(gcc　3.4.5 mingw)

for(i=0; i < num; i++){
　foo += v[i];
}

みたいなの。

vectorの先頭をポインタに渡してポインタ経由でアクセス
>>>>>>vectorを[]でアクセス>>>vector をiteratorでアクセス=dequeをiteratorでアクセス
>>>>>>>(越えられない壁)>>>>>>dequeを[]でアクセス

dequeがあればvectorはいらない子みたいなカキコがあったけど、やっぱvectorはやればデキる子だよ。

851:デフォルトの名無しさん
08/02/20 23:15:29
>>843
ありがとうございます．微妙な具体例が理解できました．
これを気にするならば overload 頑張るしかないですね．

852:デフォルトの名無しさん
08/02/20 23:18:07
オーバーロードで解決は出来るけど、
沢山あると大変だね。

853:デフォルトの名無しさん
08/02/20 23:27:12
蛇足ですけれど，>>843は書かれているような「微妙な状況」の他に，
引数が一時オブジェクトで，その一時オブジェクトのバッファが
結合後の文字列を保持できる余裕がある場合に，
バッファの再確保を回避できる最適化を積極的に活用できる
というのもあるかと思います．

854:デフォルトの名無しさん
08/02/20 23:34:05
>>847
元々 splice は move (破壊的コピー) を行うという意味づけであり
右辺値と左辺値を区別する必要はなく，
void splice(iterator, list<T,A>&);
と
void splice(iterator, list<T,A>&&);
をオーバーロードする必要もないと自分は思います
(し，おっしゃるとおり working draft も今のところそうなっています)

855:デフォルトの名無しさん
08/02/20 23:35:07
>>850
vectorアクセスするのにiterator経由より[]の方が速いって謎すぎる。
何らかの理由で最適化に失敗してるか、assertが効いてるんじゃ？

856:デフォルトの名無しさん
08/02/20 23:48:29
>>855
最適化オプション何もなしだお

857:デフォルトの名無しさん
08/02/20 23:49:40
>>855
ちなみに、倍速くらい
ポインタにすると[]のさらに倍
ちなみにdequeの[]はvectorの[]の4倍遅い

858:デフォルトの名無しさん
08/02/20 23:50:03
-O2つけて測定コード毎最適化で消してしまえ。

859:デフォルトの名無しさん
08/02/20 23:50:18
あほすぎ。

860:デフォルトの名無しさん
08/02/20 23:54:00
ふつーSTLは最適化かけて実測するもんだと思ってたのだが、違うのか？

861:デフォルトの名無しさん
08/02/20 23:57:15
STL に限らず、実測は最適化かけてからやるのが普通。
最適化しない場合の影響を調べるのでもない限りは。

862:デフォルトの名無しさん
08/02/21 00:05:39
ふつー、最適化をかけるとvetor::operator[]はポインタアクセスと同じコードに
展開される。実際、gcc3.4.6 -O2ではそう。

863:デフォルトの名無しさん
08/02/21 00:24:53
dequeのメモリ構造は複数のメモリブロックから成っているので
ブロック間でindirect accessが発生するから、要素へのアクセス
とiteratorの操作はvectorより遅くなるというのが一般論。

864:デフォルトの名無しさん
08/02/21 00:35:31
>>854
ほほう。結局、
void splice(iterator pos, list<T,A>&& l2);
この場合、l2に右辺値（一時オブジェクト）を渡そうが
左辺値を渡そうが、l2は常に左辺値として扱われるという
ことだよね？この仕様変更のメリットとしては、右辺値も
渡せるということかね。

865:デフォルトの名無しさん
08/02/21 00:47:02
>>864
splice の定義内では，明示的にキャストをかけるか
std::move を使うかしないと l2 は左辺値として扱われると思います．

＞この仕様変更のメリットとしては、右辺値も渡せるということかね。
自分はそう理解していたので>>834のように書きました．
右辺値が渡せるので>>846に書いたような
l1.splice(it,decltype(l2)(move_iterator(l2.begin()),move_iterator(l2.end())));
みたいなコードも通るようになります．

866:デフォルトの名無しさん
08/02/21 00:50:32
>>865
後半は漏れの理解不足で分からんけど、アリガトン。

867:デフォルトの名無しさん
08/02/21 00:55:32
>>866
すいません．
l1.splice(it,list<int>(l2.begin(),l2.end()));
みたいなコードも通るようになるといいたかったんです．
といいますか>>846のとかこれの場合は insert で良いですね……orz

868:デフォルトの名無しさん
08/02/21 01:37:08
>>867
いえいえ。
move_iteratorとか見たことなかったので漏れの理解不足というより
知識不足だった。範囲指定のコンストラクタで一時オブジェクト
をそのまま渡すことができると。
それが、l1.insert(it, l2.begin(), l2.end());で可能だったという
こっですね。

次ページ