Рандомизированная очередь - это коллекция, которая предоставляет доступ к своим элементам в случайном порядке. Таким образом, каждый отдельный "взгляд" на эту коллекцию даёт случайную, независимую от других, перестановку элементов. Например, если взять два итератора на начало коллекции, а затем каждым пройти по всем элементам до конца, то эти два прохода дадут две разных, независимых друг от друга, перестановки.
Пример: исходная коллекция = 1, 2, 3, 4, 5, 6
Перестановки:
6, 2, 4, 1, 5, 3
5, 3, 2, 6, 4, 1
2, 6, 4, 5, 3, 1
Подобный код должен работать:
randomized_queue<int> q;
for (int i = 0; i < 5; ++i) {
q.enqueue(i);
}
auto b1 = q.begin();
auto e1 = q.end();
auto b2 = q.begin();
auto e2 = q.end();
std::vector<int> v11, v12;
std::copy(b1, e1, std::back_inserter(v11));
std::copy(b1, e1, std::back_inserter(v12));
assert(v11 == v12); // Два прохода одним итератором дают одинаковую последовательность
std::vector<int> v21, v22;
std::copy(b2, e2, std::back_inserter(v21));
std::copy(b2, e2, std::back_inserter(v22));
assert(v21 == v22); // Два прохода одним итератором дают одинаковую последовательность
assert(v11 != v21); // С высокой степенью вероятности, два разных итератора задают разные последовательности
// взятие итераторов не повлияло на очередь
while (!q.empty()) {
std::cout << q.dequeue() << ' ';
}Утилита, которая принимает список строк и выдаёт k из них с равномерным распределением. При этом "строка" - это произвольная последовательность печатных символов, ограниченная символом перевода строки (\n).
In: printf '%s\n' A B C D E F G H I | ./subset 3
Out:
C
G
A