Рандомизированная очередь

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

Пример: исходная коллекция = 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() << ' ';
}

Клиентская программа subset

Утилита, которая принимает список строк и выдаёт k из них с равномерным распределением. При этом "строка" - это произвольная последовательность печатных символов, ограниченная символом перевода строки (\n).

In: printf '%s\n' A B C D E F G H I | ./subset 3 Out:

C
G
A