【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 以降 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 ] ということにしたいのですね。 183 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 21:36:55 ] はいはい模範回答。 もともとのAlexanderのSTLにはbasic_string<>は無かった。 しかし、標準化の過程でSTLコンテナに適合するようにされた。 basic_string<>がalgorithmと重複するようなメンバ関数を持っていたり、 しかもそれがイテレータではなくsize_typeを扱ったりするのはその名残。 184 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 10:23:42 ] >>173 の >basic_string<char>でテンプレートだし。 てのが気になるなあ… 「stream I/O もテンプレートだからSTL」とか言い出しかねない勢い。 185 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 12:46:36 ] 入念に勉強してない限り、 「C++コンパイラに付いてくるtemplate classを使ったもの全部＝STL」 と思っている人は多い気がする 実用上困る事項でもないし・・・ 186 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 15:08:26 ] 定期的に出る話題だから 今回も「ああ、またですか」てなもんだ。 でもbasic_stringはもう 仲間に入れてあげてもいいと思うんだ。 187 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 16:00:31 ] やだよ basic_stringなんてC++標準化委員会も「失敗作だった」と 認めているじゃないか 188 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:21:30 ] そこまで言ってたっけ。 189 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:55:00 ] >>186 たまにこのスレを斜め読みするものとしては そういう話が定期的に回ってくれると 自身の無知加減がよくわかるから助かるよ。 basic_stringって曰くがあったのか・・・（´・ω・） 190 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 01:35:54 ] >>187 ソースくれ 191 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 01:47:14 ] 標準化委員会はSTL自体が「失敗作だった」って 認めてたぞ 192 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 01:50:21 ] 標準化委員会はC++自体が「失敗作だった」って 認めてたぞ 193 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 04:45:29 ] 親は>>192自体が「失敗作だった」って 認めてたぞ 194 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 11:11:11 ] 俺は「性交作だ」って聞いた 195 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 11:40:21 ] おあとがよろしいようで 196 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 20:20:17 ] 100個ぐらいの文字列を入れて そのなかで一番出現率が高い文字列を探すには STLのどんなデータ構造とアルゴリズムをつかえばいいでしょうか？ 197 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 20:43:38 ] まず服を脱ぎます 198 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 20:44:07 ] 次にソートします 199 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 20:48:02 ] かぜひきました 200 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 20:51:58 ] 相当大変な事態ですね。

---

---

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

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