C++ 双方向リストクラス std::list 入門
双方向リストクラス std::list とは std::list とは C++ で標準に使用できる便利な双方向リストクラスでござるぞ。 「双方向リスト」とは、要素を格納するノードが前後のノードへのポインタを持ち、どの位置への挿入・削除でも O(1) と高速に処理できるコンテナクラスだぞ。 ※ 「コンテナクラス」とは、単一タイプ・データ構造の複数のデータを取り扱うためのクラスのことだぞ std::list と対比されるのは std::vector である。 vector は末尾への挿入・削除は O(1) と高速だが、それ以外の位置への挿入・削除は O(N) で、データ数に比例した処理時間を要してしまう。 その半面、どの位置のデータへも O(1) と高速にアクセス（参照・代入）することができる。 任意の位置へのアクセスをランダム・アクセスと呼ぶので、vector はランダム・アクセスが O(1
イテレータを実装しよう
イテレータ（iterator）は C++ STL（Standard Template Library）の中核を成す概念のひとつで、ポインタの機能を抽象化したものである。 参照外し（dereference）、インクリメント・デクリメント、比較などのポインタ同等の機能を持つ。 STLの各コンテナには、それ専用のイテレータクラスが定義されており、 イテレータオブジェクトの生成はコンテナの begin(), end() メソッドなどで行う。 コンテナの最大要素を取得する例： vector<int> cntn; ..... // cntn にデータを格納する処理 int val = MIN_INT; for(vector<int>::iterator itr = cntn.begin(); itr != cntn.end(); ++itr) val = max(val, *itr); イテレータは、
C++11 乱数 std::random 入門
rand() の問題点 これまで広く使用されてきた rand() による乱数生成には以下の問題点がある。 生成される範囲が [0, 32767] と狭い rand() % N は一様では無い 周期があまり長くない 乱数生成アルゴリズムが固定（通常は線形合同法） 正規分布など、一様でない乱数生成が面倒 rand() で生成される値の範囲は [0, 32767] と狭い。15ビットしかない。 (rand() << 15) + rand() とすれば、30ビット乱数にすることは可能だが、スマートではないし、 生成アルゴリズムの関係で、乱数に偏りが出る場合がある。 通常、乱数として欲しいのは [0, N) 範囲の値であることが多い。この場合は rand() % N とすることが一般的だ。 しかし、このようにして生成した乱数は一様でなく偏りがある。特に N が大きい時にその現象が顕著になる。 例えば
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
