Sign in to follow this  
suliman

return random element of std::list?

Recommended Posts

suliman    1652
Hi is there any way of getting a random element from my list? Say i have a list of <building *> and i just want the list to throw out a completely random element. I could randomize a number, hop fowrard in that list that random many times but that seems a bit silly. Any batter way to do it? Thanks for your help Erik

Share this post


Link to post
Share on other sites
You could try swaping the various pointers within the list or create a circular list and rotate through it like you already said. Lists really are not made for random access. You could always take apart the list toss it in array randomize the array and then toss it back in the list.

Share this post


Link to post
Share on other sites
Perost    332
You should also think about if a list is the best container for you. Do you need constant time insertion and removal of items? If random access is more important, use a vector instead.

Share this post


Link to post
Share on other sites
DrEvil    1148
If you are going to be doing that often I would randomize the list itself and then pull from the front of it each time or something.

std::random_shuffle(_list.begin(), _list.end());
return _list.front(); // pop front also?

Share this post


Link to post
Share on other sites
Perost    332
Quote:
Original post by DrEvil
If you are going to be doing that often I would randomize the list itself and then pull from the front of it each time or something.

std::random_shuffle(_list.begin(), _list.end());
return _list.front(); // pop front also?


That won't work, random_shuffle only works on random access iterators. See here.

Share this post


Link to post
Share on other sites
suliman    1652
my plan is to "getRandomNumber(0,listSize)" and iterate with that number to find my random entry. I cannot use vectors and probably this will be fast enough becouse i dont do this to often and with to big lists.

Thanks for your help guys
Erik

Share this post


Link to post
Share on other sites
Skizz    794
If you need to traverse the list in order to get the number of elements in the list, you could use this algorithm instead:

random_element = null
current_element = head_of_list
count = 1

while current_element != null
if random < 1 / count // 0 <= random < 1
random_element = current_element

current_element = current_element->next // current_element->next returns either null for end of list or
// the next element in list
++count

return random_element

This only requires one iteration of the list to get a random element from it with uniform probability, it does not need to know beforehand the number of elements in the list.

Skizz

Share this post


Link to post
Share on other sites
Skizz    794
Incidently,

rand() % buildingList.size()

produces biased results towards the start of the list. For

rand() * buildingList.size() / MAX_RAND

the bias is distributed throughout the list rather than at the start, but is subject to overflow in the multiplication part for very large lists.

Skizz

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this