C++ の 再帰template を使ったあまり使えない競プロ用 std::vector 操作テク
template は再帰的に展開されるので工夫次第で色々できます。 出来るってだけで実用的かどうかは知りません。
自分が使っていたり、思いついたりした std::vector 操作テクを紹介します。
C++11です。 GCCです。
目次
vector の 入力を簡単に
競プロではよく標準入力から長さ $N$ の数列 $A$ が与えられたりします。
N A1 A2 ... AN
C++ で競プロやるとこんな感じで受け取ると思います。
#include <iostream> #include <vector> using namespace std; int main(){ int n; cin >> n; vector<int> A(n); for(int i=0; i<n; i++) cin >> A[i]; //ここで何かする return 0; }
このfor文、毎度書くの面倒ですよね。 下みたいな感じで一気に入力読めると楽ですよね。*1
vector<int> A(n);
cin >> A;
これを実現するには istream::operator>> に 新たに vector<int> を定義してやればいいのですが、 どうせなら int の他にも string や long long , double 等でも同じことがしたいですよね。 全部について書くのは面倒なので template を使ってまとめて書いてしまいましょう。
template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいいです。 return is; } int main(){ int n; cin >> n; vector<int> A(n); cin >> A; //簡単！ //ここで何かする return 0; }
templateを使うとまとめて書ける以上に嬉しいことがあって、これ多重vectorでも読んでくれます。
vector<vector<double>> mat(n, vector<double>(n)); cin >> mat;
これは template が再帰的に展開されるためです。
istream& operator >> (vector<vector<double>>& val); //template の T は vector<double>型
istream& operator >> (vector<double>& val); //template の T は double型
istream& operator >> (double& val); //初めから定義されている istream >> double&
行列が入力に与えられるとき等に使えて結構便利ですが、
入力が多い*2 と cin は時間がかかってしまい、 下手するとTLEの原因になったりします。
適宜 scanf を使ったり、 cin 高速化テク を使ったりしましょう。
vector の 出力を簡単に
vector の中身を全て空白区切りで出力したいとき。
vector<int> vec = {1,2,3,4}; for(int i=0; i<vec.size(); i++){ cout << val << ( i+1 == vec.size() ? "" : " " ); //1 2 3 4 } cout << endl;
これもこう書けると楽ですよね。
cout << vec << endl; //1 2 3 4
istreamのときと同様に、ostream::operator<< に 新たに vector<int> を定義すればOKです。 これもtemplateでまとめてしまいましょう。
template<typename T> ostream& operator << (ostream& os, vector<T>& vec){ for(int i=0; i<vec.size(); i++){ os << vec[i] << ( i+1 == vec.size() ? "" : " " ); } return os; }
vector<int> vec = {1,2,3,4}; cout << vec << endl; //1 2 3 4
問題によって空白区切りだったり改行区切りだったりするため、汎用性はかなり低いです。 手元でデバッグ出力が簡単に出来るよー、程度になら使えると思います。
これも再帰的に展開してくれるので多重vectorも出力できますが、 このままでは見辛いので尻尾で改行したり括弧でくくったり、一工夫必要です。
余談。 無理してそのまま ostream に流さないで join 関数作るって発想もあります。
#include <sstream> template<typename T> string join(vector<T>& vec, string sep = " "){ stringstream ss; for(int i=0; i<vec.size(); i++){ ss << vec[i] << ( i+1 == vec.size() ? "" : sep ); } return ss.str(); }
vector<int> vec = {1,2,3,4}; cout << join(vec, ",") << endl; // 1,2,3,4 cout << join(vec, "\n") << endl; //1 //2 //3 //4
多重 vector の fill
多重vectorを全て同じ値で埋めたいとき。
vector には
fill constructor
があるので、 初期化だけで良ければこれを利用しましょう。
vector<vector<vector<int>>> A(n, vector<vector<int>>(n, vector<int>(n, -1))); //全ての要素が -1 で埋められる。
多重for文を書いて素直に埋めることもあります。 一番内側のループは std::fill を使えば不要です。
for(int x=0; x<A.size(); x++){ for(int y=0; y<A[x].size(); y++){ fill(A[x][y].begin(), A[x][y].end(), -1); //for(int z=0; z<A[x][y].size(); z++){ // A[x][y][z] = -1; //} } }
新たに作り直した多重vectorで上書きしても、for文を回すのと計算量的には同じです。 *3
A = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n, -1)));
再帰template を使うとこんな感じになります。
template<typename V, typename T> void fill(V& x, const T& val){ //再帰の終端用関数 x = val; } template<typename V, typename T> void fill(vector<V>& vec, const T& val){ for(auto& v: vec) fill(v, val); //fill(vector<V> vec, T val) から fill(V vec[i], T val) が呼ばれる。 }
fill(A, -1);
入出力のときのと異なるのは、再帰templateの終端の関数を自分で定義している点です。
istream::operator>> 、 ostream::operator<< には int や double 等 の
基本的な型との operator が既に定義されていたため不要でしが、
このfill関数は自前の関数なので終端を定義してやらねばなりません。
多重 vector の resize
DPをするとき、4重5重の vector を使いたかったりします。 そんでよくこんなヤバそうなコードを書いたりします。
vector<vector<vector<vector<long long>>>> dp(100,vector<vector<vector<long long>>>(5,vector<vector<long long>>(3,vector<long long>(2,0))));
100*5*3*2の4重vectorです。 139文字らしいので 1 tweet に収まります。
でも出来ればこんなにvector<vector<...なんて書きたくないです。
宣言だけしておいて resize用のfor文を回したりする人もいると思います。*4
vector<vector<vector<vector<long long>>>> dp; dp.resize(100); for(int a=0; a<100; a++){ dp[a].resize(5); for(int b=0; b<5; b++){ dp[a][b].resize(3); for(int c=0; c<2; c++){ dp[a][b][c].resize(2, 0); } } }
再帰template を使うとこんな書き方が出来ます。
template<typename V, typename H> void resize(vector<V>& vec, const H head){ //再帰の終端。 可変長templateの長さが 0 になるとこっちが呼ばれる。 vec.resize(head); } template<typename V, typename H, typename ... T> void resize(vector<V>& vec, const H& head, const T ... tail){ vec.resize(head); for(auto& v: vec) resize(v, tail...); }
vector<vector<vector<vector<long long>>>> dp; resize(dp, 100,5,3,2);
可変長template を使ってます。
Haskell のリスト操作の head / tail みたいな感じで、 列の頭だけ取り出して再帰 → 頭だけになったら終端。
以前は可変長templateを知らず、 vectorを代わりに与えてました。 可変長templateの方がスッキリしてていい感じです。
↓以前使ってたゴミ。 よく使う int/long long/double/string の再帰終端を用意して、 呼び出し用の関数も用意してました。
void resize(int& val, vector<int>::iterator first, vector<int>::iterator last){val=0;} void resize(long long& val, vector<int>::iterator first, vector<int>::iterator last){val=0LL;} void resize(double& val, vector<int>::iterator first, vector<int>::iterator last){val=0.0;} void resize(string& val, vector<int>::iterator first, vector<int>::iterator last){val="";} template<class T> void resize(vector<T>& vec, vector<int>::iterator first, vector<int>::iterator last){ if(first == last) return; vec.resize(*first); //if(last - first == 1) return; for(auto& vec_ : vec) resize(vec_, first+1, last); } template<class T> void resize(T& vec, vector<int> sz){ resize(vec, sz.begin(), sz.end()); } //resize(vec, {100,5,3,2}); として呼び出す。 //initializer_list を利用してた。
複数の vector にまとめて入力
競プロではたまに $N$ 個の何かについて パラメータ $X$ , $Y$ , $Z$ が与えられ、何らかの処理をする問題が出題されます。
次のような順でパラメータが与えられれば vector の 入力を簡単に の方法で入力を簡単に読めます。
N X1 X2 ... XN Y1 Y2 ... YN Z1 Z2 ... ZN
int n; cin >> n; vector<int> x(n); vector<double> y(n); vector<string> z(n); cin >> x >> y >> z;
しかし実際には次のような順で与えられることが多いです。
N X1 Y1 Z1 X2 Y2 Z2 . . . XN YN ZN
これを cin >> x >> y >> z のような感覚で受け取りたいです。
x,y,z からなる構造体を定義して istream との operator>> も定義、という手法をまず思いつきますが、
問題毎にパラメータの数や型は異なるので汎用的なものは作りづらそうですし、毎度1から書いてる暇があったら素直にfor文書いた方が手っ取り早いです。
template でどうにか汎用的な入力メソッドを作れないでしょうか？
実用的かどうかはかなり怪しいですが、こんな感じのを思いつきました。
template<typename H> void input_set(istream& is, const int idx, vector<H>& head){ //終端 is >> head[idx]; } template<typename H, typename ... T> void input_set(istream& is, const int idx, vector<H>& head, T& ... tail){ //idx行目の入力を処理 input_set(is >> head[idx], idx, tail...); } template<typename H, typename ... T> void input_set(istream& is, vector<H>& head, T& ... tail){ //istream 指定したいときはこっちを直接呼び出す for(int i=0; i<head.size(); i++) input_set(is, i, head, tail...); } template<typename H, typename ... T> void input_set(vector<H>& head, T& ... tail){ //istream を指定しなければ cin から受け取る input_set(cin, head, tail...); }
int n; cin >> n; vector<int> x(n); vector<double> y(n); vector<string> z(n); input_set(x,y,z); //input_set(cin, x,y,z);
実用的、ではないと思うなぁ……。
