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

1 名前：デフォルトの名無しさん mailto:sage [2008/08/26(火) 12:01:17 ] C++標準ライブラリの一つ、STLについて。 前スレ 【C++】STL（Standard Template Library）相談室 9 pc11.2ch.net/test/read.cgi/tech/1204045410/ 過去ログ・リンク・書籍紹介は >>2 以降 267 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:12:36 ] リストの中身をAの順で並び替えて、A同士が連続したままになるように Bの順で並び替えるにはどうすればいいの？ 268 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:17:32 ] Bでソートした後 Aで安全ソート ってことか？ 269 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:52:56 ] >>267 あ1 あ2 あ3 い7 い9 う4 う5 う6 てな感じ？ 270 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 22:02:56 ] >>268 安全じゃなくて安定だろ 271 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 00:01:29 ] stable_sort 272 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 07:46:27 ] 期待通りの並てになるまでランダムに入れ替える 273 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 07:54:36 ] きたいどおりのなみて？ 274 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 08:11:40 ] >>272 ほんとにそういうアルゴリズムがあるんだよな 最初見たときギャグかと思ったが ja.wikipedia.org/wiki/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88 275 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 08:54:38 ] お前らボゴソートさんをあまりなめない方が良い。 276 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 08:54:40 ] 勿論、ギャグですが。 277 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 09:48:11 ] イテレータを保持して参照しようとするとエラーが出る erase()はしてない、参照前にpush_back()をした push_back()すると以前のイテレータが無効になるのか？ 278 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 09:52:06 ] >>277 無効になるコンテナもある。vectorとかdequeとか。 無効にならないコンテナもある。listとかmapとか。 279 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 12:25:13 ] まさにvector 場所を保持できないので必要なデータをとるときに 最初から検索しなきゃならないので不便だな listに変更する 280 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 12:29:08 ] vectorなら単にインデクスアクセスすりゃいいんじゃね？ 281 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 12:58:07 ] インデックスも保持しといたらあてにならんだろう 282 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 13:13:01 ] push_backしかしないならインデックスは変わらんだろ 283 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 15:29:09 ] インデックスはとある理由で禁書されている。 284 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 15:45:12 ] push_backしかしない場合、dequeのイテレータは無効になるが 参照やポインタは無効にならない。 微妙に便利な時もあるかもしれない。 285 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:25:56 ] push_backしかしない場合インデックスは変わらないだろうけど 参照とかポインタは変わるだろ 286 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:57:59 ] vectorならな dequeだと変わらない 287 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:25:06 ] dequeもメモリ続いてるから、足りなくなったら再確保されてアドレス変わらね？ 288 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:48:20 ] > An insert at either end of the deque invalidates all the iterators to the deque, > but has no effect on the validity of references to elements of the deque. 先頭と末尾への挿入は、イテレータは無効にするが要素への参照は無効にしない。 289 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:53:24 ] ↑は規格書の 23.2.1.3 deque modifiers のところね。 290 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:53:27 ] >>287 deque<T>の仕様をとてつもなく乱暴に要約すると、 vector<T*>みたいな構造になってる。 だから拡張されても要素自体のアドレスは変わらない。 291 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:55:25 ] ちなみに両端以外への挿入はイテレータも参照も無効になるから注意 292 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 18:37:10 ] >>287 ランダムアクセスできるだけでメモリは続いてないでしょ？ 293 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 01:17:19 ] とうとうお前らがdequeのスゴさに気づく時が来た 294 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 01:20:50 ] いや知ってて当たり前のことばかりだから 295 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 01:21:28 ] dequeの使いどころがわからん 296 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 01:29:23 ] 上から取ったり、下から取ったり、南京玉簾のような使い方をする場合、dequeほど使えるコンテナは無いぞ。 297 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 01:49:09 ] 「dequeは結構すげえんだぜ！」 っていうデータをまとめた記事（英語）が以前貼られてたね。 298 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 09:50:07 ] >>295 ・ランダムアクセスしたい ・要素を加えたり抜いたりすることがある そういうときに使う。 vectorでやると要素の追加・削除で領域を連続にするためのコストがかかる。 299 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 11:40:49 ] listはイテレータを記録すれば、ランダムアクセスできるよね？ イテレータが無効になる場合ある？ 300 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 11:48:27 ] つうかイテレータ記録すればどんなコンテナだろうとランダムアクセスできるんじゃね 301 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 12:57:27 ] 話の焦点が「イテレータを記録するモノ（コンテナなり何なり）」の機能に移るだけだよな、それ。 302 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 14:17:32 ] >299 結局 vector<list<something>::iterator> みたいなのを使うことになって vector が登場する罠 303 名前：デフォルトの名無しさん mailto:sage [2008/11/01(土) 17:56:00 ] つまり boost::multi_index の話しに 304 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 00:29:30 ] dequeのbuffer sizeってなんぼぐらい？ vc7,8は16bytes gcc3.4.4(cygwni)は512bytes vcの16って小さくね？ stringなんかはlistと同じになっちゃわないか このサイズを指定できるdequeがほしいんだが boostにあったりするかなあ 305 名前：sage mailto:sage [2008/11/02(日) 02:27:17 ] すみませんです。 listのiteratorって、 要素の追加とか削除とかして要素数が変わってしまっても、 そのまま使える保証はあるんでしょうか？ 要素の参照は保証されている思うんですが、iteratorが使えるのか。 VCでは実際動くみたいですが言語仕様的にいかがなものか。 ぜひアドバイスおねがいします。 306 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 02:48:55 ] 保証されている。アドバイスとしては仕様書読め。 307 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 02:51:24 ] 付け加えると削除したイテレータ自体は当然無効になる。 308 名前：sage [2008/11/02(日) 03:15:01 ] 早速の返答ありがとうございます！ ブラボーlist!使いやすさ爆発です。 そして以後ちゃんと仕様書読むようにします。 ありがとうございました。m(_ _)m 309 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 10:20:03 ] VC使ってる時点で言語仕様も糞も無いと理解しろ。 310 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 11:41:22 ] VC++6.0の頃じゃないんだから 今は結構まともだよ 311 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 12:10:26 ] VC++2008と仕様書との相違点はそれほど多くない。 書いてないだけで、これ以外にもあるのかもしれないがｗ msdn.microsoft.com/en-us/library/x84h5b78.aspx 312 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 13:37:16 ] むしろgccのほーが異端 313 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 13:45:55 ] それはない 314 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 14:30:28 ] MFC(笑) ATL(笑) 315 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 15:35:16 ] 急にどうした？ 316 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 15:45:00 ] dcc最強 317 名前：デフォルトの名無しさん mailto:sage [2008/11/02(日) 20:53:06 ] ecc最強 翻訳的な意味で 318 名前：デフォルトの名無しさん mailto:sage [2008/11/04(火) 13:56:24 ] BCCはどうよ C++Builder2009にはBoost標準添付だったが 319 名前：デフォルトの名無しさん mailto:sage [2008/11/04(火) 14:33:06 ] Boostって行っても1.35、しかもフルセットでなくてサブセットだけどな 320 名前：デフォルトの名無しさん [2008/11/05(水) 11:45:38 ] map<string int> hoge; mapを宣言したとき、intの領域は初期化されているんでしょうか？ されていないとしたら、 map<string,int>::iterator itr; map<string,int>::iterator itrEnd; itr = hoge.begin(); itrEnd = hoge.end(); while(itr != itrEnd){ itr->second = 0; itr++; } のように初期化すればいいんですかね？ 321 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 11:58:44 ] ちがう 322 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 12:00:49 ] なんで初期化したいんだろうか 323 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 12:12:16 ] intのほうでカウントとりたいんです 324 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 12:33:11 ] map<string int> hoge; だけだと map コンテナの中身は空っぽだから string も int もまだ領域確保されていなくて デフォルト初期化も値初期化もはじまっていない 空のコンテナの begin() と end() は無効な要素を指している 無効な要素に対するアクセスは失敗する itr->second = 0;　//　やっちゃらめぇ だと思います 325 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 12:47:23 ] 空のコンテナなら begin() == end() にならないんだっけ？ そうなるなら>>320を走らせちゃってもアクセス違反にはならないが 326 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 12:51:39 ] >>324 なるほど void func(){ map<string int> hoge; } の関数内で宣言した場合、関数が呼び出される度に　空っぽになるんでしょうか？ 327 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:04:07 ] 呼び出される度にbegin()==end()になります 328 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:16:46 ] hoge["str"] ++; とやればちゃんと0から加算されるんですか？ 329 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:17:25 ] 空のコンテナのイテレータはbegin()==end()になるって保証は 規格書に書いてあるの？ 330 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:18:24 ] >>328 vectorとmapを混同するな 331 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:19:34 ] >>328 規格ではmapにoperator[]を適用した場合もしそのキーが 存在しない時はデフォルトのコンストラクタで初期化される 決まりになってるからint()、つまり0から始まる 332 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:22:43 ] >>329 23.1.7 333 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:25:49 ] >>330 どの辺を混同していますか？ 334 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 13:25:53 ] >>332 サンクス これは目から鱗だ 335 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:23:33 ] iteratorの位置を動かすとき ++it とかするけど　it+=8 のような感じで8個分移動する方法はないの？ 336 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:26:55 ] >>335 advance 337 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:27:32 ] もちろん、ランダムアクセス可能なイテレータはit += 8で平気。 338 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:36:44 ] listなのでループで回すしかないか あと、ある値を持つコンテナを検索する関数を作ったのだが 見つからなかった場合NULLを返そう思ったら itにNULL代入できない。しかも it ==0とか演算も不可 このような場合みんなはどうしてるん？ 339 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:40:21 ] >>338 end返すのはいやなのか？ 340 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 20:47:32 ] thx、打開した 341 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 21:25:09 ] そもそもfindでいいんじゃね 342 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 21:28:59 ] stlportのhash_mapにお尻から回す奴はないですか？ 343 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 21:33:23 ] イチジク浣腸はどうだ 344 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 21:53:29 ] rbegin() rend() 345 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 22:49:22 ] 叙述関数には引数わたせないの? find_if( List.begin(), List.end(), compare( 引数１　、　引数２　) ); 346 名前：デフォルトの名無しさん mailto:sage [2008/11/05(水) 22:56:09 ] ファンクタを使えばいくらでも。 347 名前：デフォルトの名無しさん mailto:sage [2008/11/06(木) 16:02:53 ] >>342 vcのstdext::hash_mapならreverse_iteratorがあるぞ 348 名前：デフォルトの名無しさん mailto:sage [2008/11/07(金) 00:51:20 ] VC2008とSTLｐらすか5.1.7ですけど _STLP_USE_STATIC_LIBを指定すると ↓と言われてリンクできません。 ファイル 'stlportstld_statix.5.1.lib' を開くことができません。 stlportstld_static.5.1.libならあるんですけど。バグですか？ 349 名前：デフォルトの名無しさん mailto:sage [2008/11/07(金) 01:02:22 ] ren stlportstld_static.5.1.lib stlportstld_statix.5.1.lib 350 名前：デフォルトの名無しさん mailto:sage [2008/11/07(金) 01:12:47 ] #define _STLP_NEW_PLATFORM_SDK 1 351 名前：デフォルトの名無しさん [2008/11/08(土) 12:18:23 ] VB6からVC++2005にプログラムを移植してるんですが、 下記の処理がVB版に比べてVC++版では50倍ほど時間がかかりました。 1から順に使われていないID番号を探すアルゴリズムで、内容は全く同じですが、なぜでしょうか？ m_itemは構造体配列で、要素数は600個程度です。 VC++のstd::vectorの実装はクソすぎなんでしょうか？ ■VBの処理 Dim i As Long, j As Long For i = 1 To 65535 　For j = 0 To m_item_num - 1 　　　 If m_item(j).id = i Then Exit For 　Next 　 If j = m_item_num Then 　　　get_new_item_id = i 　　　Exit Function 　End If Next ■VC++の処理 size_t i, j; for( i= 1; i< 0xFFFF; i++ ){ 　for( j= 0; j< m_item.size(); j++ ) 　　　if( m_item[j].id == i )　　break; 　if( j == m_item.size() )　　return i; } 352 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 12:36:59 ] >>351 const size = m_item.size(); for(j = 0; j < size; ... キミのままだと、jのループ後とにm_item.size()関数が評価される。 353 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 12:47:16 ] VC2005だとm_item[j]が毎回範囲チェックされてる vector使う前に #define _SECURE_SCL 0を入れると良い感じらしい あと、まさかとは思うけどDebug版じゃなくて Release版で実行してないとかはないよね？ 354 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 12:58:48 ] そもそもループを1重に直したら（VBでもC++でも）もっと速くなると思う。 355 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 12:59:39 ] setでも使えばいいのに、とも思った 356 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 13:01:24 ] VBは知らないけど、C++のただの配列とvectorとでも50倍も差はないから、なんか他の要因で遅くなってると思われ。 357 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 13:02:15 ] あーごめんそれは無理か 358 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:00:46 ] 終了条件おかしくないか？ 359 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:07:46 ] 351ですが、 >>352が主な原因だったようです。>>353でも多少改善しました。 二重ループをやめて、qsort()でもしてから一重ループで探すというのもいいかもしれませんが、 アルゴリズムを変更しないとVBより遅くなるというのは腑に落ちませんね。 ベクターは使い方次第でパフォーマンスに劇的に影響するようで、なんか怖いです。 360 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:24:53 ] VC2008のvectorで if (int i = 0; i < tbl.size(); i++) tbl[i] ・・・ みたいな使い方と、 配列で、 if (int i = 0; i < TBL_SIZE; i++) tbl[i] ・・・ みたいな使い方をした場合、 Debugビルドで最適化なしだと数十倍の差で、Releaseビルドで、最適化ありだと、二倍程度の差だった。 361 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:26:01 ] このスレ的にはiterator使おうぜ 362 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:31:04 ] >>359 VB知らないんだけど、この場合のm_item_numってなに？ それ次第では、そもそも「内容は全く同じ」という認識が間違ってたことに。 363 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:35:47 ] VBとコードが違わないか？ >for( i= 1; i< 0xFFFF; i++ ){ for( i= 1; i<= 0xFFFF; i++ ){ 調べてる要素が違ってるなら50倍違ってもおかしくはないけど。 あとは計測時間が短すぎて時間を計ってるタイマーの精度の違いが出てるとか とりあえず>>351のコードをReleaseビルド&_SECURE_SCLでコンパイルしてVBより50倍も遅いなんてことあり得ないだろ。 364 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 14:53:51 ] >359 ちゃんと最適化かけたか？ 365 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 15:06:10 ] STLがVBに負けるなんて悔しい　ビクンビクン 366 名前：３５１ mailto:sage [2008/11/08(土) 15:08:04 ] すみません。デバッグビルドになってたようです＞＜ なんかデバッグなしにしたり最適化とかするとエラーが出てコンパイルできなかったので、何となく諦めてました。 >>359をやった上で最適化まですると、VBより速くなりました。 めでたしめでたし。 367 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 15:10:02 ] しね

---

---

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

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