Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » C++ pick a random element from a vector?

This thread is locked; no one can reply to it. rss feed Print
C++ pick a random element from a vector?
Mark Oates
Member #1,146
March 2001
avatar

simplest approach is to:

int random_int(int min, int max)
{
   return rand()%(max-min+1) + min;
}

template<class T>
T random_element(std::vector<T> &elements)
{
   return elements[random_int(0, elements.size()-1)];
}

Problem is what should the behavior be when elements is empty? I can't find a solution!

Chris Katko
Member #1,881
January 2002
avatar

Problem is what should the behavior be when elements is empty? I can't find a solution!

An exception? How is "random element" any different than trying to get the "last" element of an empty array?

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Mark Oates
Member #1,146
March 2001
avatar

any different than trying to get the "last" element of an empty array?

Oh, interesting.

Without knowing too much about this, it seems like back() just simply segfaults. I'm not to familiar with how exceptions should be used in this case.

bamccaig
Member #7,536
July 2006
avatar

An exception would be the only possible solution (short of crashing). Trying to get "any" element from an empty set is undefined. It doesn't make sense. Arguably you could return something like null/undefined in languages with first-class support for it, but that too would be likely to cause havoc. An exception makes the most sense.

Append:

To clarify, std::vector::operator[] will indeed crash here on an empty set. We're suggesting that you should throw an exception. If you use std::vector::at() instead of operator[] that will handle the bounds checking for you. For performance sensitive code crashing is probably acceptable though... Programmer should have checked...

Mark Oates
Member #1,146
March 2001
avatar

Would back() throw an exception on an empty set?

Am I creating new, non-standard behavior?

bamccaig
Member #7,536
July 2006
avatar

Mark Oates
Member #1,146
March 2001
avatar

Ok cool.

Exception would be nice.

Ariesnl
Member #2,902
November 2002
avatar

If you use a vector of pointers to the actual elements, the solution is simple..
If empty just return NULL. Besides.. sorting, iterating, searching such a vector is MUCH faster !
I don think you can do that with a template function though.. never tried

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

l j
Member #10,584
January 2009
avatar

You could add something like this for pointer types.

template <class T>
T* try_random_element(std::vector<T*> &elements)
{
  if (elements.size() == 0)
  {
    return nullptr;
  }
  else return random_element(elements);
}

C++17 may include the optional type which would be useful for this case if you don't want to use exceptions.

You might also want to consider using the C++11+ random header. It has far more options than C's rand and should also yield similar results on different compilers.

RPG Hacker
Member #12,492
January 2011
avatar

What are you intending to use this code in? Keep in mind that exceptions in C++ are slow as shit, so you really don't want to use them in code that runs every frame (or, god forbid, multiple times per frame). In that case, some kind of "error" return value, defined by you, would be favorable. Of course that is hard to do with templates, so T* might indeed be easier than T.

Audric
Member #907
January 2001

Depending on what classes you use it for, it may be more practical for the template to return "the default value of T".
For pointers it will be NULL, for numbers it will be zero.
For your own classes, it will be the result of the default constructor.

From what I read, it seems you do it by typing return T();

Peter Hull
Member #1,136
March 2001

I know that Haskell and Rust return an optional value, Python throws an error.

You could try returning an iterator rather than the value:

template <typename _Coll>
typename _Coll::const_iterator choice(const _Coll& v) {
  if (v.empty()) {
    return v.end();
  }
  else {
    return std::next(v.begin(), rand() % v.size());
  }
}

and checking it:

#SelectExpand
1int main() 2{ 3 4 std::vector<std::string> values{"Eggs", "Cheese", "Bacon", "Apples", "Soup", "Beer"}; 5 6 for (int i = 0; i < 100; ++i) { 7 auto v = choice(values); 8 if (v == values.end()) { 9 std::cout << "You are an idiot" << std::endl; 10 } 11 else { 12 std::cout << i << '\t' << *v << std::endl; 13 } 14 } 15 return 0; 16}

Also note that rand() % X is not the best way to get uniform values between 0 and X-1.

Audric
Member #907
January 2001

Also note that rand() % X is not the best way to get uniform values between 0 and X-1.

(The word you're looking for is "equiprobable")
A more likely problem is to compile the code with Microsoft's compiler, RAND_MAX is only 32767, so items above this number NEVER get randomly selected.

Chris Katko
Member #1,881
January 2002
avatar

Exceptions are relatively slow. Relative is relative.

Trying to use a method that requires elements to exist, when there are none, is a violation of the pre-conditions of the contract.

- Returning an in-stream value, null, is dangerous. It's also atypical C++, so it should be used with caution when surrounded by typical C++-code. Surrounding code is a clue to the usage of other code.

- Exceptions shouldn't be firing off every 10 frames. They should be firing off to tell you that you did something wrong at run-time. Also consider asserts. (The only time I really use exceptions is when the resource or action is truly blackboxed, like trying to access a SQL database and the database could lose connection on any call--that would be impossible to check every call before hand--it could fail between the check and the actual call!)

- Regardless of the method of error notification, it is a error condition and code should either be expected to be an impossible condition to achieve, or users should be expected to check and guarantee array size before using. Calling that function without data means that calling code block is broken.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

RPG Hacker
Member #12,492
January 2011
avatar

Exceptions are relatively slow. Relative is relative.

[...]

Exceptions shouldn't be firing off every 10 frames. They should be firing off to tell you that you did something wrong at run-time.

This is the important part here. Exceptions are fine as long as they're only thrown when an actual error condition is met, so if you define that calling random_element() on an array with a length of 0 is not an error condition, then the function definitely shouldn't throw an exception when the array is empty. Or in other words: Throwing an exception while your code is behaving "as itended" is a bad idea, at least in C++. So whether you throw an execption here or not really depends on how you define your random_element() function and what you want to achieve. Do you consider a call to this function with an empty array an error? Throw an exception. Do you consider such a call valid and want the application to respond in a specific way to it? Don't throw an exception and instead return a default value or something like that.

Throwing an exception while in a valid condition can have dramatic effects on performance if you do this every frame or even more often than that. I could experience this first-hand some time ago when coding a TMX map renderer. I used std::maps and std::vectors to hold some of my map data. Now after loading the map, I wanted to iterate over its data (don't know if it was a map or a vector, I think the former) to do some stuff with and just ignore non-existing elements. For non-existing elements, I just caught the exception that was thrown. Now I don't know how I did this back then, but I somehow managed to accidently also have this code running at runtime instead of just after map creation. The result was that the FPS in my game immediately dropped from 60 to 10 or somewhere around that. I was quite surprised, until I realised that my code was throwing dozens of exceptions each frame.

So yeah, throwing exceptions in realtime code is definitely not recommended.

bamccaig
Member #7,536
July 2006
avatar

For all intents and purposes, places where performance matters that much can spend the extra ms checking first. Or you can provide an alternative overload that doesn't throw.

The alternative is multiple return values, and the workaround in languages that don't support that is an "output" parameter:

template<typename T>
bool random_element(const std::vector<T> & v, T& element);

This has the unfortunate side-effect that the caller has to do a bit more work to set up the call, but it has the advantage that no exception is needed and it still differentiates between all possible values of the container.

int x;

if(random_element(foo, x)) {
    // x is random.
} else {
    // x is undefined.
}

An iterator may be the better solution to avoid copying if the container has heavy objects, but I think that's going to end up leading to heavy copies eventually anyway so it's probably not the place to worry about it.

Go to: