Sign in to follow this  

access random item in std::list?

This topic is 3934 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

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
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
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
there is some problem with the casting and i dont get it to work. And i need it to return a pointer anyway, so I tried to fix it and clean it up, but it doesnt work... (slump is my random int generator)


template<typename T>
typename T* getRandom(T & list)
{
return= std::advance(list.begin(),slump(0,list.size()));
}

unit * u = getRandom(unitList);





//initializing' : cannot convert from 'class std::list<class unit *,class std::allocator<class unit *> > *' to 'class unit *'

Share this post


Link to post
Share on other sites
Quote:
Original post by suliman
there is some problem with the casting and i dont get it to work. And i need it to return a pointer anyway, so I tried to fix it and clean it up, but it doesnt work... (slump is my random int generator)

template<typename T>
typename T* getRandom(T & list)
{
return= std::advance(list.begin(),slump(0,list.size()));
}

unit * u = getRandom(unitList);


//initializing' : cannot convert from 'class std::list<class unit *,class std::allocator<class unit *> > *' to 'class unit *'


This happens because you changed the code without understanding what it does. In my code, T is a container type (list, vector, deque). You kept this property by keeping the argument T & list. So, your modified function returns a pointer to a list. See where the contradiction is?

My original code returned an iterator inside the list. This allows me to avoid having to look into the type of the list to determine what kind of object it contains. This makes the code simpler and also lets it work with less effort on other containers (should you, for instance, use a vector instead of a list). Besides, your code assumes that the function would somehow return a pointer, because you know that your list contains pointers — but, again, you're losing genericity since you'll have to write a non-pointer version for other list types.

In short, keep the function general (although you may specialize the random number generator if you wish) and dereference the returned iterator to get the element.

template<typename Container>
typename Container::iterator & getRandom(Container & list)
{
return std::advance(list.begin(),slump(0,list.size()));
}

unit * u = * getRandom(unitList);

Share this post


Link to post
Share on other sites
still doesnt work, even if not changing anything. And the earlier version didnt compile either, thats why i starting changing it in the first place. I now try your:

template<typename Container>
typename Container::iterator & getRandom(Container & list)
{
return std::advance(list.begin(),slump(0,list.size()));
}

unit * u = * getRandom(unitList); //call


If i include the call the compiler gives me
return' : cannot convert from 'void' to 'class std::list<class unit *,class std::allocator<class unit *> >::iterator &'

on the return line. But if i make no call the compiler gives no errors. So there's still something wrong here...

Thanks for helping out
Erik

Share this post


Link to post
Share on other sites
You're right, there was an incorrect part in my code. It should have been:

template<typename Container>
typename Container::iterator getRandom(Container & list)
{
typename Container::iterator it = list.begin();
std::advance(it,slump(0,list.size()));
return it;
}

unit * u = * getRandom(unitList);


[EDIT] Forgot to remove the darned reference as well.

Share this post


Link to post
Share on other sites
I LOVE LOVE LOVE template!

but is there something wrong with the SIMPLE solutions I posted? Here it is again:

int unitIndex = rand() % myUnitList.size();
unit *u = *advance(myUnitList.begin(), unitIndex);

You're jut spending so much trouble getting a generic version of something working. Get the non-generic verion working and understood, then make the generic version. Most people don't write a generic tree class, till they know how to write a tree class, etc.

Share this post


Link to post
Share on other sites
dont know why but it crashes when doing it on a (working and tested) list and on a working vector it doesnt crash but returns a bugged pointer to some random data (points not to a real pointer). Same problem with my test:

template<typename Container>
typename Container::iterator & getRandom(Container & list)
{
typename Container::iterator it = list.begin();
int n=slump(0,list.size()-1);
for(int ii=0;ii<n;ii++)
it++;
return it;
}


BUT: This below works, but its not very generic. Its not even a function. It should be kinda the same thing, only this works, the other doesnt. And im not sure why not...

int n=slump(0,unitList.size()-1);
std::list<unit*>::iterator it = unitList.begin();
for(int ii=0;ii<n;ii++)
it++;
unit * u = *it;

Share this post


Link to post
Share on other sites

This topic is 3934 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