二分探索
大量のデータがあった場合。
そっからある特定のIDと合致するデータを探したい…
もし、そのIDの小さい順にならんでいるなら二分法がありますね。
二分法そのものに関してはアルゴリズムの本に載ってます。
さてさて、その二分法をstlで使うならこんなプログラムになりますかね。
下のコードは、Dataというクラスのtrueidをキーにして、探すプログラムです。
ポイントは stlのlower_boundの最後の引数ですね。
自分で定義したDataというクラスの<演算子が定義されていないなら、代替用の関数として別途代入できるわけです。
(定義されていても、用途がちがうってときもあるし)
/** * @file main.cpp * @author r-suzuki * @date 2008-04-01 */ #include#include #include #include using namespace std; class Data { public: int m_true_id; int m_inner_id; Data(int ti = -1, int ii = -1); void output(void); }; Data::Data(int ti, int ii) : m_true_id(ti), m_inner_id(ii) { } void Data::output(void) { cout << "Data[" << m_true_id << "]" << endl; cout << endl; } bool compare(const Data& arg1, const Data& arg2) { if( arg1.m_true_id < arg2.m_true_id ) return true; return false; } int main(void) { vector nodes; for(int i =0; i < 10; i++){ nodes.push_back(Data(i)); } for( size_t i = 0; i < nodes.size(); i++){ nodes[i].output(); } // 讀懃エ「 vector
test; test.push_back(1); test.push_back(2); test.push_back(3); binary_search(test.begin(), test.end(), 2); Data a(4); vector::iterator target = lower_bound(nodes.begin(), nodes.end(), a, compare); target->output(); return 0; }