多段階選抜 (C++20) (MSVC only)


C++20(TS) generator document is below.

|多段階選抜|解答日|シリーズ:yieldの練習/ジェネレータを入れ子に/整数平方根・立方根の実装|
|:--|:--|:--|
|問題|　|http://nabetani.sakura.ne.jp/hena/ord24eliseq/<br>https://qiita.com/Nabetani/items/1c83005a854d2c6cbb69|
|Ruby|2014/8/2(当日)|https://qiita.com/cielavenir/items/9f15e29b73ecf98968a5|
|C#/Python|2014/8/4|https://qiita.com/cielavenir/items/a1156e6a4f71ddbe5dcb|
| |　|ここから上はdrop_prev_square/drop_prev_cubicをまとめる前の答案|
|Go/C#/Ruby/Python|2014/8/5|https://qiita.com/cielavenir/items/2a685d3080862f2c2c47|
|PHP/JavaScript|2014/9/9|https://qiita.com/cielavenir/items/28d613ac3823afbf8407|
|VB|2014/9/10|https://qiita.com/cielavenir/items/cb7266abd30eadd71c04|
|D|2015/12/21|https://qiita.com/cielavenir/items/47c9e50ee60bef2847ec|
|Perl|2017/3/10|https://qiita.com/cielavenir/items/6dfbff749d833c0fd423|
|Lua|2017/3/13|https://qiita.com/cielavenir/items/c60fe7e8da73487ba062|
|C++20(TS)|2017/3/15|https://qiita.com/cielavenir/items/e1129ca185008f49cbab (MSVC)<br>https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 (clang)|
|F#|2017/3/17|https://qiita.com/cielavenir/items/a698d6a26824ff53de81|
|Boo/Nemerle|2017/5/13|https://qiita.com/cielavenir/items/e2a783f0fe4b0fe0ed48|
|Perl6|2017/5/15|https://qiita.com/cielavenir/items/656ea17fa96c865c4498|
|Kotlin|2017/5/25|https://qiita.com/cielavenir/items/9c46ce8d9d12e51de285|
|Crystal|2018/5/8|https://qiita.com/cielavenir/items/1815bfa6a860fd1f90db|
|MoonScript|2018/6/16|https://qiita.com/cielavenir/items/8b03cce0386f4537b5ad|
|Julia/Rust|2018/12/20|https://qiita.com/cielavenir/items/3ddf72b06d625da0c4a5|
|Nim|2018/12/26|https://qiita.com/cielavenir/items/5728944867e609fd52a7|
|Tcl|2018/12/31|https://qiita.com/cielavenir/items/76cbd9c2022b48c9a2c9|
|Pascal/Cobra|2019/1/16|https://qiita.com/cielavenir/items/81b81baf8dfc1f877903|
|Icon|2019/1/17|https://qiita.com/cielavenir/items/889622dcc721f5a4da24|
|Swift|2020/5/31|https://qiita.com/cielavenir/items/3b0b84a218e35d538f7f|
|Java/Groovy/Scala|2020/5/31|https://qiita.com/cielavenir/items/7f058203a8fd03b65870|
|V|2020/10/17|https://qiita.com/cielavenir/items/df30a6c101a97a713df5|
|Zig/Zen|2020/10/17|https://qiita.com/cielavenir/items/9cced9e4a94dcd70df0f|
|Pike|2020/11/2|https://qiita.com/cielavenir/items/3a8248f41611302b34fd|
|Vala/Smalltalk|2020/11/29|https://qiita.com/cielavenir/items/085dabe593cd916af5e8|
|Objective-C|2020/11/30|https://qiita.com/cielavenir/items/a1736e38789a3dd5cc5a|
|Ruby(Ractor)|2021/1/2|https://qiita.com/cielavenir/items/f493c6d512b63cc571cc|
|Python(_xxsubinterpreters)|2021/6/29|https://qiita.com/cielavenir/items/f1f581a055db918954f1|
|Falcon/Scheme|2021/9/5|https://qiita.com/cielavenir/items/c13d12cf44f0d17f4a94|
|Clojure/Lisp|2021/9/7|https://qiita.com/cielavenir/items/7458ba076f4e5bc0f196|
|(icbrtの実装に関する)補題|2017/5/11|整数除算であってもn/(x*y)はn/x/yに等しい(ことの証明)<br>https://qiita.com/cielavenir/items/21a6711afd6be8c18c55|

- 真打登場。
- ただしVisual C++ 2017でしか動きません。 Works with only Visual C++ 2017.

```cpp:tyama_hena24_enum.cpp
// http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
// http://nabetani.sakura.ne.jp/hena/ord24eliseq/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <numeric>
#include <experimental/generator>
#include <cstdio>
#include <cmath>
using namespace std;
using namespace std::experimental;

generator<int> generate(){
	int i=1;
	for(;;){
		co_yield i;
		i+=1;
	}
}
generator<int> drop_prev(bool(*check)(int),generator<int> _prev){
	auto prev=_prev.begin();
	int a=*prev;
	++prev;
	int b=*prev;
	for(;;){
		if(!check(b))co_yield a;
		a=b;
		++prev;
		b=*prev;
	}
}
generator<int> drop_next(bool(*check)(int),generator<int> _prev){
	auto prev=_prev.begin();
	int a=*prev;
	++prev;
	int b=*prev;
	co_yield a;
	for(;;){
		if(!check(a))co_yield b;
		a=b;
		++prev;
		b=*prev;
	}
}
generator<int> drop_n(bool(*check)(int,int),int n,generator<int> _prev){
	auto prev=_prev.begin();
	int i=0;
	for(;;){
		i++;
		int a=*prev;
		if(!check(i,n))co_yield a;
		++prev;
	}
}
bool is_sq(int n){
	int x=(int)sqrt(n);
	return x*x==n;
}
bool is_cb(int n){
	int x=(int)cbrt(n);
	return x*x*x==n;
}
bool is_multiple(int i,int n){return i%n==0;}
bool is_le(int i,int n){return i<=n;}

int main(){
	map<char,function<generator<int>(generator<int>)>> f={
		{'S',[&](auto e){return drop_next(&is_sq,move(e));}},
		{'s',[&](auto e){return drop_prev(&is_sq,move(e));}},
		{'C',[&](auto e){return drop_next(&is_cb,move(e));}},
		{'c',[&](auto e){return drop_prev(&is_cb,move(e));}},
		{'h',[&](auto e){return drop_n(&is_le,100,move(e));}},
	};
	vector<int>v(8);
	iota(v.begin(),v.end(),2);
	for(auto &e:v)f[(char)('0'+e)] = [&](int &j){
		return [&](auto e){return drop_n(&is_multiple,j,move(e));};
	}(e);

	string line;
	for(;getline(cin,line);){
		bool first=true;
		//cS => f['S'](f['c'](generate()))
		//auto z=reduce!((s,e)=>f[e](s))(generate(),line);

		auto z=generate();
		for(char e:line)z=f[e](move(z));
		auto it=z.begin();
		for(int i=0;i<10;i++){
			int n=*it;
			++it;
			if(!first)putchar(',');
			first=false;
			printf("%d",n);
		}
		puts("");
		fflush(stdout);
	}
}
```

### 170314追記

最初に書いた答案は間違いだらけだった…
diffは以下の通り。

```cpp
diff --git a/hena/tyama_hena24_enum.cpp b/hena/tyama_hena24_enum.cpp
index f14a604..1d9dc83 100644
--- a/hena/tyama_hena24_enum.cpp
+++ b/hena/tyama_hena24_enum.cpp
@@ -3,8 +3,10 @@
 
 #include <iostream>
 #include <string>
+#include <vector>
 #include <map>
 #include <functional>
+#include <numeric>
 #include <experimental/generator>
 #include <cstdio>
 #include <cmath>
@@ -18,7 +20,7 @@ generator<int> generate(){
                i+=1;
        }
 }
-generator<int> drop_prev(const function<bool(int)> &check,const generator<int> &_prev){
+generator<int> drop_prev(bool(*check)(int),generator<int> _prev){
        auto prev=_prev.begin();
        int a=*prev;
        ++prev;
@@ -30,7 +32,7 @@ generator<int> drop_prev(const function<bool(int)> &check,const generator<int> &
                b=*prev;
        }
 }
-generator<int> drop_next(const function<bool(int)> &check,const generator<int> &_prev){
+generator<int> drop_next(bool(*check)(int),generator<int> _prev){
        auto prev=_prev.begin();
        int a=*prev;
        ++prev;
@@ -43,7 +45,7 @@ generator<int> drop_next(const function<bool(int)> &check,const generator<int> &
                b=*prev;
        }
 }
-generator<int> drop_n(const function<bool(int,int)> &check,int n,const generator<int> &_prev){
+generator<int> drop_n(bool(*check)(int,int),int n,generator<int> _prev){
        auto prev=_prev.begin();
        int i=0;
        for(;;){
@@ -65,16 +67,19 @@ bool is_multiple(int i,int n){return i%n==0;}
 bool is_le(int i,int n){return i<=n;}
 
 int main(){
-       map<char,function<generator<int>(const generator<int>&)>> f={
-               {'S',[&](auto &e){return drop_next(&is_sq,e);}},
 bool is_le(int i,int n){return i<=n;}
 
 int main(){
-       map<char,function<generator<int>(const generator<int>&)>> f={
-               {'S',[&](auto &e){return drop_next(&is_sq,e);}},
-               {'s',[&](auto &e){return drop_prev(&is_sq,e);}},
-               {'C',[&](auto &e){return drop_next(&is_cb,e);}},
-               {'c',[&](auto &e){return drop_prev(&is_cb,e);}},
-               {'h',[&](auto &e){return drop_n(&is_le,100,e);}},
+       map<char,function<generator<int>(generator<int>)>> f={
+               {'S',[&](auto e){return drop_next(&is_sq,move(e));}},
+               {'s',[&](auto e){return drop_prev(&is_sq,move(e));}},
+               {'C',[&](auto e){return drop_next(&is_cb,move(e));}},
+               {'c',[&](auto e){return drop_prev(&is_cb,move(e));}},
+               {'h',[&](auto e){return drop_n(&is_le,100,move(e));}},
        };
-       for(int i=2;i<10;i++){
-               f[(char)('0'+i)] = [&](auto &e){return drop_n(&is_multiple,i,e);};
-       }
+       vector<int>v(8);
+       iota(v.begin(),v.end(),2);
+       for(auto &e:v)f[(char)('0'+e)] = [&](int &j){
+               return [&](auto e){return drop_n(&is_multiple,j,move(e));};
+       }(e);
+
        string line;
        for(;getline(cin,line);){
                bool first=true;
@@ -82,7 +87,7 @@ int main(){
                //auto z=reduce!((s,e)=>f[e](s))(generate(),line);
 
                auto z=generate();
-               for(char e:line)z=f[e](z);
+               for(char e:line)z=f[e](move(z));
                auto it=z.begin();
                for(int i=0;i<10;i++){
                        int n=*it;
```

#### チェック関数の渡し方
- C++11では`function<ret(param)>`という覚えやすい書き方ができるようになった。これの`const&`を渡すことが主流であろう。
- しかし、この書き方だとfunctionオブジェクトが生成されてしまい、この参照は(おそらく`f[]()`を抜けた段階で)破棄されてしまう。
- よって、 **存在するオブジェクトの値渡し** でなければならない。関数を渡す場合は必然的に関数ポインタを使うことになる。
- 2..9においても、この数値をメモリ上に残して置かなければならない。
- cf: http://stackoverflow.com/questions/37634643/why-does-my-program-have-variable-lifetime-issues-when-using-generators

#### generatorの渡し方
通常、引数の渡し方は3通りある。

1. `const generator<int> &_prev`
  - その場で生成したオブジェクトをコピーを避けかつ変数に入れずに渡したいときに使用する方法である。
  - generator#begin()はgeneratorオブジェクトを変更するため、今回は不可である。
2. `generator<int> &_prev`
  - コピーを避け、かつオブジェクトを変更する必要があるときに使用する方法である。
  - generatorオブジェクトが変更される点は満たすが、上記の変数の寿命の兼ね合いで正常に動かない。
3. `generator<int> _prev`
  - 毎回コピーを行う方法である。
  - 今回、これだけが正しく動作する。なお、コピーのコストはかなり小さいようである。

そして、generatorクラスはコピーコンストラクタが削除されているため、ムーブセマンティクスを用いて渡す必要がある。

ドキュメントも少ない現状、常用は難しい印象でした。

以下SEO対策

---

#### Passing check function

- From C++11, you can use the notation `function<ret(param)>`, which is quite rememberable. Now usually this `const&` is passed.
- However, this notation generates the function object and the reference is destructed (possibly after `f[]()` is passed).
- Therefore, we have to pass the **value (not reference) of existing objects.** We have to use the function pointer.
- The 2..9 range must also be retained on memory.
- cf: http://stackoverflow.com/questions/37634643/why-does-my-program-have-variable-lifetime-issues-when-using-generators

#### Passing generator

Usually there are 3 ways to pass generators.

1. `const generator<int> &_prev`
  - We use this if we want to use immediate objects without variables and to avoid copying them.
  - Since generator#begin() modifies the generator object, we cannot use method.
2. `generator<int> &_prev`
  - We use this if we want to avoid copying objects and to modify them in the function.
  - This method satisfies that generator objects are modified, but the variables lifetime (written above) matters and the program will crash.
3. `generator<int> _prev`
  - This method copies the objects every time.
  - In our cases, only this method works. Actually the copying cost looks small.

Finally the generator class's copy constructor is deleted. So we have to use the move semantics.

Since we have few documents, common use looks difficult now.

## 170513

整数平方根・立方根コードです

```cpp:isqrt_icbrt.cpp
int isqrt(int n){
	if(n<=0)return 0;
	if(n<4)return 1;
	int x=0,y=n;
	for(;x!=y&&x+1!=y;)x=y,y=(n/y+y)/2;
	return x;
}
int icbrt(int n){
	if(n<0)return icbrt(-n);
	if(n==0)return 0;
	if(n<8)return 1;
	int x=0,y=n;
	for(;x!=y&&x+1!=y;)x=y,y=(n/y/y+y*2)/3;
	return x;
}
```

## 181024

clangでもコンパイルできる完全版を https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 に置きました