トップページ⇒tech
988コメント299KB

Boostを語れゴラァ part5

■ このスレッドは過去ログ倉庫に格納されています
0001BOOTS2007/10/18(木) 08:09:35
語って.はぁと part boost::mpl::int_<5>

過去スレ
part 4 http://pc11.2ch.net/test/read.cgi/tech/1175663346/
part 3 http://pc11.2ch.net/test/read.cgi/tech/1158991211/
part 2 http://pc8.2ch.net/test/read.cgi/tech/1139313234/
part 1 http://pc8.2ch.net/test/read.cgi/tech/1091198276/

■関連サイト■
Boost C++ Libraries
http://www.boost.org/

Boost 翻訳プロジェクト
http://boost.cppll.jp/HEAD/

Let's Boost
http://www.kmonos.net/alang/boost/

boost info
http://shinh.skr.jp/boost/
0757デフォルトの名無しさん2008/03/15(土) 14:58:36
ずっとデキューだと思ってた。
デックと言われたとき軽くショック受けて3日ほど寝込んだわ。
0758デフォルトの名無しさん2008/03/15(土) 14:59:32
>>757
ディーク
0759デフォルトの名無しさん2008/03/15(土) 15:13:47
deckとひっかけて、あえてそう読める綴りにしたんだよね。
でも/dek/と発音しなくちゃいけない決まりは無い
0760デフォルトの名無しさん2008/03/15(土) 22:30:16
>>754
つい先日、どっかのスレにリンク貼られてたね。
でも「あらゆるパフォーマンスで」っていう話ではなく、
「皆が思っている以上にdequeが勝っている項目が多い（から、dequeを軽視するのはやめよう）」
という話だったかと。
0761デフォルトの名無しさん2008/03/15(土) 22:32:46
「とりあえずvector使っとけばいいってもんじゃない」ぐらいの趣旨かと
0762デフォルトの名無しさん2008/03/15(土) 22:34:17
>>760
「要素の連続性保証がいらないならdequeにしとけ〜」じゃなかった？
0763デフォルトの名無しさん2008/03/15(土) 22:34:57
deque は間に挿入しないのであれば
メモリの最確保が起こってもコピーが発生しないからな。
あれは凄い利点だと思う。
0764デフォルトの名無しさん2008/03/15(土) 22:47:11
ギャップ付きベクタを一般化したような感じだよな
0765デフォルトの名無しさん2008/03/15(土) 22:47:52
Stackなどの補助コンテナはデフォルトでdequeを使ってるという事実。
0766デフォルトの名無しさん2008/03/15(土) 22:59:45
そりゃそうだろ
両端キューなんだからスタック・キューの実装に不向きなわけが無い
0767デフォルトの名無しさん2008/03/15(土) 23:03:27
まあオーバースペック感はあるが。
0768デフォルトの名無しさん2008/03/15(土) 23:10:40
>>766
ウフフフ
0769デフォルトの名無しさん2008/03/15(土) 23:10:56
dequeはランダムアクセスに弱いし、
vectorに比べるとメモリ効率も悪い。

>>763
間に挿入してもコピーは発生しない。
0770デフォルトの名無しさん2008/03/15(土) 23:15:43
>>769
間に挿入してコピー発生しなかったらそれはリストなんだぜ。
deque の挿入で O(1) なのは両端の挿入だけ。
0771デフォルトの名無しさん2008/03/15(土) 23:23:19
間に挿入してもコピーが発生しないようなdequeは書こうと思えば書けるのでは？
0772デフォルトの名無しさん2008/03/15(土) 23:26:54
>753
横浜優勝スレの人？

>757
P.J.Plaugerさんによると、デックかディーキュー（ディーイーキュー）と読めだそうな。
0773デフォルトの名無しさん2008/03/15(土) 23:28:14
>>771
ランダムアクセスがかなり複雑になりそうな・・・。
0774デフォルトの名無しさん2008/03/15(土) 23:30:52
ランダムアクセスと途中への挿入・削除を高速にしたい場合はどのコンテナを使ったらいいですか？
0775デフォルトの名無しさん2008/03/15(土) 23:34:17
木構造を使えば全操作を O(log N) で行えるようにはできる。
0776デフォルトの名無しさん2008/03/15(土) 23:35:00
裏を返せば、O(1) でできる操作がないってことだが。
まあ、サイズ取得くらいは O(1) で可能だけども。
0777デフォルトの名無しさん2008/03/16(日) 00:07:32
>>774
map
0778デフォルトの名無しさん2008/03/16(日) 00:08:36
std::map の operator[] はランダムアクセスとはちょっと違うよな・・・。
0779デフォルトの名無しさん2008/03/16(日) 01:08:38
Boost 1.34.1のuBlasを使っています。
matrixの要素をすべて列挙したいのですがどのようにすればいいですか？
できるだけシンプルな方法が知りたいです。
0780デフォルトの名無しさん2008/03/16(日) 02:04:47
>>754
1つ前のSTLスレにあった。
http://www.codeproject.com/KB/stl/vector_vs_deque.aspx
0781デフォルトの名無しさん2008/03/16(日) 02:22:51
>>779
ublas::matrix<T> m;

for (std::size_t i = 0; i < m.size1(); ++i) {
    for (std::size_t j = 0; j < m.size2(); ++j) {
        m(i, j);
    }
}
0782デフォルトの名無しさん2008/03/16(日) 02:28:42
ありがとうございます。
やはりインデックスを使わないと無理でしょうか。

述語Pの成り立つ要素をカウントしたくて

int c = std::count_if( [first, last] , P);

みたく1行で書きたかったのですが。
07837822008/03/16(日) 02:30:40
[first, last]
じゃなくて
[first, last)
です。すみません
0784デフォルトの名無しさん2008/03/16(日) 02:48:48
イテレータを作ればいじゃない
0785デフォルトの名無しさん2008/03/16(日) 03:37:48
ありがとうございます。
イテレータを作ってみたら結果的には長くなってしまいましたが望み通り動きになりました。
0786デフォルトの名無しさん2008/03/16(日) 08:21:41
>>769
間に挿入してもコピーは発生しない。

規格では、こんなこと言ってない。どこに挿入しようが
メモリのreallocationは起こりうるというふうに考えて
おかないといけない。
0787デフォルトの名無しさん2008/03/16(日) 10:24:54
dequeのランダムアクセス (operator[]() とか at() とか) は
定数時間だったと記憶していたが、俺の記憶違いか?
0788デフォルトの名無しさん2008/03/16(日) 10:27:19
dequeのランダムアクセスはO(1)じゃないなんて意見はでてないよ？
0789デフォルトの名無しさん2008/03/16(日) 10:30:54
std::dequeはそうだね。

dequeはdouble ended queueのことだから、
deque一般には成立しない。
0790デフォルトの名無しさん2008/03/16(日) 10:32:54
>>788
>>769 とか。

>>789
ここまでの deque の話って std::deque の話じゃなかったの?
07917882008/03/16(日) 10:34:28
あ、ほんとだ
すまんこ
0792デフォルトの名無しさん2008/03/16(日) 10:35:06
俺もstd::dequeの話だと思ってた
0793デフォルトの名無しさん2008/03/16(日) 10:38:33
C++だとlistが、
double linked listで実装されたdequeにそのまま使えるから、
dequeの別の実装はないだろうね。

Javaはdequeはinterfaceで、
list版とarray版の両方の実装がある。
0794デフォルトの名無しさん2008/03/16(日) 11:41:32
テキストエディタ作ってるんだけど、行管理クラスは各行へのランダムアクセスと
途中への挿入・削除処理の高速性が要求される

std::deque はその両方の要求を満たしてるの？
0795デフォルトの名無しさん2008/03/16(日) 11:57:57
>>794
途中への挿入・削除はノードベースコンテナ（std::list std::setなど）よりは遅い。
ランダムアクセスは、一般的にメモリの構造上vectorよりはアクセス速度は落ちる。
でも実害ないなら無視すればよろし。
0796デフォルトの名無しさん2008/03/16(日) 12:16:09
各行へのランダムアクセスって、どういうときに使われるの？
いきなり500行目にジャンプ！とかってあんましないような。
頻繁に行われるであろう検索・置換もシーケンシャルだし。
0797デフォルトの名無しさん2008/03/16(日) 12:21:26
行数指定してジャンプは良く使わないか？
コンパイルエラーを直すときとか
0798デフォルトの名無しさん2008/03/16(日) 12:29:50
たしかにコンパイルエラー直すときは重宝するけど他にもあるかな？
std::deque を使うとランダムアクセスは定数時間だけど、削除とかは線形時間。
例えば1万行のテキストの空行を全て削除、とかいう操作をやるともっさりしそう。（最悪で1万の2乗くらいのオーダー）
std::list の方がいいのでは。
0799デフォルトの名無しさん2008/03/16(日) 12:30:49
テキストエディタは、
・行指向エディタだと、行のダブル・リンクト・リスト
・ギャップ・バッファ
が古典的だね。

>>797
ギャップ・バッファ方式(e.g. Emacs)でもそんな遅くないでしょ。
こっちの方が改行コードを含めた正規表現検索とかやりやすいし。
0800デフォルトの名無しさん2008/03/16(日) 13:24:03
STLコンテナの要件を満たすギャップバッファ式コンテナを作ったことがあったが
なかなかいい勉強になった。
0801デフォルトの名無しさん2008/03/16(日) 14:19:07
うｐ
0802デフォルトの名無しさん2008/03/16(日) 14:48:32
検索するといくつかあるね
ていうかboost関係ないな
0803デフォルトの名無しさん2008/03/16(日) 14:57:26
Boostにもあればいいって話かな
0804デフォルトの名無しさん2008/03/16(日) 15:02:59
>>800
俺も以前ショボイながら作ったけど、ギャップバッファの実装そのものより、
STLコンテナの要件を満たす条件を調べるのに費やした時間の方が長かったという・・・
0805デフォルトの名無しさん2008/03/16(日) 15:07:35
既存のvectorとかdequeにあわせｂﾄ戻り値やら関瑞狽竄迯�黷ﾎ
とりあえず問題なくね？
0806デフォルトの名無しさん2008/03/16(日) 15:33:11
ContainerConceptが通れば問題ないよ
0807デフォルトの名無しさん2008/03/16(日) 17:26:46
>>786
メモリの reallocation とコピーは別問題だよ。

>>790
deque のランダムアクセスは O(M) （M は内部バッファの分割数）。
O(N) よりははるかにマシだが、O(1) ではない。
0808デフォルトの名無しさん2008/03/16(日) 17:29:10
>>807
何見てしゃべってんの？規格じゃないよね？
0809デフォルトの名無しさん2008/03/16(日) 17:31:12
規格じゃない。
具体的に実装すると大抵の場合そうなっちゃうという話。
0810デフォルトの名無しさん2008/03/16(日) 17:36:32
つまり特定の実装に依存する話なわけだ。

途中への挿入で複数要素のコピーが発生する実装も、
ランダムアクセスが O(1) な実装も、規格の範囲で在りうるんだから、
何の前提も書かずに言い切らないでほしい。
0811デフォルトの名無しさん2008/03/16(日) 17:38:19
>>807
別問題じゃないよ。
std::dequeは、挿入・削除は対象以外の全てのリファレンス、ポインタ、イテレーター
を無効にする。リファレンスとポインタは先頭、末尾挿入の場合は有効のまま。
Josuttis本にはこう書いてある。
ということは、reallocationによって要素は移動されることもあるというわけでしょ。
これは初期化あるいは代入は発生しうると考えておくべきということ。
Josuttis本が間違いなら知らん。
0812デフォルトの名無しさん2008/03/16(日) 17:38:48
配列をvectorに変えたら、コンパイラがsseを使わなくなったのだけど
vectorってsse使ってくれないの？
FC8+Intel v10です。
0813デフォルトの名無しさん2008/03/16(日) 17:39:34
安全を考えると当然規格には従っておくべき。
0814デフォルトの名無しさん2008/03/16(日) 17:40:20
スレ違いな話が続いたせいで迷子がでたようだ。
0815デフォルトの名無しさん2008/03/16(日) 17:40:23
>>811
挿入・削除されたから無効になるんだろ。
reallocation が起こらなくても無効になるんだから、
reallocation とは無関係。
0816デフォルトの名無しさん2008/03/16(日) 17:40:25
分かった分かった。
お前はO(N)なソートでも使ってろ。
0817デフォルトの名無しさん2008/03/16(日) 17:42:28
>>807,809
deque のランダムアクセスは償却定数時間じゃないと規格の要件を満たさない。
「内部バッファの分割数」ってのがはっきりしないけど、「O(1) ではない」と言い切れて
しまうような実装は deque とは言えないんじゃないの？
0818デフォルトの名無しさん2008/03/16(日) 17:44:53
>>815
挿入もしないのに勝手にreallocationされんの？
新しい要素のために領域が必要だからreallocationされるんじゃないの？
0819デフォルトの名無しさん2008/03/16(日) 17:45:14
ランダムアクセスが償却定数ってどういうこと？
規格には定数って書いてあるよ
0820デフォルトの名無しさん2008/03/16(日) 17:49:23
>>815
shrinkはされる可能性はあるが、reallocationは必要になったときのみだ。それは
必要な領域拡張のとき。要素の挿入もその可能性は常にある。だから関係はある。
0821デフォルトの名無しさん2008/03/16(日) 17:49:38
>>817
ああ、よく考えたら定数で実装できそうだな。
0822デフォルトの名無しさん2008/03/16(日) 17:49:42
>>819
あれ？そうなの？
"Table 68 - Optional sequence operations" に載ってて、こいつらみんなまとめて
償却定数時間だから、 deque の operator [] もそうだと思ったんだけど。
別のところに書いてあるのか？
0823デフォルトの名無しさん2008/03/16(日) 17:52:04
長くなりそうなら、いいかげんにスレ移動してくれ。
0824デフォルトの名無しさん2008/03/16(日) 17:57:54
>>822
ごめん、俺の勘違い
0825デフォルトの名無しさん2008/03/16(日) 18:02:03
厳密には
先頭と最後の要素へのアクセス速度は同じ。
それ以外には間接レベルが違うから差異があるよ。
Big O記法はよく知らんが、少なくともlogやn^2ではない。
Data Structure AND Algorithm In C++が分かりやすい。
0826デフォルトの名無しさん2008/03/16(日) 18:08:17
この辺で語った方がみんなのためにもなると思うんだ

【C++】STL（Standard Template Library）相談室 9
http://pc11.2ch.net/test/read.cgi/tech/1204045410/
0827デフォルトの名無しさん2008/03/16(日) 18:08:56
>>818
>>>815
端への追加は O(1) で行わないといけないので、
端への追加でメモリを最確保する必要があったとしても、
それまでのデータを新しいメモリにコピーするようなことは行えない。
データの全コピーは O(N) だから。
この場合、メモリの最確保が行われるが、コピーは発生しない。でしょ？
0828デフォルトの名無しさん2008/03/16(日) 18:11:37
> 最確保 の検索結果 約 183 件...
0829デフォルトの名無しさん2008/03/16(日) 18:15:09
>>827
端はわかるけど、中間への挿入はどう考えればよい？
コピーが発生しないなら、挿入時に挿入要素以外の全イテレータは無効になる理由が
わからん。
0830デフォルトの名無しさん2008/03/16(日) 18:17:26
>>829 >>826
0831デフォルトの名無しさん2008/03/16(日) 18:21:44
このカスどもはスレチな話をいつまで続ける気なんだ
0832デフォルトの名無しさん2008/03/16(日) 18:22:58
>>829
中間への挿入はコピーが発生するに決まってるだろ。
0833デフォルトの名無しさん2008/03/16(日) 18:23:26
てか、そんな神経質にならずに先ずは規格で言われてるように
使えばいいだろ。たいがい問題ない。

考えて見ればBoostスレじゃないか。おしまい。
0834デフォルトの名無しさん2008/03/16(日) 18:24:39
>>832
でしょ。そのときは新しいメモリの割り当てもあり得るじゃん。
ウヒヒ。
0835デフォルトの名無しさん2008/03/16(日) 18:25:45
>>834
内部で確保しておいたバッファを越えていなければ
メモリの割当は起きないだろ。
0836デフォルトの名無しさん2008/03/16(日) 18:26:41
>>834-835 >>826
0837デフォルトの名無しさん2008/03/16(日) 18:27:42
要するに、reallocation に原因があるのか
それともコピーに原因があるのか、
それが分かっていない、とそう言ってる。
イテレータが失効するのはコピーが発生する可能性があるから。
reallocation がその時たまたま起こるかもしれないが、それは直接の原因じゃない。
0838デフォルトの名無しさん2008/03/16(日) 18:47:22
ところで progress_display なんだが
0839デフォルトの名無しさん2008/03/16(日) 18:54:59
断る
0840デフォルトの名無しさん2008/03/16(日) 19:03:31
>>835
よく読んでね。
あり得るって書いてるでしょ。
0841デフォルトの名無しさん2008/03/16(日) 19:28:40
【C++】STL（Standard Template Library）相談室 9
http://pc11.2ch.net/test/read.cgi/tech/1204045410/
0842デフォルトの名無しさん2008/03/16(日) 19:59:28
>>838-839
ｶﾜｲｿｽ
0843デフォルトの名無しさん2008/03/16(日) 19:59:36
>>840
100% 起こることではないってことだろ？
だからこその >>837 だ。
0844デフォルトの名無しさん2008/03/16(日) 20:45:32
boost::mutex てヘッダだけで完結しないんだな。
ライブラリをリンクするのめんどくさいし＋デカくなるんだが。
0845デフォルトの名無しさん2008/03/16(日) 22:08:13
Boost関係ないけど、C++の規格ってみんな何を参照してるんですか？
0846デフォルトの名無しさん2008/03/16(日) 22:10:15
JIS のサイトでタダで見れる。
0847デフォルトの名無しさん2008/03/16(日) 22:15:16
ANSI。安いし。
0848デフォルトの名無しさん2008/03/16(日) 22:28:18
つーかJISが自由に見れないってどうなのよ
ああいうものこそフリー・オープンであるべきなのに
0849デフォルトの名無しさん2008/03/16(日) 22:33:31
維持には金がかかるんだよ！ ってことだろう。
まあ、ネット上で見る分にはタダだから俺は気にはしてないが。

それよりも、金払って買っても
C の規格書とか画像データの PDF で検索できないとかいう話らしい点は
どうかと思う。
0850デフォルトの名無しさん2008/03/16(日) 22:39:54
なんでこうスレ違いな話をここでやるんだ？
0851デフォルトの名無しさん2008/03/16(日) 23:26:25
うっかり盛り上がってしまったから。
いいじゃないか、たまには。
0852デフォルトの名無しさん2008/03/16(日) 23:33:06
ダメ。
2度も3度も誘導されておいて、移動しないのはアホ。
ふさわしい場で議論をしようという気がない腑抜け。
0853デフォルトの名無しさん2008/03/17(月) 00:10:35
そんな議論なんてまじめなことやる気がないのは
移動しないあたりからよくわかる。
ちょっとおいたのすぎた雑談だよ。
0854デフォルトの名無しさん2008/03/17(月) 02:46:47
ラベルも低いしな。
0855デフォルトの名無しさん2008/03/17(月) 05:01:12
別に良いじゃん
0856デフォルトの名無しさん2008/03/17(月) 05:02:05
っていうかなんでこの板はIDないの？
■ このスレッドは過去ログ倉庫に格納されています