return random element of std::list?
Author
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
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.
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.
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?
std::random_shuffle(_list.begin(), _list.end());
return _list.front(); // pop front also?
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.
Author
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
Thanks for your help guys
Erik
If you need to traverse the list in order to get the number of elements in the list, you could use this algorithm instead:
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
random_element = nullcurrent_element = head_of_listcount = 1while 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 ++countreturn random_elementThis 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
std::list<building *> buildingList;
std::list<building *>::iterator it = buildingList.begin();
std::advance( it, rand() % buildingList.size() );
// use *it
std::list<building *>::iterator it = buildingList.begin();
std::advance( it, rand() % buildingList.size() );
// use *it
Incidently,
produces biased results towards the start of the list. For
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
rand() % buildingList.size()produces biased results towards the start of the list. For
rand() * buildingList.size() / MAX_RANDthe 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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
