What container/ADT should I use for the following?

[Metalstrm]

monarch, that does sound similar to what I need! Imagine I have these 10 elements in a container, where 'o' is a live element and 'x' is a dead one.

starting at: o o o o o o o o o o

The function picks a random live element, does its magic, maybe killing it in the process, and repeats the random search-kill procedure until all the elements are dead. Say it picks element 3, and kills it, giving

o o x o o o o o o o

It now randomly picks another element, which has to be live, and therein lies the problem. I was thinking of creating a separate list of pointers to choosable elements, and this may be similar to your approach, but I haven't tried it yet...

As it stands at the moment, I am using a bool like I said above. But when the situation gets to something like this,

x o x x x x x x x x,

the function is going to take a long time to get to the one good element it needs. On average, 1000 elements would need something like 7.4k repetitions of the search-kill function, which is around n log n I guess.