関数を要素とするstd::vectorを作りたい

Question

ソートアルゴリズムを色々と自作して比較しています(SelectionSort, InsertionSort, QuickSort, MergeSort, BubbleSort, std::sort, std::stable_sort)。
自作のもののシグネチャはいずれも下記と同様です。

template<class Iterator, class Compare>
void SelectionSort(Iterator begin, Iterator end, Compare comp)

それぞれの実行時間と内部でのcompの呼び出し回数を調べるために、下記のようなコードを関数の数だけ書いています。
関数名にまつわる部分を除けばほとんど同じなので、std::vectorに関数をまとめてstd::vector<func> functions{SelectionSort, InsertionSort}のようにループを回したいです。
どうvectorを書けば動くのでしょうか?

    auto list{unsorted_list};
    int selection_cnt = 0;
    auto selection_time = MeasureRuntime([&list, &selection_cnt]() {
      return SelectionSort(std::begin(list),
                           std::end(list),
                           [&selection_cnt](const int &lhs, const int &rhs) {
                             ++selection_cnt;
                             return lhs < rhs;
                           });
    });

コード全文 [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

---

追記

下記のようにfunctionを試してみたのですが、エラーになります。

using Iterator = std::vector<int>::iterator;
using Compare = std::function<bool(int, int)>;

int main() {
  std::vector<std::function<void(Iterator, Iterator, Compare)>> functions{SelectionSort, std::sort};
}

Answer 1

ソート関数群

template<class Iterator, class Compare>
void SelectionSort(Iterator begin, Iterator end, Compare comp) {
    for (auto it = begin; it != end; ++it) {
        auto min = std::min_element(it, end, comp);
        std::iter_swap(it, min);
    }
}

template<class Iterator, class Compare>
void InsertionSort(Iterator begin, Iterator end, Compare comp) {
    for (auto it = begin; it != end; ++it) {
        auto following = std::upper_bound(begin, it, *it, comp);
        std::rotate(following, it, std::next(it));
    }
}

に対して，

using Iter = std::vector<int>::iterator;
using CmpFun = std::function<bool(const int &, const int &)>;

std::vector< void(*)( Iter,Iter,CmpFun ) > V
{
    SelectionSort< Iter,CmpFun >,
    InsertionSort< Iter,CmpFun >
};

//Vを使ってみる
std::vector<int> Unsorted{ 3,9,0,8,3,1 };
for( auto f : V )
{
    auto Vals = Unsorted;
    int counter = 0;
    f( Vals.begin(), Vals.end(), [&counter]( const int &lhs, const int &rhs )->bool{    ++counter;  return lhs<rhs; } );

    for( auto v: Vals ){    std::cout << v << ", "; }
    std::cout << "\ncounter=" << counter << std::endl;
}

みたいなことでしょうか．

---

追記：
処理速度に関しては，std::functionじゃなくて，比較処理者を具体的に用意して与えれば改善するのかも？

//比較処理者
class Cmp
{
public:
    Cmp() : m_Counter(0) {}
    bool operator()( const int &lhs, const int &rhs ){  ++m_Counter;    return lhs<rhs; }
    int GetCounterVal() const { return m_Counter;   }
    void ResetCounterVal(){ m_Counter=0;    }
private:
    int m_Counter;
};

//
using Iter = std::vector<int>::iterator;
using CmpFun = Cmp&;//std::function<bool(const int &, const int &)>;

std::vector< void(*)( Iter,Iter,CmpFun ) > V
{
    SelectionSort< Iter,CmpFun >,
    InsertionSort< Iter,CmpFun >
};

std::vector<int> Unsorted{ 3,9,0,8,3,1 };
Cmp comparer;  //比較処理者
for( auto f : V )
{
    auto Vals = Unsorted;
    comparer.ResetCounterVal();
    f( Vals.begin(), Vals.end(), comparer );

    for( auto v: Vals ){    std::cout << v << ", "; }
    std::cout << "\ncounter=" << comparer.GetCounterVal() << std::endl;
}

Comments

[退会済みユーザー]

ありがとうございます。
手元で試してみると、コードは簡潔になるもののソートにかかる時間が3-8倍程度遅くなりました。
理由がよく分からないのですが、Valsやf(下記コードではlist, func)へのアクセスが入れ子のように深くなるから...なのでしょうか?

```
for (const auto &func : functions) {
list = {unsorted_list};
int cnt = 0;
auto time = MeasureRuntime([&func, &list, &cnt]() {
return func(std::begin(list),
std::end(list),
[&cnt](const int &lhs, const int &rhs) {
++cnt;
return lhs < rhs;
});
});
}
```

[fana]

遅くなる理由はよくわかりません．
std::functionのオーバーヘッドが大きいのかも？

[yohhoy]

おそらく 比較関数オブジェクト Compare を std::function として各アルゴリズムをインスタンス化したため、ソート時の要素比較ごとに呼出オーバーヘッドが乗っているのだと思います。

個別ソートアルゴリズムの関数テンプレートを直接呼び出していたときはCompare にはラムダ式が指定されており、C++コンパイラは関数テンプレート実体化時に比較処理コードをインライン化しているはずです。（≒最適化が効きやすい構造だった）
実行時オーバーヘッドはstd::function でインタフェースを共通化・汎用化した代償ともいえますが、現在の構造のまま速度改善するのは難しい気がします。たぶん。

[fana]

ラムダで与えている比較処理がループ内でいつも同じなのであれば
ラムダじゃなくて自前ファンクタを用意してその型使えばマシになるのだろうか（という旨を追記してみた）

[退会済みユーザー]

なるほど、奥が深いですね...

void(*)( Iter,Iter,CmpFun ) この書き方は何という手法?なのでしょうか? 自分で使いこなせるように詳細を調べたいのですが、キーワードが分かりません。

[fana]

それはただの関数ポインタです．

Answer 2

ちょっと出先でコードが書けなくて申し訳ないですが、std::functionを要素にしたvectorを作成する、もしくはポリモーフィズムでループさせる(質問とずれますが)、で実現できそうかなと思います。

【追記】
遅くなりすみません。

using Iterator = std::vector<int>::iterator;
using Compare = std::function<bool(const int&, const int&)>;

int main() {
    std::vector<int> unsorted_list{ 9, 8, 7, 6, 5 };

    auto std_sort = [](Iterator it_1, Iterator it_2, Compare com) {
        std::sort(it_1, it_2, com);
    };
    auto std_stable_sort = [](Iterator it_1, Iterator it_2, Compare com) {
        std::stable_sort(it_1, it_2, com);
    };

    std::vector<std::function<void(Iterator, Iterator, Compare)>> vec{std_sort, std_stable_sort};

    for (auto&& v : vec) {
        int cnt = 0;
        v(std::begin(unsorted_list),
                    std::end(unsorted_list), 
                    [&](const int &lhs, const int &rhs) {
                        ++cnt;
                        return lhs < rhs;
                    });
        std::cout << cnt << std::endl;
    }
}

こんな感じのを想像していました。これならエラーは出ないかな、と思います。

Answer 3

C++でのラムダの型は、1つごとに異なることになっています。std::functionで受けることになるかと思います。