std::partial_sortは、先頭から決められた数だけソートします。例えば、 #include <iostream> #include <algorithm> int main() { int a[] = { 7, 2, 5, 1, 6, 8, 3, 9, 4 }; const int size = sizeof(a) / sizeof(a[0]); std::partial_sort(a, a + 4, a + size); for(int i = 0; </algorithm></iostream>…

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見る4.2のゲームか…

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見るまだ4割ほどし…

例えば、multimapで同じキーを持つ要素の個数を調べたいとしましょう。 #include <iostream> #include <map> #include <algorithm> #include <functional> using namespace std; struct S { }; int main() { multimap<int,S *> m; for(int n = 0; n < 3; n++) { m.insert(make_pair(1, new S())); m.insert(m</int,s></functional></algorithm></map></iostream>…

例えばfor_eachの第3引数ですが、ここは関数オブジェクトを指定します。しかしそれを一々作るのもどうかと思うので、関数があればptr_funで関数オブジェクトを作ってそれを利用します。 #include <iostream> #include <vector> #include <algorithm> using namespace std; void print(int </algorithm></vector></iostream>…

http://www.kmonos.net/wlog/111.html#_1001100720 かなり遅れた反応だったにもかかわらず（書く時間がなかなか取れなかった）、うちの記事を取り上げていただきました。ありがとうございます。 例えば、32bit整数を1億個のvectorを構築して、それに1個加え…

C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 ２倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域…

結局、 class CInt { int n; public: CInt(int m) { n = m; } void print() const { cout void print(int k) const { cout };となっていると、 CInt::printがどちらを指すのかわからないためにうまくいかないのだった。 しかし、こうするとわかるようである…

以下は、VC2005EEで。 for_eachとmem_funを組み合わせると、コードが少し短くなる。 #include #include #include #include using namespace std;class CInt { int n; public: CInt(int m) { n = m; } void print() const { cout };int main() { const int n …

iteratorのincrement こう書くと、iteratorのincrementの速度を純粋に比較できる。 void procVector() { vector v; for(int k = 0; k v.push_back(k); int a = 0; typedef vector::const_iterator CIT; for(int i = 0; i for(CIT p = v.begin(); p != v.end(…

sequential access listにランダムアクセスはできないので、 これの速度を調べる。 const int m = 1000; // コンテナの大きさ const int n = (int)(1e10 / m); // 繰り返し回数void procVector() { vector v; for(int k = 0; k v.push_back(k); int sum = 0;…

仕事でlistを使っているところがあって、 こんなところでなにもわざわざlistを使わなくてもと思っていたが、 最近全部vectorにしたら、想像以上に速くなった。 listはどういうときに使えるか考えてみる。 以下のベンチマークは、 VC2003＋Windows XPで行って…

前にも同じようなことを書いたが、 http://d.hatena.ne.jp/inamori/20060903/p1 もうちょっと詳細に。 f(x) = (x + 1) % n という写像のスピードを考える。 x = 0から1000万回この写像を繰り返して、その実行時間を調べる。 実装には、 map, hash_map, vecto…

プロファイラは、 実行時そのコードを何回通るかを示し、 高速化のヒントとなるものだが、 最近はそのコードにかかる秒数までも出してくれる。 http://www.compuware.co.jp/products/devpartner_fm/dpsprofiler.html しかし、これには罠があり、 数値を鵜呑…

f : A → B という写像を実装する。 集合A, Bは同じ個数の要素を持ち、その個数をnとする。 A,Bの型をそれぞれS,Tとすると、 写像の実装で真っ先に思い浮かぶのは、 map であろう。 だが、nが小さいとき pair の配列のほうが速いのではないだろうか。 mapを使…