Dynamiczna tablica struktur - losowanie

Hej.
Już nie myślę a nigdy nie miałam takiego problemu, dlatego postanowiłam zapytać was. Mam max 300 elementów w dynamicznej tablicy struktur, niektóre z nich po pewnym czasie już nigdy nie zostaną wykorzystane. W strukturze mam zmienną "int użycie=0 albo int użycie=1", która określa czy element w przyszłości może być wykorzystany czy nie. Chciałabym losować element, który zostanie użyty. Teraz pytanie - losować "*na pałę" spośród wszystkich elementów i sprawdzać za każdym razem zmienną "użycie"? Czy może od razu zwalniać pamięć gdy wiem, że element już nie zostanie wykorzystany - tylko wtedy zostaną mi wiszące wskaźniki i indeksy nie będą po kolei np. [2,83,243] i jak tu spośród takich liczb coś wylosuje ;/ Co się robi w takich przypadkach?
Pozdrawiam

*Myślałam jeszcze, że może losować dopóki >połowa jest zdatnych do użycia a potem po prostu przelecieć od początku do końca po tych które zostały (będzie to ułomna losowość), no ale nie wiem już sama.

Może trzymaj na std::list indeksy tych struktur, ktore mogą byc użyte? Losujesz sposród tego, usuwanie z listy jest w czasie stałym.

A czemu nie użyjesz listy zamiast tablicy? Wtedy usuwanie elementów będziesz miała w O(1).

Musisz powiedzieć coś więcej.
Jeżeli ci pozostał jeden element to jego wylosowanie zajmie ci średnio 300 razy.
Natomiast jeżeli masz licznik tych które możesz wylosować, losujesz wartość mniejszą od licznika.
I jedziesz po tablice pomijając te które nie możesz wylosować tu też średnio ci zajmie 300 iteracji ale będą oni trochę szybsze.
Ale jak użyjesz dodatkowej tablicy z indeksami do losowania to losujesz w tej tablice, wymieniasz wylosowany z ostatnim i zmniejszasz licznik to wszystko będzie w czasie O(1)

Nie wiem co mam jeszcze powiedzieć. @Shalom tylko czy z taką "linked list" da się wylosować element?

_13th_Dragon napisał(a):

Ale jak użyjesz dodatkowej tablicy z indeksami do losowania to losujesz w tej tablice, wymieniasz wylosowany z ostatnim i zmniejszasz licznik to wszystko będzie w czasie O(1)

o nie zauważyłam tego. spróbuję to, wydaje się proste i działać. Dzięki! :)

Tak, chociaż dostęp do niego będzie niestety O(n). Ale jeśli lista będzie przechowywać same indeksy a dane będą w tablicy to będzie O(1)