未使用IDを探す

int getID() {

    // [前準備]

    // テーブル「ITEMS」から 1000～9999の範囲の ID の値を取り出す。
    // （ID に重複は無い）

    std::vector<int> id_list;

    RecordSet rs = db.querySql(
        "select ID from ITEMS where where ID between 1000 and 9999 order by ID");

    while (rs) {
        id_list.push_back(rs["ID"].getValueInt());
        rs.moveNext();
    }

    // ここまでが前準備

    // ここからが本題

    int id = 1000;

    if (id_list.empty())
        return id;

    for (size_t i = 0; i < id_list.size(); i++, id++) {
        if (id != id_list[i])
            return id;
    }

    throw std::runtime_error("ID不明");

}

こんなコードがありました。

ちなみに、前準備のところにあるDB操作っぽいクラスは適当です。
なんとなく雰囲気で察してください。
やっていることは、DBからIDの一覧を取得して配列へ格納しているだけです。

問題なのは「本題」の方でして……。

何をしているんだろうな、これは。
まったくもって意味不明です。

小一時間ほど悩み、前後の関係から類推して、一つの考えが閃きました。

「もしかして、使用していないIDを探しているのでは」
（この後の処理で、ここで取得したIDを使ってデータを追加しているので、多分間違いない）

まぁ、見て分かるとおり「使用していないIDを探す」のなら、上のコードは全く見当違いの処理をしています。
今まで正しく動いていたのは、
レコードの削除処理が無いおかげで ID に連番が振られ続けているためです。（多分）

「使用していないIDを探す」は、あくまで推測なので、このコードはそのまま放置しましたが、確実に「使用していないIDを探す」のなら、こうなります。

const int MIN_ID = 1000;
const int MAX_ID = 9999;

std::sort(id_list.begin(), id_list.end());
// 今回の例の様に、既にソート済みなら↑は不要

size_t index = 0;
int id = MIN_ID;
while (id <= MAX_ID && index < id_list.size()) {
    if (id < id_list[index])
        return id;
    else if (id == id_list[index]) {
        id++;
        index++;
    } else {
        index++;
    }
}

if (id <= MAX_ID)
    return id;

throw std::runtime_error("ID不明");

---

C++なら標準でそれっぽい関数を持っていそうだったのですが、見当たりません。
それでも一応標準関数を使って実装してみました。

struct gap
{
    bool operator()(int a, int b)
    {
        return a + 1 != b;
    }
};

std::sort(id_list.begin(), id_list.end());

if (id_list.empty())
    return MIN_ID;

if (id_list.front() != MIN_ID)
    return MIN_ID;

std::vector<int>::iterator it = std::adjacent_find(id_list.begin(), id_list.end(), gap());
if (it == id_list.end()) {
    if (id_list.back() == MAX_ID)
        throw std::runtime_error("ID不明");
    return id_list.back() + 1;
} else {
    return *it + 1
}

逆に分かりづらくなりました。

---

std::vector<int> seq;
for (int i = MIN_ID; i <= MAX_ID; i++)
    seq.push_back(i);

std::pair<std::vector<int>::iterator, std::vector<int>::iterator> result =
     std::mismatch(id_list.begin(), id_list.end(), seq.begin());

if (result.second = seq.end())
    throw std::runtime_error("ID不明");
return *result.second;

連番用の配列を用意しなければいけないので、IDの範囲が広いと結構つらい（メモリ的に）かも。

拙作 value_iterator を使えば、メモリの問題も解決です。

std::pair<std::vector<int>::iterator, value_iterator<int, 1> > result = 
    std::mismatch(id_list.begin(), id_list.end(), value_iterator<int, 1>(MIN_ID));

if (*result.second > MAX_ID)
    throw std::runtime_error("ID不明");
return *result.second;

---

コレでもいける。

struct gap
{
    int pre_id;
    gap(int min_id) : pre_id(min_id - 1)
    {
    }

    bool operator(int id)
    {
        std::swap(pre_id, id);
        return id + 1 <> pre_id;
    }
};

std::vector<int>::iterator it = std::find_if(id_list.begin(); id_list.end(); gap(MIN_ID));
if (it == id_list.end() {
    if (id_list.back() == MAX_ID)
        throw std::runtime_error("ID不明");
    return id_list.back() + 1;
}
return *it - 1;

取得できるのが使っていないIDの最小値ではなくなりますが。

---

さて、ここまでの方法は、使っているID（ソート済み）を先頭から順番に調べていって、IDが連番になっていないところを見つける方法でした。

せっかくIDをソートしたのですから、バイナリサーチを使って高速に空きを見つけることが出来るはずです。
MIN_ID + index == id_list[index] が成り立てば、index 以前は連番であることを利用します。

if (id_list.empty())
    return MIN_ID;

    const int id = getID(id_list, 0, id_list.size())
    if (id > MAX_ID)
        throw std::runtime_error("ID不明");
    return id;
}

int getID(const std::vector<int>& id_list, size_t first, size_t last)
{
    if (MIN_ID + first != id_list[first])
        return MIN_ID + first;

    if (MIN_ID + last - 1 == id_list[last - 1])
        return MIN_ID + last;

    const int mid = (first + last) / 2;
    if (MIN_ID + mid - 1 != id_list[mid -1])
        return getID(id_list, first, mid);
    else
        return getID(id_list, mid, last);
}

まだ最適化できそうですが、まぁ良いです。

---

さらに。
これまでは、DBから取得したID一覧から、存在しない値をプログラム側で探していましたが、
DBの方で探してもらうことも出来そうです。

select ID + 1 from ITEMS where (ID + 1) not in
    (select ID from ITEMS where ID between 1000 and 9999) 
  and (ID + 1) between 1000 and 9999
union
select ID - 1 from ITEMS where (ID - 1) not in
    (select ID from ITEMS where ID between 1000 and 9999) 
  and (ID - 1) between 1000 and 9999

全てではないですが、使っていないIDが取得できます。

---

下準備として 0 ～ 9 の10個のレコードを持つテーブル DIGITS を用意します。

create table DIGITS (N number(1,0))
insert into DIGITS (N) values (0)
insert into DIGITS (N) values (1)
...
insert into DIGITS (N) values (9)

select ID from
(select D4.N*1000 + D3.N*100 + D2.N*10 + D1 as ID from
DIGITS D4,DIGITS D3,DIGITS D2,DIGITS D1 where D4<>0)
where ID not in (select ID from ITEMS where ID between 1000 and 9999)

これなら、1000～9999 の範囲で使っていないID一覧が取得できます。

タグ：C++