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

1 名前：858 [2007/12/24(月) 03:41:59 ] C++標準ライブラリの一つ、STLについて。 前スレ 【C++】STL（Standard Template Library）相談室 7 pc11.2ch.net/test/read.cgi/tech/1185986999/ 過去ログ・リンク・書籍紹介は >>2 以降 67 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 15:49:19 ] STLじゃないけど #include <cassert> #include <pstade/oven/equals.hpp> #include <pstade/oven/uniqued.hpp> #include <pstade/oven/merged.hpp> #include <pstade/oven/initial_values.hpp> #include <vector> int main() {   using namespace::pstade::oven;   using namespace std;   vector<int> A = initial_values(1,2,3,4,5,6,7,8,9,10);   vector<int> B = initial_values(4,5,6);   assert( equals(A,A|merged(B)|uniqued) ); } こんな感じでいちいちeraseだの使わずに書きたい気分 68 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 16:45:30 ] >>65だけど あのぉーすみませんが、pstadeってなんっすか？ boostライブラリィの一種？ 69 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 17:19:44 ] p_stadeさんの作ったC++ライブラリ 70 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 17:37:06 ] かなりマニアティックなものなんですか？ 解答が無かったんで、今自力でtemplate作ったけど、速度がでねぇ〜 参ってるんだよね、コンテナ二つがそれぞれ500件と5000件で先の要件を満たす ようにすると、PCが1,2秒固まるんだよね p_stadeさんの作ったC++ライブラリって速度速いの？ template < typename ForwardIterator > ForwardIterator to_unique( ForwardIterator lhs, ForwardIterator rhs ) { 　　ForwardIterator result = lhs; 　　for( ForwardIterator it = lhs; it != rhs; ++it ){ 　　　　if( std::find( lhs, result, *it ) == result ){ 　　　　　　*result++ = *it; 　　　　} 　　} 　　resulturn result; } 71 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 18:38:00 ] sort→unique→eraseじゃないの。これが遅いからどうにかしたいって話か？ 72 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 18:54:26 ] >>70は >>65の件 73 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 20:01:07 ] 俺の環境(athlon64 3000+,gcc4.1.2,linux2.6 x86)ではstlのを1とするとovenは10、>>70のは40ぐらいの時間だった libstdc++でのuniqueの実装はadjacent_findで先頭部分で既にuniqueになってるものを飛ばし あとはuniqueになっている部分の末尾と比較しながら uniqueであるなら末尾の次にコピー、そうでないなら無視といった具合に イテレータが進んでいくだけってシンプルなものだったから、それと比較したらまぁそんなもんかとはおもうけど 2.3秒かかるってのはstd::vectorのreserve()をせずにどんどん突っ込んだとかそういう要因の方がでかそう 74 名前：デフォルトの名無しさん mailto:sage [2008/01/01(火) 18:56:28 ] p_stade（笑） 75 名前：デフォルトの名無しさん [2008/01/02(水) 03:41:11 ] >>70 >解答が無かったんで、今自力でtemplate作ったけど、速度がでねぇ〜 for文の中でfindしてりゃそりゃ遅いだろうよw ハッシュつかえば一発じゃん。 76 名前：デフォルトの名無しさん [2008/01/02(水) 10:38:22 ] 「ハッシュ」て、ハッシュドビーフのハッシュですか？ 77 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 10:46:25 ] はい 78 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 12:04:26 ] ハッシュド、即ちハッシュキーに変換されたビーフ。 79 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 12:53:45 ] お前の話はつまらん 80 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 14:21:50 ] >>76 つまらん話のおかげでシチューを 火にかけっぱだったのを思い出した。 マジ感謝。 # 正月2日からレトルトってのもアレだが。 81 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 21:35:31 ] >>80 レトルトかよ！ 時間とれる時くらいまともな料理しろって。(実は喰い物作るのって上手なスレッド処理みたいで面白いのだ) 82 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 23:21:32 ] >>81 分かるw コンロが複数あると加熱で複数スレッドとか、火入れてる間に別の一品の下ごしらえとか。 慣れてくると俺OSがマルチスレッドに最適化されてくるのが分かる。 83 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 23:53:15 ] 生活板か料理板か喪男板かダム河川板でやれ 84 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 03:33:58 ] ダム河川板とのつながりを理解できない俺は負け組み。 85 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 05:22:00 ] >>84がデッドロックしてるお… 86 名前：デフォルトの名無しさん [2008/01/03(木) 08:54:14 ] 定数を返すファンクタってありませんか？ って自分で書くのは簡単ですが， 標準があればそれを使おうと思います． 87 名前：デフォルトの名無しさん [2008/01/03(木) 09:50:18 ] >>86 質問の意味がわかりません。 88 名前：デフォルトの名無しさん [2008/01/03(木) 11:07:20 ] www.zvon.org/other/haskell/Outputprelude/const_f.html 的なやつのことだったら、自作しないと標準の範囲では存在しないはず。 それ以前にid関数もなかったはずだ。 boostは知らんので当該スレで聞いてくれ。 89 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 20:01:01 ] メイヤーズ先生の本を読んで、STLとマルチスレッドって相性悪いと言うか、 結局、期待通りの動作は、実装依存で全てのSTLの振舞いが保障されてないみたいなことが書いてあったな STLを駆使した、マルチスレッドプログラミングって、かなり精通しないと難しそうな印象を持った 90 名前：デフォルトの名無しさん [2008/01/03(木) 21:33:28 ] C++0x でスレッド関係のライブラリが標準で入るようになれば 改善されると期待してるんだけど，無理かなぁ． 91 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:09:54 ] >>89 その本ではどう動く事を期待してたの？ 92 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:36:22 ] >>その本ではどう動く事を期待してたの？ Effective STL本に書いてあるのは STLのコンテナでマルチスレッドをサポートする基準、ようするに、実装から 最大限望めることは ★複数の読み取りが安全である ★異なるコンテナへの複数の書き込みは安全である 以上で全てと書いてあるよ、ただし。「望むこと」はできるが、常に実現できるとは 限らないことに注意しなければなっらない。こうした内容を保障する実装もあり、保障しない実装もある。 とのことです、漏れ自身、STLを使ってない、マルチスレッドの実装をリファクタリング∩改造したことはあるけど、 STL∩マルチスレッドの経験ないからあんまり良く分かんないけど、なんか考えても難しそうな希ガスる。 93 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:40:27 ] >STLとマルチスレッドって相性悪いと言うか うわさではよく聞くんだけどさ・・。具体的にこの場合に絶対におかしくなる ってコードとどのSTL実装かを知ってる人っているのかな？ いまどきのLinuxとかWinでは問題ないとか勝手に思ってるんだけどさ。。 94 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:43:54 ] 続き。以前にSolarisのSTLでクラス変数をがんばってpthread_lockで 囲ってる実装を見て、なんかあぶなそうだなあと思った記憶はある。 95 名前：デフォルトの名無しさん [2008/01/03(木) 22:44:08 ] libstdc++については、"XXX MT"でgrep してみるといくつか既知のバグがあることがわかるよ。 文字列の参照カウントまわりとか。詳しくはbugzillaをどうぞ。 96 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:55:23 ] >>93 >>いまどきのLinuxとかWinでは問題ないとか勝手に思ってるんだけどさ。。 その本にも、同じようなことが書いてある マルチスレッドプログラムの作成は難しく、STLの実装が最初から完全な スレッドセーフであればと願うプログラマーは多いと また、後先逆になったけど >>具体的にこの場合に絶対におかしくなる >>ってコードとどのSTL実装かを知ってる人っているのかな？ 具体的なミューテックスを、行う際の完璧な（著者いわく）Lock方法が載ってるよ 97 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 22:59:59 ] 後、STL以外のマルチスレッドの実装方法は難しいので、それに関しては ビョーン本と、自分の書いた（メイヤーズ先生）MoreEffective C++を 読めとも書いてある 98 名前：デフォルトの名無しさん mailto:sage [2008/01/04(金) 00:14:41 ] std::stringとかがCOWな実装ならロックしててもまずいよね場合があるよね。 99 名前：デフォルトの名無しさん mailto:sage [2008/01/04(金) 00:16:52 ] そうだね。詳しくはMore Exceptional C++嫁という感じかな。 翻訳されてないけど。 100 名前：デフォルトの名無しさん [2008/01/06(日) 20:55:32 ] >>86はどうなった？ 101 名前：デフォルトの名無しさん mailto:sage [2008/01/06(日) 21:10:40 ] 日本語でおｋとなった 102 名前：デフォルトの名無しさん mailto:sage [2008/01/06(日) 22:58:34 ] これだから関数型言語のひとつも使えない連中は以下略 103 名前：デフォルトの名無しさん mailto:sage [2008/01/07(月) 02:04:14 ] >>86>>100 Boost.Lambdaのconstantは望むものと違う？ 104 名前：デフォルトの名無しさん [2008/01/10(木) 23:19:46 ] a 105 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 13:33:47 ] b 106 名前：デフォルトの名無しさん [2008/01/11(金) 14:01:47 ] 初歩的な質問で申し訳ないのですが class sample{ public: vector<int> vector_int; list<double> list_double; 〜省略〜 } というようなクラスをnew演算子で動的に生成した場合、delete演算子で解放 する際にはメンバのvectorやlistのメモリも解放されるのでしょうか。 ご教授お願いします 107 名前：デフォルトの名無しさん [2008/01/11(金) 14:11:45 ] >>106 される． 安心して使いたまえ． 108 名前：デフォルトの名無しさん [2008/01/11(金) 14:18:33 ] >>107 ご教授ありがとうございます。 また質問で恐縮なのですが関連して、メンバを vector<int> *p_vector_int とし、コンストラクタ内で動的にメモリ確保したとすると、この場合はデストラクタ内 で解放するように定義しとかなければいけないのでしょうか？ 109 名前：別人 mailto:sage [2008/01/11(金) 14:42:35 ] >>108 そのとおり、でも sample a; sample b = a;//もしくはsample b(a); これでデストラクタが呼ばれると同じポインタを複数回deleteしたりする未定義動作になるから注意してね。 110 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 14:49:55 ] >>108 コンテナをnewするなんて糞みたいなことはやめたまえ。 111 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:00:28 ] >>109 >>110 ありがとうございます。 確かにコンテナをnewで確保するっていうのも変な話かも知れないです。　 動的なメモリ確保・解放っていうのがintやdoubleといったような基本的な 型でしか情報が見つからなかったので、クラスや可変長配列の場合どうなるのか、 モヤモヤしていたんですが、すっきりしました。ありがどうございました。 112 名前：デフォルトの名無しさん [2008/01/11(金) 15:05:27 ] >>108 解放忘れが気になるなら， std::auto_ptr を使うといいよ． 113 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:06:50 ] >>112 調べてみます。ありがとうございます 114 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:08:25 ] auto_ptrなんて落とし穴満載の使いづらいのを進めるなよ。 115 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:10:54 ] >>114 そこらへんは、自分で判断しますので大丈夫ですよ・・・きっとｗ 116 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:19:07 ] >>108 boost::shared_ptr (or boost::scoped_ptr) boost::shared_ptr<std::vector<int> > sp_vector_int; 117 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:24:57 ] >>111 動的確保する為のコンテナを、動的確保なんて「例」だとしても阿呆過ぎる。 118 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:30:23 ] 大量に複数のコンテナを用意する場合、コンテナのメンバ変数に メモリが圧迫されることがあるので、newするケースもあると思うがなぁ。 119 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 15:34:45 ] Container<Container<Type> > 120 名前：デフォルトの名無しさん [2008/01/11(金) 15:49:21 ] >>114 だって，boost のビルドからしろって勧めるのも気が引けるじゃないか． 121 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 16:03:12 ] >>120 いや、なるべくbestの回答をするのが親切だと思う。 122 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 16:07:43 ] boost::shared_ptrはboostの他のライブラリに依存しない設計方針らしい 123 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 16:13:54 ] ビルドが必要なのは実装依存のコンポーネントだな。 thread関連とかasio（まだ無いが）とか。 shared_ptrなんぞバイナリー落としてインストールするだけだ。 124 名前：デフォルトの名無しさん [2008/01/11(金) 17:24:46 ] >>123 それを言うならヘッダファイルジャマイカ？ 125 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 18:09:22 ] C++相談室どこいった？ 126 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 18:15:35 ] 落ちた 127 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 18:23:18 ] 996レスくらいだっけ? ぎりぎりで落ちたよね。 128 名前：デフォルトの名無しさん [2008/01/11(金) 18:31:41 ] イテレータって何ですか？ 129 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 19:03:45 ] >>124 ヘッダもだけどライブラリじゃなくてか？ 130 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 19:06:44 ] shared_ptrはもう導入しないでどうするという感じだな 天才が作ってるうえアフォな質問にも丁寧に答えてくれるしな boostの問題はライブラリによってサポートに差があることかな 131 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 19:18:34 ] >>130 次期 C++ で導入されるよ 132 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 20:05:28 ] TR1に入ってるものは全部C++0xで標準に入るんだよな。 shared_ptr weak_ptr bind function mem_fn type_traits... 133 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 20:09:01 ] regex とか random とか tuple とかも入るよ。 んで、auto_ptr は deprecated になる。 134 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 21:01:32 ] >>117 まぁ　そうですね。clear()呼べば済む話ですもんね お騒がせしました。 135 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 21:06:37 ] auto_ptr、deprecatedになるのかｗ ｶﾜｲｿｽ strstreamみたいな感じか 136 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 21:16:13 ] 破壊的だと使い勝手悪いしなあ。 137 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 21:30:29 ] コンテナに入れられないのがよほど致命的なんだろ。 138 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 21:32:59 ] 致命的過ぎるよなー、それ。 139 名前：デフォルトの名無しさん [2008/01/11(金) 22:07:12 ] >>129 いやぁ，shared_ptr だけならヘッダファイルだけ もってくればつかえるとオモタ． 140 名前：デフォルトの名無しさん [2008/01/11(金) 22:08:03 ] で auto_ptr の直接の代わりは scoped_ptr ？ 141 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 22:28:42 ] そんなもん使わずに shared_ptr 使えって事だ。 142 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 23:06:56 ] auto_ptrはreleaseできるのが地味に便利 143 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 23:09:13 ] 参照カウンタのオーバーヘッドを気にしてしまう人もいるんじゃないか　たぶん 144 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 23:16:19 ] boost::ptr_vectorは地味に便利だ 145 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 23:16:32 ] unique_ptrが楽しみ 146 名前：デフォルトの名無しさん mailto:sage [2008/01/11(金) 23:24:31 ] 参照カウンタ込みで new できるとオーバーヘッドも小さいんだが。 汎用的に作れないもんかね。 147 名前：デフォルトの名無しさん mailto:sage [2008/01/12(土) 00:04:47 ] >>146 intrusive_ptrではだめなの？ 148 名前：デフォルトの名無しさん mailto:sage [2008/01/12(土) 00:13:08 ] >>147 使うために色々と必要な事があるからなあ。 149 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 20:04:36 ] multimapのいくつかの要素を述語を使って消去したいのですが 何か良い方法はありますか？ bool pred(pair<int, int> v) { return v.first == 3 && v.second == 'c'; } int main(int argc, char* argv[]) { multimap<int, char> m; m.insert(make_pair(1,'a')); m.insert(make_pair(2,'b')); m.insert(make_pair(3,'c')); // 消去したい m.insert(make_pair(3,'c')); // 消去したい m.insert(make_pair(3,'d')); m.insert(make_pair(4,'d')); m.erase(???); return 0; } 環境はVC8です。 150 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 20:05:36 ] 149です。 bool pred(pair<int, int> v) のところは bool pred(pair<int, char> v) の間違いでした。 お願いします。 151 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 20:14:10 ] イテレータとfor_eachじゃね？ 152 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 20:38:42 ] >>151 Effective STL Item9 や JosuttisのSTL本にも載ってるけど こんな感じだろうか。 bool pred(const pair<int, char>& v) { 　return v.first == 3 && v.second == 'c'; } for(multimap<int, char>::iterator it = m.begin(); it != m.end(); ) { 　if( pred(*it) ) { 　　m.erase(it++); 　} 　else { 　　++it; 　} } 試してはいない。 153 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 20:52:44 ] >>152 begin()とend()じゃなくて、lower_bound()とupper_bound()の方がいいと思う。 154 名前：149 mailto:sage [2008/01/13(日) 20:56:22 ] >>152 お示しの方法でうまくいきました。 >151,152 ありがとうございました。 155 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 21:39:07 ] >>152 折角mapなのに全検索は勿体無くねぇ？ 156 名前：149 mailto:sage [2008/01/13(日) 21:47:11 ] >>153 lower_bound()とupper_bound() にするのは速度的な問題でしょうか？ しかし、キーを二回余分に渡すのもちょっと面倒ですね。 >>152 一旦キーでマッチしたものを、すべてシーケンスコンテナに入れて そこからさらに絞り込むっていう方法も考えていたんですが 今、私が書いているコードで使う要素数が多くても3個ほどなので あまり変わらないような気がしました。 要素が多いとまた変わってくるかもしれません。 157 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 22:04:28 ] >>153　>>155 確かに。multimapだった。 equal_range()でイテレータの組を取ってもいいか。 >>156 全部の要素をlinerで舐めるのは非効率だわ。 上の人たちが言ってるやり方が効率が良い。 158 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 22:06:48 ] upper_boundとlower_boundは大小の順にソートシーケンスに 適用するアルゴリズムだ。 std::mapはデフォルトでキー順に既に要素を挿入した時点で ソートされているのでまさに効率の良い方法。 Cで言うとbinary_search()な。 159 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 22:13:59 ] >>156 KeyとValueの両方の条件で削除要素を決定するなら 汎用性を考えた場合、Linerになるけど全部舐める しかないかもな。まあ、今の場合は削除対象を絞る 条件がKeyが3に固定されてるからいいけど。 160 名前：デフォルトの名無しさん mailto:sage [2008/01/13(日) 23:31:50 ] >>156 149の通りの条件なら、Key == 3 の範囲をequal_rangeで得て、 その範囲に対して Value == 'c' を消してまわるのが速そう。平均的には、ね。 総要素数に対してequal_rangeの範囲が無視できるだけ小さいならおk。 実際に行いたい条件が149と違う場合は話が違ってくる。 Keyが単一とは限らないとか。...って、>>159に書いてあるか。 161 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 10:47:18 ] そういえばmultimapってどういう用途に使ってますか？ mapは連想配列の様に便利に使ってますが multimapという道具の使い方がいまいち思い浮かばない…。 162 名前：デフォルトの名無しさん [2008/01/14(月) 11:02:35 ] 得点が0〜100点で、名前を要素とする 同一得点は存在するからマルチ 163 名前：161 mailto:sage [2008/01/14(月) 11:07:45 ] >>162 なる。　７０点取った人を羅列その他できますね。　サンクスです 164 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 11:23:23 ] >>161 辞書 165 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 11:25:39 ] STL限定なら別だけど辞書ならbimapの方がよくね？ 166 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 11:48:17 ] 用途の話しだ 167 名前：デフォルトの名無しさん mailto:sage [2008/01/14(月) 13:18:36 ] 「ようとのはなししだ」ですか?

---

---

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

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