[B! stl] paellaのブックマーク

STL風に使えるマップ型コンテナの紹介と性能比較 - Preferred Networks Research & Development

最近スマートフォンに乗り換えました。徳永です。 C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。以下、計算量の表記をする際には、要素数をnとします。 Loki::AssocVector LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ

paella 2011/07/20

Loki::AssocVectorとgoogle-sprasehashとSTX B+ Treeとstd::mapとstd::tr1::unordered_mapのメモリ消費と探索時間の比較。あとで読む

リンク

C++のmapについてのめも - ichirin2501's diary

速度向上を考える上で、mapの使い方で差が出たのでめも。 mapは[ ]演算子がオーバーロードされているので、演算子の書き方を多用していた。演算子で書くと存在しないkeyを指定した場合、自動で生成してくれる。これが便利なときもあれば不便なときもある。例えば、メモ化探索にmapを利用していた場合、既に探索した状態かどうかを調べるときに[]演算子で勝手に状態生成してもらっては困る。なので、今まではこんな感じで書いてた。 map<int,int> mii; int dfs(int S){ if( mii.count(S) ){ return mii[S]; } int ret = 0; /* 処理 */ return mii[S] = ret; } countメソッドはkeyがあるかどうか(0or1)を返す。勝手に状態数は増えない。でも、どう考えても　探索3回してるよねこれ mapの[]演

paella 2011/03/25

「[]演算子で書くと存在しないkeyを指定した場合、自動で生成してくれる。これが便利なときもあれば不便なときもある」

リンク

EASTL から垣間見るゲームソフトウェア開発現場の現状その 1

(2016/02/10 追記: EASTL は長らく EAWebKit の一部としてライセンスが不明瞭なまま公開されていましたが、この日 BSD ライセンスで正式に公開されました https://github.com/electronicarts/EASTL) 若干古いものですが、2007 年に発表された、Electronic Arts によるゲーム開発向けの改良を加えた STL、"EASTL" の仕様。 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html 仕様だけで実装が公開されてないのが非常に残念なのですが、それは別として、何故こんなものが必要なのか、どういう事情でこの機能が盛り込まれたのか、といったゲーム開発現場の事情が細かく解説されていて、とても参考になります。特に、既にある程度 C++ に習熟してい

paella 2011/02/28

Electronic Arts Standard Template Library。ゲームプログラム向けにSTLを賢くさせたもの、らしい。組み込みにもよさげ。

リンク

My iPhone is not a Mac Pro – Savoy Blog

This article is about enhancing the performance of iPhone applications using the power of Objective C++. By discussing a real-world probl em from Savoy’s Spots application, the article shows the necessary optimizations to make the program run smoothly in three steps. Using Objective C++ to enhance the performance of iPhone applications. One thing I really like about software development is, that th

paella 2011/02/09

高速列挙とC配列へのアクセス、アルゴリズムの改良で250msec→1msecの高速化を行った話。一つ一つの状態でのソースがあるので分かりやすい。

リンク

STL のコンテナにデフォルトコンストラクタが無いクラスのオブジェクトを突っ込むお話 - Cry’s Diary

某曲をヘビーローテーション中．その指ごと連れてってあげる〜♪ STL のコンテナの要素になるために必要な要件は CopyConstructible (20.1.3/1 と Table 30) - 要するにコピーコンストラクタを持っていて，その意味がコピーとしてきちんと定義されていること Assignable (23.1/4 と Table 64) - 要するに代入演算子（operator=）を持っていて，その意味がコピー代入としてきちんと定義されていること（例外安全性の要件として，コピーコンストラクタと代入演算子（operator=）が強い例外安全性を保証すること，及びデストラクタが例外を送出しないこと（no-throw）を保証すること）（ちなみに SGI STL の記述では上2つを合わせたものが Assignable コンセプトになっている）以上です．特に注意すべきこととして，デ