What containers are valid to use with std::random_shuffle( RandomIt first, RandomIt last )?
The API description says the two iterators need to be random-access iterators -- I guess I'm not clear what a random-access iterator is, and specifically, why std::vector::begin() and ::end() are, but the same from std::set and std::unordered_set are not.
#include <algorithm>
#include <set>
#include <unordered_set>
#include <vector>
int main( int argc, char* argv[] )
{
std::set<int> s = { 1, 2, 3, 4, 5 };
std::unordered_set<int> u = { 1, 2, 3, 4, 5 };
std::vector<int> v = { 1, 2, 3, 4, 5 };
std::random_shuffle( s.begin(), s.end() ); // compile error
std::random_shuffle( u.begin(), u.end() ); // compile error
std::random_shuffle( v.begin(), v.end() ); // :)
return 0;
}
If you look at set then down to iterator class member it will tell you the iterator type, in this case BidirectionalIterator. (The "legacy" bit can be disregarded for this purpose).
For random_shuffle it needs to be RandomAccessIterator which means the iterator can be moved in jumps of any integer size (or in other words, the container elements can be accessed in constant time by an integer index).
This is possible for vector (offset by an index from the start), but not possible for set where the only way to get to the N-th element is to traverse the elements one step at a time (because it's stored as a tree).
More info about iterators: Types of iterator : Output vs. Input vs. Forward vs. Random Access Iterator
I couldn't find a table in the Standard of containers vs. iterator types, however if you look at this container property table then any container that supports operator[] for an integer index is random access, otherwise it isn't. So that is <array>, <vector> and <deque>. (The maps use operator[] in a different way). Also there is <string> which doesn't appear in that table, plus any user-defined container which offers random access iterators of course.
NB. set is a sorted container so it couldn't be random-shuffled anyway.