access random item in std::list?
Author
hi
is there any way to get a random object from a std::list like:
unit * u;
u=myUnitList.getRandom();
There is a way, but you will have to code it yourself. However, it's nothing difficult: off the top of my head, the following should work.
Here, random is a functor or function that takes a number N as argument, and returns a number between 0 and N inclusive with whatever random distribution suits you. list is any container which supports size, begin and iterator.
template<typename T, typename F>typename T::iterator& get_random(T & list,const F & random){ return std::advance(list.begin(),random(0,list.size()-1));}Here, random is a functor or function that takes a number N as argument, and returns a number between 0 and N inclusive with whatever random distribution suits you. list is any container which supports size, begin and iterator.
Author
im new to this templetes... How would i use it to do what i wrote about (unit * u should point to the random unit from the list) What is the actual call?
just understand your problem is 2 completely seperable pieces:
1. How to choose a random item of the list you want to retrieve. This is basically nothing more than using a random number generator to get a number between 0 and size()-1 of the list.
2. How to get a specific indexed item out of a std::list (basically how to get random_access like behavior from a std::list with no built in support for index subscripts).
for number 1, something like:
int selectedIndex = rand() % myUnitList.size();
for number 2, something like:
typedef std::list<unit*> UnitList; // change this line to reflect your real types, this is just for illustration purposes.
UnitList::iterator unitIterator = advance(myUnitList.begin(), selectedIndex);
unit *u = *unitIterator;
or rewritten without the typedef and iterator type mentioned:
int unitIndex = rand() % myUnitList.size();
unit *u = *advance(myUnitList.begin(), unitIndex);
1. How to choose a random item of the list you want to retrieve. This is basically nothing more than using a random number generator to get a number between 0 and size()-1 of the list.
2. How to get a specific indexed item out of a std::list (basically how to get random_access like behavior from a std::list with no built in support for index subscripts).
for number 1, something like:
int selectedIndex = rand() % myUnitList.size();
for number 2, something like:
typedef std::list<unit*> UnitList; // change this line to reflect your real types, this is just for illustration purposes.
UnitList::iterator unitIterator = advance(myUnitList.begin(), selectedIndex);
unit *u = *unitIterator;
or rewritten without the typedef and iterator type mentioned:
int unitIndex = rand() % myUnitList.size();
unit *u = *advance(myUnitList.begin(), unitIndex);
Author
the first
gameItem * g=get_random(blackMarket.itemList);
the second
int unitIndex = rand() % blackMarket.itemList.size();
unit *u = *std::advance(blackMarket.itemList.begin(), unitIndex);
"cannot convert parameter 1 from 'class gameItem *' to 'class gameItem *& "
i dont get it to work...
gameItem * g=get_random(blackMarket.itemList);
the second
int unitIndex = rand() % blackMarket.itemList.size();
unit *u = *std::advance(blackMarket.itemList.begin(), unitIndex);
"cannot convert parameter 1 from 'class gameItem *' to 'class gameItem *& "
i dont get it to work...
template<typename list_type>list_type::iterator get_random_element( list_type& list ) { int random_element_number = 4; {for(list_type::iterator it = list.begin(); it != list.end(); ++it ) { --random_element_number; if (random_element_number == 0) return it; }} return list.end();}template<typename list_type>list_type::const_iterator get_random_element( list_type const& list ) { int random_element_number = 4; {for(list_type::const_iterator it = list.begin(); it != list.end(); ++it ) { --random_element_number; if (random_element_number == 0) return it; }} return list.end();}The hard part, as with all random selections, is actually figuring out what you mean by random, and then generating it.
List can only be read linearly, so getting an element out of the middle takes on average O(N) time.
[Edited by - NotAYakk on March 8, 2007 3:00:13 PM]
if it's a big list and it's not changing much, vector would probably be faster for random access.
and if list is changing more than just rarely on ends, but you want random access, then std::deque is your choice:
std::list - for linear access, running down all items in list (like doing unit.update() on each unit). Good at adding and removing anywhere
std::vector - for most efficient random access. really bad at adding / removing anywhere but end(), somewhat ok at adding to end().
std::deque - for middle ground, great at random access, good at adding / removing at either end, not abysmal at adding in middle.
std::list - for linear access, running down all items in list (like doing unit.update() on each unit). Good at adding and removing anywhere
std::vector - for most efficient random access. really bad at adding / removing anywhere but end(), somewhat ok at adding to end().
std::deque - for middle ground, great at random access, good at adding / removing at either end, not abysmal at adding in middle.
Author
ok but my problem is i dont know how to call these functions, as i said:
the first
gameItem * g=get_random(blackMarket.itemList); //i abviously do something wrong
the second
int unitIndex = rand() % blackMarket.itemList.size();
unit *u = *std::advance(blackMarket.itemList.begin(), unitIndex);
//"cannot convert parameter 1 from 'class gameItem *' to 'class gameItem *& "
i dont get it to work...
the first
gameItem * g=get_random(blackMarket.itemList); //i abviously do something wrong
the second
int unitIndex = rand() % blackMarket.itemList.size();
unit *u = *std::advance(blackMarket.itemList.begin(), unitIndex);
//"cannot convert parameter 1 from 'class gameItem *' to 'class gameItem *& "
i dont get it to work...
template<typename T, typename F>typename T::iterator& get_random(T & list,const F & random){ return std::advance(list.begin(),random(0,list.size()));}int random(int min, int max){ assert (max > min); return std::rand() % (max - min) + min;;}std::list<unit*> units;unit* u = *get_random(units,random);[Edited by - ToohrVyk on March 9, 2007 2:22:05 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
