std::shuffle doesn't compile with std::list

Question

I'm trying to shuffle some list of generated elements. 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 doens't 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 anybody have any idea?

Answer 1

std::list does not provide random access to its elements, which std::shuffle() requires. This is how the signature of std::shuffle() looks like 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 an std::vector instead - which, by the way, you are encouraged to use as the default sequential container by the C++ Standard itself.

As an example (live demo on 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; }
}

The std::iota() algorithm is just a simpler alternative to your particular usage of std::generate.

Answer 2

std::shuffle requires random access iterators. std::list doesn't provide those. You need a different container, such as std::vector.

If you really need std::list, you may need to implement the shuffling in a dedicated algorithm. But first make sure you really need it. Often times people think they need std::list when they really need std::vector.

Answer 3

[algorithms.general]/2, declaration of shuffle:

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

[..]

If an algorithm’s template parameter is RandomAccessIterator [..] the actual template argument shall satisfy the requirements of a random-access iterator (24.2.7).

Clearly std::list only provides bidirectional iterators. Try to use a container that does provide random-access iterators instead.

Answer 4

AndyProwl correctly explains why the code doesn't compile, and notes that it's often more appropriate to use a std::vector than a std::list. However, juanchopanza scaremongers slightly in his claim that shuffling a std::list requires a dedicated algorithm. In fact, it is easy to shuffle a std::list using std::shuffle, by way of an intermediate vector of references (and using the move constructor, if appropriate):

#include <numeric>
#include <random>

template <typename T, typename URBG>
void shuffle(std::list<T>& l, URBG&& urbg)
{
    std::vector<std::reference_wrapper<const T>> v(l.begin(), l.end());
    std::shuffle(v.begin(), v.end(), urbg);
    std::list<T> shuffled;
    for (auto &ref : v) shuffled.push_back(std::move(ref.get()));
    l.swap(shuffled);
}

int main()
{
    std::list<int> l(10);
    std::iota(l.begin(), l.end(), 0);
    shuffle(l, std::mt19937{ std::random_device{}() });
    for (auto x : l) std::cout << x << " ";
}

In fact, we can do even better: since it is possible to move elements between lists without invalidating iterators or references, we can even shuffle lists of objects that are neither copyable nor movable, and (more significantly perhaps) also ensure that shuffling preserves references to list elements.

template <typename T, typename URBG>
void shuffle(std::list<T>& l, URBG&& urbg)
{
    std::vector<std::list<T>::const_iterator> v;
    for (auto it = l.cbegin(); it != l.cend(); ++it) v.push_back(it);
    std::shuffle(v.begin(), v.end(), urbg);
    std::list<T> shuffled;
    for (auto &it : v) shuffled.splice(shuffled.end(), l, it);
    l.swap(shuffled);
}

Of course both these solutions have an O(n) space overhead for the vector of references (or iterators). If that's a problem then you can implement a slower O(n log n) time algorithm that uses just O(1) space, as described here. Though you'd probably save more space by switching to std::forward_list anyway.