11

C ++ 11の可変個引数テンプレートを使用して、一般化された「ランダムピッカー」機能を実現したいと思います。

このようなもの...

template <typename T>
T randomPicker(T one, T two, T three)
{
    int pick = 3 * (rand() / double(RAND_MAX));
    switch (pick)
    {
        case 0:
            return one;
        case 1:
            return two;
        default:
            return three;
    }
}

...任意の数のパラメーターを受け入れるように一般化されている場合を除きます（上記のように、それぞれ同じタイプですが、パラメーターとして任意のタイプを受け入れ、返されたときに選択したタイプを特定のタイプTに変換することもできます）。

テンプレート再帰を使用してtypesafeprintfなどを実現するという考えを理解しています。可変個引数テンプレートを使用して、上記のような関数を作成することもできますか？ヒントをいただければ幸いです。

4

5 に答える 5

8

可変個引数テンプレートを使用する必要があるかどうかはわかりませんが、初期化子リストを使用する方が簡単です。

#include <cstddef>
#include <iostream>
#include <random>
#include <algorithm>
#include <initializer_list>
using namespace std;

template <class T>
T random_picker(initializer_list<T> container){
    static default_random_engine re;
    uniform_int_distribution<size_t> range{0, container.size()-1};
    auto random_iterator = container.begin();
    advance(random_iterator, range(re));
    return *random_iterator;
}

int main(){
    for(size_t i = 0; i < 10; ++i)
        cout << random_picker({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) << endl;
}
于 2011-11-09T23:57:03.863 に答える
8

Something like this, although I can't test it:

template <typename First, typename... Others>
First randompicker(First first, Others ...args) {
    const size_t len = sizeof...(args) + 1;
    if (rand() / double(RAND_MAX) < 1.0 / len) {
        return first;
    }
    return randompicker(args...);
}

template <typename Only>
Only randompicker(Only only) {
    return only;
}

I'm not sure whether the overload there is right -- presumably a parameter pack can be empty, I don't know whether I can still overload for one argument without ambiguity.

Admittedly this uses more random numbers than your example with 3 args, and may be more sensitive to bias from rounding errors. So, you could pick a random number from 0 to len-1 at the start, and then call a recursive function that selects the nth argument out of the parameter pack:

template <typename First, typename... Others>
First select(size_t idx, First first, Others ...args) {
    if (idx == 0) return first;
    return select(idx-1, args...);
}

template <typename Only>
Only select(size_t, Only only) {
    return only;
}

template <typename First, typename... Others>
First randompicker(First first, Others ...args) {
    static std::default_random_engine re;

    const size_t len = sizeof...(args) + 1;
    std::uniform_int_distribution<size_t> range{0, len - 1};

    const size_t idx = range(re);
    return select(idx, first, args...);
}

In all cases, I have n if/else statements instead of an n-way switch. You might be lucky with the optimizer, or you might be able to "unroll the loop" a bit by having First, Second ... A few parameter args before the variable args.

于 2011-11-09T23:12:40.450 に答える
3

1 つの方法は、次のようなことです。

template<typename T, typename... Args>
T randomPicker(T first, Args ...rest) {
    T array[sizeof...(rest) + 1] = {first, rest...};

    return array[rand() % (sizeof...(rest) + 1)];
}

IdeOne でテスト済み

于 2011-11-09T23:11:07.740 に答える
2

これはうまくいくはずです。 randomPickerどのパラメータを返すかを選択します。 randomPicker_impl正しいものが選択されるまで、パラメータを処理します。のオーバーロードLastにより、テンプレートの展開が確実に終了します。

完全な動作コードはこちら: ideone.com/2TEH1

template< typename Ret, typename Last >
Ret random_picker_impl( size_t i, Last&& last )
{
   return std::forward<Last>(last);
}

template< typename Ret, typename First, typename Second, typename ... Rest >
Ret random_picker_impl( size_t i, First&& first, Second&& second, Rest&&... rest )
{
   if( i == 0 )
   {
      return std::forward<First>(first);
   }
   else
   {
      return random_picker_impl<Ret>( i-1, std::forward<Second>(second), std::forward<Rest>(rest)... );
   }
}

template< typename First, typename ... Rest >
First random_picker( First&& first, Rest&&... rest )
{
   size_t index = (sizeof...(rest) + 1) * (std::rand() / double(RAND_MAX));
   return random_picker_impl<First>( index, std::forward<First>(first), std::forward<Rest>(rest)... );
}
于 2011-11-09T23:54:33.373 に答える
0

リンクされたリストのランダムな要素を選択する通常の方法は、1/1、1/2、1/3、...、1/n の確率で、選択した要素を各リンクの現在の要素に置き換えることです。

#include <cstdlib>
#include <ctime>
#include <iostream>

namespace {
template<typename T>
T randomPickerHelper(int& sz, T first) {
    return first;
}
template<typename T, typename ...Args>
T randomPickerHelper(int& sz, T first, Args ...rest) {
    T next = randomPickerHelper(sz, rest...);
    return std::rand() % ++sz ? next : first;
}
}

template<typename T, typename... Args>
T randomPicker(T first, Args ...rest) {
    int sz = 1;
    return randomPickerHelper(sz, first, rest...);
}

int main() {
    std::srand(std::time(0));
    for (int i = 0; i < 1000000; ++i) {
        std::cout << randomPicker(1, 2, 3, 4, 5) << std::endl;
    }
    return 0;
}

何度も電話rand()するけど。

template<typename T, typename ...Args>
struct Count {
    static const int sz = Count<Args...>::sz + 1;
};
template<typename T>
struct Count<T> {
    static const int sz = 1;
};

template<typename T>
T pick(int n, T first) {
    return first;
}

template<int N, typename T, typename ...Args>
T pick(int n, T first, Args ...rest) {
    if (n == Count<T, Args...>::sz) {
        return first;
    }
    return pick(n, rest...);
}

template<typename T, typename ...Args>
T randomPicker(T first, Args ...rest) {
    return pick(std::rand() % Count<T, Args...>::sz + 1, first, rest...);
}

これは可能だと思いますが、GCC 4.6.0 は展開をサポートしていません<Args...>。

于 2011-11-10T00:04:13.033 に答える