【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 以降 82 名前：デフォルトの名無しさん mailto:sage [2008/09/29(月) 13:56:19 ] >>73 実装の話だが、VC++のChecked Iterator有効状態だとiteratorアクセスが遅く、 vectorの単なる走査だと生ポインタ取り出してインクリメントしたほうが速くなる 結果というのをどっかで見た 83 名前：デフォルトの名無しさん mailto:sage [2008/09/29(月) 22:32:49 ] デバッグ版で速度を気にしても仕方がない 84 名前：デフォルトの名無しさん mailto:sage [2008/09/30(火) 00:08:56 ] >>82 デフォルトで安全なほうに振ってるからな それ知らずにベンチマークして「遅いｗｗｗ糞杉ｗｗｗ」 って言ってる奴マジ恥ずかしい 85 名前：デフォルトの名無しさん mailto:ｓage [2008/10/03(金) 21:16:07 ] サンプルコードに下記のコードがあったのですが解説がないので どのような動きをするのかわかりません・・。 誰か簡単に教えていただけませんか //------------------------------------------------------------ //STLの補助マクロ // // #define foreach(type,obj,i) \ for(type::iterator i=(obj).begin();(i)!=(obj).end();(i)++) #define const_foreach(type,obj,i) \ for(type::const_iterator i=(obj).begin();(i)!=(obj).end();(i)++) 86 名前：デフォルトの名無しさん mailto:sage [2008/10/03(金) 21:24:03 ] >>85 解説しろといわれてもこまるほど 簡単なというか基本的なことしかでてきてない コードなんだがなにが分からないの？ イテレータ知らないの？ 87 名前：デフォルトの名無しさん mailto:sage [2008/10/03(金) 22:10:28 ] >>85 typeにはstd::vectorとかのコンテナ型を指定する。objはそのインスタンス。iはイテレータを使ったループ変数だ。 こんな風に使う。 std::vector<int> vecx; (略). foreach(std::vector,vecx,i) { std::cout<<*i; } 88 名前：デフォルトの名無しさん [2008/10/04(土) 05:58:22 ] 今時のコンピュータ早くて 多少重い部品使っても全然平気。 89 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 09:28:46 ] C++でそんなマクロを作る意味あんの？ 90 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 11:03:46 ] マクロじゃないとできへんのや・・ 91 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 11:42:58 ] >>85のマクロだけど 「#define foreach(type,obj,i)」のtypeを無くして引数を２個だけにできますか？ 何に使うかはともかくとして、ちょっと気になった。 92 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 11:54:38 ] >>91 BOOST_FOREACHを使う。 93 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 12:06:59 ] BOOST_FOREACHもマクロなんですがｗ 94 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 12:19:19 ] でっていう 95 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 12:53:53 ] VC++なら8からfor eachが使える。 96 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 13:37:59 ] BOOST_FOR_EACHを使うとループを二重にも三重にも出来る std::vector<std::vector<int> > vec(10, std::vector<int>(10)); BOOST_FOREACH(std::vector<int>& row, vec) BOOST_FOREACH(int& i, row) i = 999; 97 名前：デフォルトの名無しさん mailto:sage [2008/10/04(土) 13:44:59 ] >>91 autoを使う 98 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 01:30:25 ] >>97 autoは別スレの話題だ typeofならギリギリ可 99 名前：デフォルトの名無しさん [2008/10/05(日) 15:35:23 ] vectorへのアクセスを速くする良い方法ってありますか？ いま、 for(vec::iterator it=vec.begin();it!=vec.end();it++) access to *it を for(int i=0, int num=vec.size(), Type *ptr=&vec[0];i<num;i++) accsess to ptr[i]; とかやっちゃってます。 100 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 15:42:29 ] >>99 BOOST_FOREACHを使うとend()がキャッシュされる分高速化されるらしい。 101 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 15:57:14 ] endをキャッシュするより >>99のように 数値変数でループ回数を制御する方が速いことが多い x86のような性能優先のCPUならどっちでも変わらないが 組み込みに使える普通のCPUだと差がつくことが多い 102 名前：99 mailto:sage [2008/10/05(日) 16:14:17 ] なるほど、最適化すればx86なら変わらないのですね。ありがとう。 ちなみに、目的としては動的に確保できる多次元配列のアクセスを速く したいんだけれども。array[][][]と同程度の速度が出たりしますか。 ・・・なんて聞いてないで自分で実験してみればいいか＾＾； BOOSTはデフォルトでビルドできないためソースを人に渡せないから、 速度の関係ないアルゴリズム検証用にしか使ってません。 103 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 16:19:22 ] BOOST_FOREACHはビルドしなくても使える 104 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 16:27:35 ] >>103 そうじゃなくてboost入れてない人がいるって話だろ 105 名前：99 mailto:sage [2008/10/05(日) 16:48:34 ] そうです。使わない人にとっては、BOOST入れるのって結構面倒ですしね。 ソース書いて、アセンブラ見てみたんだけど、一見したところ変わらないみたい。 通常、静的な多次元配列array[a][b][c]ならば、連続で並んでるのが保障 されてるから、一発で目的のアドレスを参照できるから速い。 疑問なのが、動的な多次元配列の場合、 int ***ptr ptr = new int**[a] ptr[i] = new int*[b] ptr[i][j] = new int[c] とした時、 ptr[i][j][k]にアクセスすると、ptr[i]にアクセスして、入ってる番地を見 て、更に入ってる番地を・・ってのを繰り返すけど、メモリアクセスは通常 遅いので、動的配列は遅いのだけど。 で、普通に考えてvectorも同じような多重メモリアクセスをやってるような 気がするんだけど、遅くならないのかな。 106 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 16:56:16 ] vector<vector<vector<int> > >とかなら105のと同じように遅くなるだろと思う。 107 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 16:58:03 ] 仕方がない 行毎に列の大きさを変えられる利便性とのトレードオフ 108 名前：99 mailto:sage [2008/10/05(日) 17:16:38 ] うーむ、やっぱそうですよね。ありがとうございます。 僕のケースでは大抵の場合は行毎のサイズは固定で、初期化の時から変化 しないって場合が多いので、１次元配列で確保してます。例えば画像デー タみたいに、ユーザの入力にあわせて初期化サイズが変わるみたいな状況です。 この場合、データの規則性・連続性は保障されるので、構造的には静的多 次元配列と同じパフォーマンスが出せるはずですが、最適化してくれるものですか？ もし可能なら、変数沢山のマクロから解放されてソースも読みやすくなるし、 メモリリークもしないから非常に素敵なんだけどな・・・。 109 名前：デフォルトの名無しさん mailto:sage [2008/10/05(日) 17:17:54 ] 長方形や立方体でよければ、1次元に詰め込んでv[i * x + j]とアクセスする方法が取れる。 110 名前：デフォルトの名無しさん mailto:sage [2008/10/06(月) 03:44:50 ] boost::multi_arrayもあるけどインタフェースが変態的なんだよな 結局の所自分で簡単なクラス作って使うのが無難 111 名前：デフォルトの名無しさん [2008/10/15(水) 12:18:18 ] vectorで配列を作って vectorの要素0から99までの最大値をmax_elementで求める vectorの要素100から199までの最大値をmax_elementで求める vectorの要素200から299までの最大値をmax_elementで求める 省略 という処理をしたいんですが、どのようにすればいいでしょうか？ 112 名前：デフォルトの名無しさん mailto:sage [2008/10/15(水) 12:22:41 ] a = *max_element(&v[0], &v[100]); b = *max_element(&v[100], &v[200]); c = *max_element(&v[200], &v[300]); 113 名前：デフォルトの名無しさん mailto:sage [2008/10/15(水) 12:36:31 ] 省略 114 名前：デフォルトの名無しさん [2008/10/15(水) 12:37:38 ] ありがとうございます。 それで出来るはずだと思って試していたら、他の所でミスしてましたorz。 iteratorを使って ループ文中で if(count%100){ a=*max_element(iterator,ここが分からない); } という風にiteratorを基準に、後ろ100個目までを範囲指定することを出来ませんか？ 115 名前：デフォルトの名無しさん mailto:sage [2008/10/15(水) 12:41:30 ] ランダムアクセスイテレータなら a=*max_element(iterator, iterator + 100); 116 名前：デフォルトの名無しさん mailto:sage [2008/10/15(水) 12:42:36 ] vectorなんだからランダムアクセスできるでしょ 117 名前：デフォルトの名無しさん [2008/10/15(水) 12:53:31 ] 出来ました！ありがとうございます！！ 118 名前：デフォルトの名無しさん [2008/10/19(日) 00:12:46 ] 疑問なんだけど、vectorの配列から作ったiteratorってのは、 ポインタの配列なの？ 119 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:21:37 ] 最適化の結果ポインタと同じような動作になるけど そのものじゃないはず 120 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:13:31 ] 実装によるんじゃなかった？ 単にポインタをtypedefしている実装もあれば、classにしてる実装もあるって 聞いたような気がする夢をみたかもしれない 121 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 16:43:31 ] vectorの配列から作ったiteratorって言うと、 vector<vector<hoge> >::iterator のことかい。 122 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 17:21:14 ] 俺はvector<hoge>[N]のイテレータ、つまりvector<hoge> *のことかと思った でもどっちにしても話が合わない気がする 123 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 17:24:23 ] vi->begin() とか気持ち悪いコード初めて書いたわ 124 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 17:37:42 ] 別に普通かな 125 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 18:30:23 ] ハッシュテーブルの辞書みたいなもんだろ。 126 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 18:44:13 ] まったく気持ち悪くないよ 127 名前：118 [2008/10/20(月) 09:02:02 ] >>121,122 vector<int>::iteratorみたいなもんです。書き方が悪かったですね。すみません 2Dライブラリだったらピクセルデータの配列を引数 3Dライブラリだったら座標データの配列を引数 にとる関数がありますけど、そういう関数にvectorで管理してるデータを 渡したいときは、どのようにしてますか？ 私は、vectorに入ってるデータのサイズ分の配列を作って、そいつに入れてから ライブラリの関数に渡すってことをしてたんですけど、もっとスマートな方法って ないですか？ 128 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 09:33:27 ] vectorのイテレータがポインタだという保証はない でもvectorの内容がメモリ上で連続している保証はある だからvがvector<T>なら、Tの配列を要求する関数に&v[0]を渡しても大丈夫 イテレータitに対応するポインタを渡したければ&*itのようにすればいい 129 名前：デフォルトの名無しさん [2008/10/20(月) 12:26:11 ] わかりやすい解答ありがとうございます。 vector便利過ぎる 130 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 09:58:32 ] vectorでイテレータなんか使ったこと無いな。 Win32 APIを使う場合は、配列を使わない訳にはいかないから、 何番目という数字が必要な場合が出てくるし、 配列要素アクセスでは、i < vec.size()の記述でないとおかしいから。 131 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 10:52:18 ] >>130のイテレータバージョンはたぶんこんな感じだな vectorでインデックスなんか使ったこと無いな。 algorithmを使う場合は、イテレータを使わない訳にはいかないから、 beginとendが必要な場合が出てくるし、 イテレータアクセスでは、i != vec.end()の記述でないとおかしいから。 132 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 12:22:45 ] つか、>>130 が vector で iterator 使ったことがあるかどうかなんて 地球上の誰も興味のない話を唐突にされても。 133 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 19:53:51 ] 内部でやってることは一緒じゃないの 134 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 20:01:15 ] いや、vector のイテレータとか、型が分からないと使えないしめんどいー インデックスでいいじゃんでも C++ 使うならイテレータつかったほうがいいのかなーどうしよー と迷うに迷って混在させてｇｄｇｄになってる俺みたいな人には重要な話 135 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 20:26:30 ] C配列との橋渡し的な役目もあるしね。使う人／使わない人がいるのは当然かと。 136 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 20:51:16 ] >>134 対象のvectorが見えてるのに型が判らないってどういう状況だ？ 137 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 21:01:51 ] いちいちstd::vector<foo>::iteratorと書くのが面倒だと言っているだけだと思う。 早くautoが欲しい。 138 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 21:04:22 ] どっちも似たようなものだし、いざとなれば相互に変換できるし、どうでもいい 139 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 13:30:52 ] 構文糖は重要だよ 各種LL言語が有用性を示してるじゃん 140 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 13:36:50 ] イテレータとポインタは構文糖の関係にはない 141 名前：デフォルトの名無しさん [2008/10/22(水) 19:03:29 ] >>137 typedef 一回書けば解決 142 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:04:19 ] double型 と　char型のメンバを持つ構造体をvectorにいれて、全要素入れ終わったらソートみたいにしてるんですけど、 mapとかつかったらもっと効率よくなりますか？ソートするキーはdouble型の値で、降順です。 143 名前：デフォルトの名無しさん [2008/10/22(水) 21:30:53 ] ファイルからや手からの入力ならset使えば、ソート時間はほぼ無い。 読み込んでいる間にソートされるので。 もしメモリ間の転送であっても速いとは思う 144 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:40:54 ] mapじゃなくてpairかもしれません。 pairでdouble型とchar型のメンバを作って、doubleをキーにソートって感じにしたいんですが、どうしたらいいですか？ char型のメンバは重複する場合もあります。 145 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:46:00 ] 扱う要素数によるよ。 整数とかポインタなら、数千まではvectorの方が一般的に他のコンテナよりも速い 146 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:49:31 ] つまりvectorにガシガシいれてあとからソートですか？ 147 名前：デフォルトの名無しさん [2008/10/22(水) 21:50:32 ] 実測しよう 148 名前：デフォルトの名無しさん [2008/10/22(水) 21:51:29 ] それほど速度を気にしないなら、setにぶち込むのが簡単。　いれたらソート終わっているので 149 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:52:15 ] そんなに速度は気にしません。あまりにも比較して遅いなら別ですが 150 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:02:12 ] 気になるなら測れ、としか。 151 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:03:05 ] 速度気にしてないのか 152 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:13:56 ] 気にしてないわけではありません。 実測してみます 153 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:18:40 ] typedef struct{ double dist; char name[20]; }DIST; int main(){ std::set<DIST> distance; distance.insert( 200 ); →２要素を代入するにはどうすればいいですか？ } 154 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:22:03 ] >>153 DIST型のオブジェクトを渡すべきところへ200を渡してどーすんですか 155 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:36:25 ] あらかじめvectorでサイズを決め打ちするなら早いけど、 領域を増やしていくならsetのほうがはやい 156 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:37:13 ] >>154 渡し方がわかりません。ソートに使うキーはdoubleのほうです 157 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:40:53 ] >>153 std::pairでくるんで渡せ 158 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:54:03 ] こんなんでどう？ struct DIST { double dist; char name[20]; DIST(double d, char* str) : dist(d) { std::strcpy(name, str); } friend class Comp; }; struct Comp { bool operator()(const DIST& d1, const DIST& d2) const { return d1.dist < d2.dist; } }; int main() { std::set<DIST, Comp> distance; distance.insert(DIST(200, "abc")); //→２要素を代入するにはどうすればいいですか？ distance.insert(DIST(100, "def")); distance.insert(DIST( 50, "ghi")); for (std::set<DIST, Comp>::const_iterator pos = distance.begin(); pos != distance.end(); ++pos) std::cout << pos->dist << ", \"" << pos->name << "\"\n"; } 159 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:54:46 ] distance.insert( std::pair(200.0 ,"moziretu") ); こうですか？ 160 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:56:05 ] >>158 通りません・・・ 161 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 22:56:51 ] >>160 これ頭に付けてるよな #include <iostream> #include <cstring> #include <set> 162 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:02:07 ] >>161 コピペみすってました・・・ struct DIST { double dist; char name[20]; DIST(double d, char* str) : dist(d) { std::strcpy(name, str); } friend class Comp; }; struct Comp { bool operator()(const DIST& d1, const DIST& d2) const { return d1.dist < d2.dist; } }; これがどういうことをしてるのかわかりません。 163 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:07:19 ] >>162 まず二要素を一度に代入できるように、DISTにコンストラクタを付けた。 こうする事によって一時オブジェクトが生成できるようになる。 次にソートの基準をdoubleにするために、叙述関数もしくは関数オブジェクト を書かなければならないが、この場合は関数オブジェクトを書いている。 というのもstd::setのデフォルトの比較基準はless<DIST>となり、これは 存在しないので、自分で書かなければならないからだ。そこで比較関数 オブジェクトにCompを使う事にして自分で書いている。 164 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:09:37 ] classがstructになっててなんかおかしいよ 165 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:20:44 ] >>164 わかったよこれでいいだろ class DIST { double dist; char name[20]; public: DIST(double d, char* str) : dist(d) { std::strcpy(name, str); } double getdist() const { return dist; } const char* getname() const { return name; } friend class Comp; }; struct Comp { bool operator()(const DIST& d1, const DIST& d2) const { return d1.dist < d2.dist; } }; int main() { std::set<DIST, Comp> distance; distance.insert(DIST(200, "abc")); //→２要素を代入するにはどうすればいいですか？ distance.insert(DIST(100, "def")); distance.insert(DIST( 50, "ghi")); for (std::set<DIST, Comp>::const_iterator pos = distance.begin(); pos != distance.end(); ++pos) std::cout << pos->getdist() << ", \"" << pos->getname() << "\"\n"; } 166 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 02:37:33 ] おまえら暇だな… DIST dist; distance.insert(dist); 167 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 19:19:10 ] func(string hoge){ } という関数に char mozi[256];で宣言された文字列をfunc(mozi)みたいに渡せますか？ 168 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 19:20:02 ] ええ 169 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 19:21:30 ] なんでそんなことができるんですか？ 170 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 19:23:21 ] stringのコンストラクタにconst char*を取るものがあるから 171 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 19:26:39 ] なるほど！STLってほんとにすごいですね 172 名前：デフォルトの名無しさん mailto:sage [2008/10/24(金) 00:21:21 ] でもSTL関係ないですね！ 173 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 03:20:25 ] stringはSTLだろ basic_string<char>でテンプレートだし。 174 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 04:09:49 ] >>173 馬鹿発見 175 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 08:24:14 ] >>173 ん・・あぁ・・そうだね・・・・ 176 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 10:01:54 ] >>173 const char *を引数にとるコンストラクタを持つ文字列クラスは、STL固有ではありません。 177 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 17:43:47 ] んなこたーない 178 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:02:21 ] 自前で似たようなモノを作れるのに？ 179 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:47:47 ] >>176 const T* だよ >>178 STLであろうがなかろうが全部自前で似たようなものを作れるぞ 180 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 20:47:06 ] なんか話が噛み合ってない 181 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 21:03:12 ] わかってないんだよ、おそらく本当にｗ 182 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 21:23:12 ] ということにしたいのですね。

---

---

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

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