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

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...

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

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.

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:

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

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.

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.