クラスや構造体を順序付けして配列に追加する方法を考える（STLを使用した二分挿入ソート）

二分探索したいんです！
二分探索を行う場合に配列はソートされている必要がある。
配列がソートされた状態を維持するように要素を追加する処理を考える。
ネットには int などスカラ値を使用した例は多いがクラスや構造体を使用する例が少ないので忘れないようにまとめておく。

サンプルソース

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using std::vector;
using std::cout;
using std::endl;
using std::lower_bound;

class Info {
public:
    int id;
};

struct InfoAscending {
    bool operator()(const Info* lhs, const Info* rhs) {
        return lhs->id < rhs->id;
    }
    bool operator()(const Info* lhs, int rhs) {
        return lhs->id < rhs;
    }
//  bool operator()(int lhs, const Info* rhs) {
//      return lhs < rhs->id;
//  }
};

void append(vector<Info*>& vec, Info& info) {
    vector<Info*>::iterator lower =
        lower_bound(vec.begin(), vec.end(), &info, InfoAscending());
    vec.insert(lower, &info);
}

void print(Info* info) {
    cout << info->id << ' ';
}

void delete_info(Info* info) {
    delete info;
}

int find(vector<Info*>& vec, int id) {
    vector<Info*>::iterator lower =
        lower_bound(vec.begin(), vec.end(), id, InfoAscending());
    if (lower != vec.end() && (*lower)->id == id)
        {
        return lower - vec.begin();
        }
    return -1;
}

int main() {
    srand((unsigned int)time(NULL));

    //オブジェクトの追加
    int value;
    vector<Info*> vec;
    for (int i = 0; i < 5; ++i) {
        Info* info = new Info();
        info->id = value = rand() % 99;
        cout << "Add " << info->id << endl;
        append(vec, *info);
    }

    //コレクション一覧
    cout << "Vector { ";
    std::for_each(vec.begin(), vec.end(), print);
    cout << '}' << endl;

    //最後に追加したidを検索
    cout << "Find(" << value << ") : vec[" << find(vec, value) << ']' << endl;
    //存在しないidを検索
    value = 99;
    cout << "Find(" << value << ") : vec[" << find(vec, value) << ']' << endl;

    std::for_each(vec.begin(), vec.end(), delete_info);
    return 0;
}

実行結果

Add 88
Add 10
Add 89
Add 36
Add 23
Vector { 10 23 36 88 89 }
Find(23) : vec[1]
Find(99) : vec[-1]

要素の追加はappend()で行っている。
append()内では std::lower_bound で比較対象以上の値を持つ最初の要素を取得し、その前方に挿入することによりソート済み状態を維持する。
std::lower_bound の第４引数には関数オブジェクトを指定し InfoAscending::operator()(Info* lhs, Info* rhs) が呼び出される。

要素の検索はfind()で行っている。
もともと二分探索による検索は std::binary_search があるが対象の有無しかわからないので不便。
find()では見つけた要素のインデックスを返すようにしている。見つからない場合には-1を返す。

また、ソートキーであるidを指定して検索できるように InfoAscending::operator()(Info* lhs, int rhs) を実装している。
この関数がないと検索するために、Infoクラスのインスタンスが必要になる。

・余談
std::upper_bound を使用する場合には InfoAscending::operator()(int lhs, Info* rhs) のように引数が逆になるので注意が必要。