std::random_shuffle, std::shuffle
cppreference.net에서
(에서 넘어옴: cpp/algorithm/shuffle)
| 헤더에 정의됨 <algorithm>
|
||
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
|
(1) | (C++14에서 폐기됨) (C++17에서 제거됨) |
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
|
(2) | (C++11까지) |
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );
|
(C++11부터) (C++14에서 폐기됨) (C++17에서 제거됨) |
|
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
|
(3) | (C++11부터) |
주어진 범위의 요소들을 재배열하여 [first, last)각 가능한 순열이 동일한 확률로 나타나도록 합니다.
1) 난수 소스는 구현 정의되지만, 함수 std::rand가 자주 사용됩니다.
2) 난수 소스는 함수 객체
r. 다음 조건 중 하나라도 만족하면, 동작은 정의되지 않습니다:
- 의 반환 타입이
r로 변환 가능하지 않은 경우std::iterator_traits<RandomIt>::difference_type. - 양의 값
n타입의std::iterator_traits<RandomIt>::difference_type, 의 결과가r(n)구간 에서 무작위로 선택된 값이 아닌 경우[0,n).
3) 난수 소스는 객체
g. 타입
T을 std::remove_reference_t<URBG>로 할 때, 다음 조건 중 하나라도 만족하면, 동작은 정의되지 않습니다:
|
(C++20까지) |
만약 의 타입이 *first가 아닌 경우Swappable(C++11까지)RandomIt가 아닌 경우ValueSwappable(C++11부터), 동작은 정의되지 않습니다.
매개변수
| first, last | - | 무작위로 섞을 요소들의 범위를 정의하는 반복자 쌍 |
| r | - | 무작위로 선택된 값을 반환하는 함수 객체 |
| g | - | 무작위로 선택된 값을 반환하는 생성기 객체 |
| 타입 요구 사항 | ||
-RandomIt는 다음 요구 사항을 충족해야 합니다: LegacyRandomAccessIterator.
| ||
복잡도
정확히 std::distance(first, last) - 1번의 교환이 이루어집니다.
가능한 구현
다음 구현도 참조하십시오: libstdc++ 및 libc++.
| random_shuffle (1) |
|---|
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) is not actually correct, because the generated number is
// not uniformly distributed for most values of i. The correct code would be
// a variation of the C++11 std::uniform_int_distribution implementation.
}
}
|
| random_shuffle (2) |
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)]);
}
}
|
| shuffle (3) |
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(균일 난수 생성기)를 사용하더라도 다른 표준 라이브러리 구현에서 다른 결과를 얻을 수 있습니다.
제거된 이유는 std::random_shuffle가 C++17에서 제거된 이유는 반복자 전용 버전이 일반적으로 std::rand에 의존하며, 이는 현재 폐기 논의 중이기 때문입니다. (std::rand는 <random> 헤더의 클래스로 대체되어야 합니다. std::rand는 유해한 것으로 간주됩니다.) 또한, 반복자 전용 std::random_shuffle 버전은 일반적으로 전역 상태에 의존합니다. std::shuffle's shuffle algorithm is the preferred replacement, as it uses a URBG as its 3rd parameter.
예제
다음 시퀀스 [1, 10]의 정수들을 무작위로 섞습니다:
이 코드 실행
#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++ 표준에 소급하여 적용되었습니다.
| DR | 적용 대상 | 발행 당시의 동작 | 올바른 동작 |
|---|---|---|---|
| LWG 395 | C++98 | 오버로드 (1)의 난수 소스가 명시되지 않았고,(1) std::rand 는 C 라이브러리 요구 사항 때문에 소스가 될 수 없었습니다.구현 정의이며, |
std::rand 사용이 허용됩니다.LWG 552( |
| N2423 )C++98오버로드 (2)의 난수 소스가 |
일 필요가 없었습니다. | r필요함↑오버로드 (3)에도 동일한 결함이 있지만, 해당 해결 부분은 C++98에 적용되지 않습니다.[] |
같이 보기
| 범위의 요소들의 다음으로 큰 사전식 순열을 생성합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
| 범위의 요소들의 다음으로 작은 사전식 순열을 생성합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
(C++20) |
범위의 요소들을 무작위로 재배열합니다 (알고리즘 함수 객체) |