質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

3回答

689閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2020/05/19 08:35

編集2020/05/19 09:10

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

C++

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

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

C++

1 auto list{unsorted_list}; 2 int selection_cnt = 0; 3 auto selection_time = MeasureRuntime([&list, &selection_cnt]() { 4 return SelectionSort(std::begin(list), 5 std::end(list), 6 [&selection_cnt](const int &lhs, const int &rhs) { 7 ++selection_cnt; 8 return lhs < rhs; 9 }); 10 });

コード全文 [Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ


追記

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

C++

1using Iterator = std::vector<int>::iterator; 2using Compare = std::function<bool(int, int)>; 3 4int main() { 5 std::vector<std::function<void(Iterator, Iterator, Compare)>> functions{SelectionSort, std::sort}; 6}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

ソート関数群

C++

1template<class Iterator, class Compare> 2void SelectionSort(Iterator begin, Iterator end, Compare comp) { 3 for (auto it = begin; it != end; ++it) { 4 auto min = std::min_element(it, end, comp); 5 std::iter_swap(it, min); 6 } 7} 8 9template<class Iterator, class Compare> 10void InsertionSort(Iterator begin, Iterator end, Compare comp) { 11 for (auto it = begin; it != end; ++it) { 12 auto following = std::upper_bound(begin, it, *it, comp); 13 std::rotate(following, it, std::next(it)); 14 } 15}

に対して,

C++

1using Iter = std::vector<int>::iterator; 2using CmpFun = std::function<bool(const int &, const int &)>; 3 4std::vector< void(*)( Iter,Iter,CmpFun ) > V 5{ 6 SelectionSort< Iter,CmpFun >, 7 InsertionSort< Iter,CmpFun > 8}; 9 10//Vを使ってみる 11std::vector<int> Unsorted{ 3,9,0,8,3,1 }; 12for( auto f : V ) 13{ 14 auto Vals = Unsorted; 15 int counter = 0; 16 f( Vals.begin(), Vals.end(), [&counter]( const int &lhs, const int &rhs )->bool{ ++counter; return lhs<rhs; } ); 17 18 for( auto v: Vals ){ std::cout << v << ", "; } 19 std::cout << "\ncounter=" << counter << std::endl; 20}

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


追記:
処理速度に関しては,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; }

投稿2020/05/19 09:35

編集2020/05/20 02:42
fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2020/05/19 11:33 編集

ありがとうございます。 手元で試してみると、コードは簡潔になるもののソートにかかる時間が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

2020/05/20 01:07

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

2020/05/20 02:03 編集

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

2020/05/20 02:45

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

退会済みユーザー

2020/05/20 02:50

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

2020/05/20 03:06

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

0

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

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

cpp

1using Iterator = std::vector<int>::iterator; 2using Compare = std::function<bool(const int&, const int&)>; 3 4int main() { 5 std::vector<int> unsorted_list{ 9, 8, 7, 6, 5 }; 6 7 auto std_sort = [](Iterator it_1, Iterator it_2, Compare com) { 8 std::sort(it_1, it_2, com); 9 }; 10 auto std_stable_sort = [](Iterator it_1, Iterator it_2, Compare com) { 11 std::stable_sort(it_1, it_2, com); 12 }; 13 14 std::vector<std::function<void(Iterator, Iterator, Compare)>> vec{std_sort, std_stable_sort}; 15 16 for (auto&& v : vec) { 17 int cnt = 0; 18 v(std::begin(unsorted_list), 19 std::end(unsorted_list), 20 [&](const int &lhs, const int &rhs) { 21 ++cnt; 22 return lhs < rhs; 23 }); 24 std::cout << cnt << std::endl; 25 } 26}

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

投稿2020/05/19 08:54

編集2020/05/19 11:50
退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

投稿2020/05/19 08:44

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問