Jump to content
  • Advertisement
Sign in to follow this  
suliman

access random item in std::list?

This topic is 4212 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 to get a random object from a std::list like: unit * u; u=myUnitList.getRandom();

Share this post


Link to post
Share on other sites
Advertisement
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.


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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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);

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites



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]

Share this post


Link to post
Share on other sites
if it's a big list and it's not changing much, vector would probably be faster for random access.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!