std:: random_shuffle, std:: shuffle

주어진 범위 [ first , last ) 내의 요소들을 재정렬하여, 해당 요소들의 가능한 모든 순열이 동일한 확률로 나타나도록 합니다.

만약 * first 의 타입이 Swappable 가 아니라면 (C++11 이전) RandomIt 이 ValueSwappable 가 아니라면 (C++11 이후) 동작은 정의되지 않습니다.

매개변수

복잡도

정확히 std:: distance ( first, last ) - 1 번의 교환.

가능한 구현

다음 구현도 참조하십시오: libstdc++ 와 libc++ .

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[std::rand() % (i + 1)]);
        // rand() % (i + 1)는 실제로 올바르지 않습니다. 생성된 숫자가 대부분의 i 값에 대해
        // 균일하게 분포되지 않기 때문입니다. 올바른 코드는 C++11 std::uniform_int_distribution
        // 구현의 변형이어야 합니다.
    }
}

template<class RandomIt, class RandomFunc>
void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[r(i + 1)]);
    }
}

template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    typedef std::uniform_int_distribution<diff_t> distr_t;
    typedef typename distr_t::param_type param_t;
    distr_t D;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

참고 사항

구현은 표준에 의해 규정되지 않으므로, 동일한 RandomFunc 또는 URBG (균일 난수 생성기)를 사용하더라도 다른 표준 라이브러리 구현에서 다른 결과를 얻을 수 있습니다.

C++17에서 std::random_shuffle 을 제거한 이유는 반복자만 사용하는 버전이 일반적으로 std::rand 에 의존하기 때문이며, 이제 std::rand 도 사용 중단이 논의되고 있습니다. ( std::rand 는 유해한 것으로 간주되므로 <random> 헤더의 클래스들로 대체되어야 합니다.) 또한 반복자만 사용하는 std::random_shuffle 버전은 일반적으로 전역 상태에 의존합니다. std::shuffle 의 셔플 알고리즘이 세 번째 매개변수로 URBG 를 사용하므로 권장되는 대체 방법입니다.

예제

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(v.begin(), v.end(), g);
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

8 6 10 4 2 3 7 1 9 5

결함 보고서

다음의 동작 변경 결함 보고서들은 이전에 발표된 C++ 표준에 소급 적용되었습니다.

1. ↑ 오버로드 (3) 는 동일한 결함을 가지고 있지만, 해당 결의안 부분은 C++98에 적용되지 않습니다.

참고 항목