Std :: shuffle not compiling with std :: list

Question

I am trying to shuffle some list of generated items. Here is the code:

std::default_random_engine generator (10);
std::list<int> list(10);

int n = 0;
std::generate(list.begin(), list.end(), [&]{ return n++; });
std::shuffle(list.begin(), list.end(), generator);

It does not compile. Here are the errors:

/include/c++/v1/algorithm:3059:34: Invalid operands to binary expression ('std::__1::__list_iterator<int, void *>' and 'std::__1::__list_iterator<int, void *>')
main.cpp:1:10: In file included from main.cpp:1:

/include/c++/v1/random:1641:10: In file included from /bin/../include/c++/v1/random:1641:

main.cpp:37:10: In instantiation of function template specialization 'std::__1::shuffle<std::__1::__list_iterator<int, void *>, std::__1::linear_congruential_engine<unsigned int, 48271, 0, 2147483647> &>' requested here
/include/c++/v1/iterator:622:1: Candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
/include/c++/v1/iterator:1017:1: Candidate template ignored: could not match 'move_iterator' against '__list_iterator'
/include/c++/v1/iterator:1369:1: Candidate template ignored: could not match '__wrap_iter' against '__list_iterator'
/include/c++/v1/string:486:11: Candidate template ignored: could not match 'fpos' against '__list_iterator'

Does anyone have any ideas?

Answer 1

std::listdoes not provide random access to its elements that are required std::shuffle(). This is the signature std::shuffle()in its specification (paragraph 25.3.12 of the C ++ standard):

template<class RandomAccessIterator, class UniformRandomNumberGenerator>
void shuffle(RandomAccessIterator first,
             RandomAccessIterator last,
             UniformRandomNumberGenerator&& g);

If you can, consider using std::vectorinstead, which, by the way, you are advised to use as the default default container with the C ++ standard itself.

( Coliru):

int main()
{
    std::default_random_engine generator(10);
    std::vector<int> v(10);

    std::iota(begin(v), end(v), 0);
    std::shuffle(begin(v), end(v), generator);

    for (auto x : v) { std::cout << x; }
}

std::iota() - std::generate.

Answer 2

std::shuffle . std::list . , std::vector.

std::list, . , . , std::list, std::vector.

Answer 3

[algorithmms.general]/2, shuffle:

template<class RandomAccessIterator, class UniformRandomNumberGenerator>
void shuffle(RandomAccessIterator first, RandomAccessIterator last,
              UniformRandomNumberGenerator&& rand);

[..]

RandomAccessIterator [..] (24.2.7).

Clearly, it std::listprovides only bidirectional iterators. Try using a container that provides random access iterators instead.