Почему образец не заполняет мой вектор случайным образом?

Question

Я экспериментировал с игрушкой sample Программа:

map<int, char> foo { { 1, 'a' }, { 2, 'b' }, { 3, 'c' } };
vector<pair<decltype(foo)::key_type, decltype(foo)::mapped_type>> bar(size(foo));

sample(begin(foo), end(foo), begin(bar), size(foo), mt19937{ random_device{}() });

Живой пример

Но bar всегда содержит содержимое foo по порядку. Это проблема реализации gcc, или мне просто не везет?

Answer 1

Выборка - это возвращение некоторого подмножества большей популяции.

Он не предназначен для возврата элементов в случайном порядке или в любом другом порядке. Это может , но это не совсем то, для чего оно существует.

cppreference намекает на порядок в этом утверждении:

Алгоритм стабилен, только если PopulationIterator отвечает требованиям ForwardIterator

«Стабильный» в данном случае означает, что он будет возвращать результаты в том же порядке, что и входные данные, поэтому порядок гарантированно , а не будет случайным с ForwardIterator . По теме: Что такое стабильность в алгоритмах сортировки и почему это важно?

Это также имеет смысл, поскольку, подобно тому, что было отмечено в комментариях, чтобы быть эффективным, вам сначала нужно выяснить, какие элементы выбрать, а затем пройти через итератор и выбрать элементы, так как вы можете итерация только от одного направления к другому. Таким образом, это должно быть тривиально, чтобы держать элементы в том же порядке.

Что касается , когда вы не используете ForwardIterator, он не дает никаких гарантий относительно заказа в ту или иную сторону. Таким образом, даже если это может показаться случайным образом упорядоченным, было бы неразумно полагаться на это, поскольку случайность упорядочения может зависеть от реализации и может иметь или не иметь высокую энтропию .

Если вы хотите случайный заказ, вы должны shuffle it.

Answer 2

std::sample выбирает элементы из диапазона, который вы передаете. От cppreference (выделите мое):

Выбирает n элементов из последовательности [first; последний) такой, что каждый возможная выборка имеет равную вероятность появления, и записывает те Выбранные элементы в выходной итератор вышли. Случайные числа генерируется с помощью генератора случайных чисел г.

Если n больше, чем количество элементов в последовательности, выбираются последние-первые элементы.

Я думаю, что документы могли бы быть более понятными, но возвращать только last-first, если количество запрашиваемых элементов больше, имеет смысл, только если каждый элемент выбран максимум один раз.

Попробуйте:

map<int, char> foo { { 1, 'a' }, { 2, 'b' }, { 3, 'c' } };
vector<pair<decltype(foo)::key_type, decltype(foo)::mapped_type>> bar(size(foo)-1);

sample(begin(foo), end(foo), begin(bar), bar.size(), mt19937{ random_device{}() });

чтобы получить две случайные выборки из foo.

Также обратите внимание, что

Алгоритм стабилен, только если PopulationIterator соответствует требования ForwardIterator

то есть не просто не повезло, что вы всегда получали один и тот же результат.