IDの自動採番について

質問

次のような要件で、各要素に自動的にIDを採番したいのですが、最も効率的なやり方はどのような方法でしょうか？

・各要素は連想配列に格納される（MFCならCMap等）
・要素は一つずつ配列に追加される。追加する際、IDを自動採番して、これをキーとする。
・任意の要素を、キー（自動採番されたID）指定で削除することが出来る。
・IDの最大値は最小化したい。

最後の要件は、IDの値そのものにある意味を持たせているため、可能な限りIDの値を大きくしたくありません。つまり、ある要素を削除した場合、IDも同時に削除されますが、そのID値を次に追加する要素で再利用したいと言うことです。

IDは所謂主キーですので、要素を削除した際にID値を前に詰めるような事はもちろん出来ません。一旦ある要素にIDを割り当てると、その要素が削除されるまで値を変更することは出来ません。

格納される要素をElementとすると

ID - Element
------------
1 - Element[1]
2 - Element[2]
3 - Element[3]
4 - Element[4]
5 - Element[5]

このような配列になっていた場合、ID"3"の要素を削除すると配列は下記のようになります。

ID - Element
------------
1 - Element[1]
2 - Element[2]
4 - Element[4]
5 - Element[5]

次に６番目の要素を挿入する際、その要素にID"3"を割り当てます。

key - Element
------------
1 - Element[1]
2 - Element[2]
4 - Element[4]
5 - Element[5]
3 - Element[6]

このように常に「IDの最大値＝配列のサイズ」となるようにしておきたいのです。
配列内の並びは使用する配列クラスの実装に依りますので、必ずしも上記のようになっているわけではありません。

要素がオブジェクト型で、かつIDとして割り当てる数値も単なる数値以上の意味を持たせるため、連想配列はCMapPtrToPtrクラス（またはそれに相当するクラス）で実装したいと思っています。
この場合、要素追加の度に、一旦全てのキー（ID）を配列から取り出して、ソートしてから空きIDを探し、そのIDを新規追加要素に割り当てる方法しかないのでしょうか？

このような事をもっとシンプルに実現したクラス等はないのでしょうか？

データベース等の外部ソフトウェアは使用しないものとします。

回答No.2

wormhole · ベストアンサー

＞これが最もスマートなやり方でしょうか？

さあ？
私が今思いつくなかでスマートな方法を紹介したつもりなので
それよりスマートな方法がないか問われましても・・・

ただ「その削除済みリストを参照して最も若いIDを使用すれば」は、
質問内容からすると最も若いIDの必要はないんじゃないかとは思いますが。

条件によりますが
オブジェクトのポインタ値を、そのままIDとして使用する手もありますが。

お礼

ご回答ありがとうございます。

オブジェクトのポインタ値をそのままIDにすれば、確かにユニーク値になるとは思いますが、ランダムな値ではそれに依存したコードが書けません。

確かに最小のIDを使用する必要はありませんね。リストの先頭から再利用すれば良いと思います。

やり方については他の方にも意見を求めたかったので。

回答No.3

duke_kimura

何をもって「効率的」とするのでしょうか？

一般的には、おそらくC++ということで、普通にSTLで実装すれば良いんじゃないでしょうか。

もしこのリストが、極端に規模が大きい物であれば、
C言語で記述して多分探索木で実装するのが高速です。

回答No.1

wormhole

削除されたIDも管理してあげればよいのでは？

お礼

早速のご回答ありがとうございます。

なるほど、そういうことですよね。
削除済みIDリストを別の配列として持っておいて、要素削除の時点でIDをそのリストに追加し、次に要素を追加する時点で、その削除済みリストを参照して最も若いIDを使用すれば良いということですね。
削除済みがなければ、（本配列のサイズ＋１）を新たなIDとして採番し、追加する。

これが最もスマートなやり方でしょうか？

補足

質問に間違った記述がありました。

>このように常に「IDの最大値＝配列のサイズ」となるようにしておきたいのです。

これは必ずしもこのようにはなりません。この一文は無視してください。