System generowania i wyszukiwania unikalnego ID

Witam, staram się wymyślić jakiś system generowania i wyszukiwania wolnego U(nique)ID w strukturze danych.
Przykładowo:

struct StrDanych {
   unsigned long int UID;
   string Dane;
};
main(){
   vector <StrDanych> Array;
   return 0;
}

Do takiego wektora będę dodawał kolejne elementy, każdy z nich musi mieć swoje UID. Na początku jest łatwo bo będą to kolejne liczby 1,2,3,..,n ; jednak w momencie kiedy usunę kilka elementów w środku zwolnią się kolejne UID np. 4,15,38,...,m. W końcu kiedy będę dodawał kolejne elementy chciałbym żeby zamiast przypisywać dane do obecnego najwyższego UID+1 przypisać do najniższego wolnego, np 4 (w tym przykładzie). Od razu zaznaczam że UID nie ma nic wspólnego z indexem w tablicy, gdyż za pomocą tych UID będą powiązane inne struktury, jak w bazie danych (przynajmniej Accessie:p) za pomocą klucza podstawowego (bo koniec końców o to mi chodzi).

Przykładowy przebieg tego o czym mówię jeśli dość kiepsko opisałem:

>Tablica elementow<
UID...Data
..1...Kon
..2...Kura
..3...Kogut
..4...Slon
..5...Tygrys

->Dodaj nowy element
UID...Data
..1...Kon
..2...Kura
..3...Kogut
..4...Slon
..5...Tygrys
..6...Kanapka //dodało na najbliższym wolnym UID - '6' Kanapke

->Usun Slon
UID...Data
..1...Kon
..2...Kura
..3...Kogut
..5...Tygrys
..6...Kanapka

->Dodaj nowy element
UID...Data
..1...Kon
..2...Kura
..3...Kogut
..4...NowyElement //zabiera wolną 4 zamiast 7
..5...Tygrys
..6...Kanapka

Mój obecny algorytm ma sens tylko dla bardzo małego zakresu danych (dla 50 tyś. trwa to już kilka sekund) (jeśli jest potrzeba mogę go wrzucić). Także zwracam się do was z pytaniem, czy ktoś mógłby mi podsunąć jakieś sensowne rozwiązanie mojego problemu - tzn jakieś 'słowo klucz' wg. którego mógłbym przeszukać internet albo jakąś technikę organizacji czegoś takiego. Nie proszę o kod!

W zasadzie mógłbyś trzymać gdzieś dodatkową strukturę danych - np. stos, który zapisuje jakie numerki są wolne. Aktualizujesz go przy dodawaniu i przy usuwaniu: jeżeli usuwasz wpis o UID x to odłóż x na stos, a przy dodawaniu sprawdzaj, czy coś jest na stosie - jeżeli jest, to to będzie nowy UID, jeżeli nie, wtedy kolejny wolny.

Może UUID? http://en.wikipedia.org/wiki/Universally_unique_identifier
fakt faktem losowe, ale przy takich danych nie ma co się przejmować:

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion,[35] that means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

a problem szukania wolnych numerków odpada.. mój szef na praktykach testował kiedyś wydajność takiego UUID jako klucza podstawowego w odniesieniu do inkrementowanego inta, w PostgreSQL nie było prawie różnicy.