述語を満たすイテレータから一様にランダムなコンテナからイテレータを取得する

Question

コンテナがあり、ランダムに述語を満たすイテレータを選択したいと思います。具体的に役立つ場合、コンテナはマップです。範囲内の要素の数を取得するために

std::count_if：

単純に、私はこれを言うでしょう。

ランダム番号btwn 0とnum_elements-1を選択してください。

乱数にカウントアップしてtrueを返すステートフルな述語を作るためのラムダを作成します。

std::find_ifとラムダ。

これはうまくいくでしょうか？もっと良い方法がありますか？あるいは、count_ifの代わりにcountを使用して、述語に失敗した場合に番号を再生成することもできます。述語がほとんど真実であると思われるが、私の目的のためにはうまくいかない場合に役立つだろう。

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]; 
}