Sign in to follow this  

return random element of std::list?

This topic is 4018 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
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
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
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
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
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
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

This topic is 4018 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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