CODEWITHSUNDEEP
c++liststdshuffle
thursdaysDove
thursdaysDove

Reputation: 552

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

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?

Upvotes: 6

Views: 4209

Answers (4)

Uri Granta
Uri Granta

Reputation: 1904

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.

Upvotes: 1

Andy Prowl
Andy Prowl

Reputation: 126452

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.

Upvotes: 14

juanchopanza
juanchopanza

Reputation: 227438

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.

Upvotes: 9

Columbo
Columbo

Reputation: 60999

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

Upvotes: 3

Related Questions