STL
ずっと書こうと思っていたんですが，この機会に書いてしまおうと思います． いくつかのアルゴリズムは型の特性によって最適な実装にディスパッチしています．このような例として最も代表的なのがstd::distanceです．std::distanceはイテレータのカテゴリとい…
vectorがPODのバッファとして使えるかどうか実験してみました．ただし，自分は精度の良い測定ができるフレームワークを持っていないので，大まかな結果だけ載せておきます． (´-｀).。oＯ（地道にstd::clock()使って統計的に値を推定したなんて恥ずかしくて…
setやmapのiterator範囲による構築やassignって，ソート済み範囲ならO(N)保証だったんですね．ソート済み範囲突っ込んでもO(NlogN)保証だとばかり思い込んでいた・・・orz．さらには，insert_iteratorによる挿入もソート済み範囲の挿入で，かつ挿入先が連続…
というわけで，ここまで長々訳の分からないことを書いておきながら，結論は至ってシンプルです．自前のfor文回すのが一番楽ですが，ここはあえて既存のアルゴリズムでやってみました． template inline bool is_sorted(ForwardIterator first, ForwardIterat…
さて，ようやく自分の疑問の核心部にたどり着きました． 厳密で弱い順序が何故STLにおいてここまで重要視されているのか，多くの書籍は「数学的な詳細には立ち入らない」としてこの部分の議論を避けているので，ここではあえてそれに踏み入ってみます． 厳密…
STLにおいて，順序を定める述語を指定するときにはすべからく「厳密で弱い順序（Strict Weak Order）」という概念が出てきます．この概念がいかにSTLで重要な位置を占めているかは次の事実を見てもらえば一目瞭然です． std::setで要素の比較に使われる述語…
まず最初に「値が等しいということ（Equality）」という概念について今一度確認してもらいます．C++（に限らず多くのprogramming言語）で普通"=="（及び"!="）で表される関係です． int a = 1; int b = 1; int c = 2; assert( a == b ); // `a' is equal to …
ここ2日ほど考えていたis_sortedですが，ようやく結論が出ました．ですがその結論の前に，多分多くの人にとっては全然面白くないであろうことを延々議論します． 結論は今日のblogの一番最後にありますので，結論だけ見たい人はid:Cryolite:20040529#p5へ飛…
id:Cryolite:20040526#p3に関して． http://www.talkaboutprogramming.com/group/comp.lang.c++.moderated/messages/162386.html keyが重複している場合はどうするんだ，という指摘． 言われてみればそうでした．id:Cryolite:20040526#p3で書いたコードはkey…
id:Cryolite:20040526#p3書いていて，ふとなぜadjacent_findがforward iterator要求するのか不思議に思ったのですが，よく考えてみればadjacent_findってiteratorを2回dereferenceする必要があるのでsingle passじゃないのですね．でも，forward iteratorが…
あるiterator範囲がソート済みかどうかを調べる，という要求に対して，私は以前からstd::adjacent_findを使うのが癖になっていて「読みにくいコード書いてしまっているのかな？」と思っていたんですが，これってidiomとして一定の認知度を得ているみたいです…
id:Cryolite:20040518#p2で指摘した，adaptableでないfunctorをadaptableにするコードを(・∀・)ハケーン．っていうか，やっぱり車輪の再発明だったか・・・orz http://www.boost.org/boost/bind/make_adaptable.hpp
上の言葉，AT&Tの，名前の読み方が良く分からないある禿げたおっちゃんの言葉ですが，この言葉，意訳すると「文字列クラスの実装には多くのものが考えられる」という意味になります．どこをどう訳したらそういう意味になるのかは置いておいて，文字列クラス…
STLの汎用アルゴリズムを定義しているヘッダーに一通り目を通してみたのですが，さすがというかなんと言うか「綺麗」の一言しか出ませんねぇ．C++でプログラムを組む，特にiteratorをきちんと使おうとするなら，一度は見ておきたいソースです．というか，あ…
さて，ここまでは話の半分で次からが本題です． 日々boostと戯れる変態（褒め言葉ですからね！）なら，当然，transform_iteratorに渡すファンクタをlambdaでinlineに書きたいと思いますね？思いませんか？思わない人はここでさようなら． で，実際にやってみ…
std::copyは入力と出力がオーバーラップしている場合，注意して使用しなければなりません．入力の前半と出力の後半がオーバーラップしてる場合のみ，std::copyが安全に使用できます．例えば以下のような場合std::copyは安全に使用できます． int a[10] = {0,…
