std :: shuffle не компилируется с помощью std :: list

Question

Я пытаюсь перетасовать некоторый список сгенерированных элементов. Вот код:

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); 

Это не компилируется. Вот ошибки:

/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' 

Есть ли у кого-нибудь идеи?

Answer 1

std::shuffle требует итераторов с произвольным доступом. std::list не предоставляет их. Вам нужен другой контейнер, например std::vector.

Если вам действительно нужно std::list, вам может потребоваться реализовать перетасовку в специальном алгоритме. Но сначала убедитесь, что вам это действительно нужно. Часто люди думают, что им нужно std::list, когда им действительно нужно std::vector.

Answer 2

std::list не предоставляет произвольный доступ к его элементам, которые требуются std::shuffle(). Это как подпись std::shuffle() выглядит в спецификации (пункт 25.3.12 стандарта C++):

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

Если вы можете рассмотреть возможность использования std::vector вместо этого - который, кстати, вам предлагается использовать в качестве стандартного контейнера по умолчанию по самому стандарту C++.

В качестве примера (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; } 
} 

Алгоритм std::iota() является только более простой альтернативой вашего использования std::generate.

Answer 3

[algorithms.general]/2, декларация shuffle:

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

[..]

Если параметр шаблона алгоритм, является RandomAccessIterator [..] фактический аргумент шаблона должны удовлетворять требованиям итератора с произвольным доступом (24.2.7).

Очевидно, что std::list предоставляет только двунаправленные итераторы. Попробуйте использовать контейнер, который вместо этого предоставляет итераторы с произвольным доступом.