Получите итератор из контейнера равномерно случайным от итераторов, которые удовлетворяют предикату

Question

У меня есть контейнер, и я бы хотел выбрать итератор, который бы случайно использовал предикат. Если это помогает быть конкретным, контейнер представляет собой карту.

наивности, я бы сказал так:

std::count_if, чтобы получить число элементов в диапазоне.

Выберите случайное число btwn 0 и num_elements-1.

Создайте лямбду, чтобы создать предикат с состоянием, который подсчитывает до случайного числа и возвращает только true.

std::find_if с лямбда.

Будет ли это работать, и есть ли лучший способ? В качестве альтернативы, я мог бы использовать count вместо count_if и регенерировать число, если он прервал предикат. Может быть полезно, если предикат в основном верен, я полагаю, но не буду работать хорошо для моих целей.

Answer 1

Вы можете обменять память на производительность, сохраняя все итераторы, для которых предикат является истинным в отдельном контейнере, а затем используйте случайное число, чтобы выбрать из него итератор. Таким образом, вам нужно перебирать последовательность только один раз (обратите внимание, однако, что вам по-прежнему нужен итератор вперед, поскольку сохраненные итераторы ввода будут недействительными, как только вы перейдете к следующему элементу). Например:

template<typename ForwardIterator, typename Predicate> 
    ForwardIterator random_iterator(ForwardIterator first, 
            ForwardIterator last, 
            Predicate pred) 
{ 
    // store iterators to elements where the predicate is true 
    std::deque<ForwardIterator> store; 
    for (; first != last; ++first) 
    if pred(*first) 
     store.push_back(first); 

    // if no element satisfies the predicate, return last 
    if (store.size() == 0) 
    return last; 

    // get a random number in range [0, store.size()) 
    int rand = get_random_number(store.size()); 

    // return the corresponding iterator 
    return store[rand]; 
}