読者です 読者をやめる 読者になる 読者になる

C++ の 再帰template を使ったあまり使えない競プロ用 std::vector 操作テク

template は再帰的に展開されるので工夫次第で色々できます。 出来るってだけで実用的かどうかは知りません。
自分が使っていたり、思いついたりした std::vector 操作テクを紹介します。
C++11です。 GCCです。

目次

  1. vector の 入力を簡単に
  2. vector の 出力を簡単に
  3. 多重 vector の fill
  4. 多重 vector の resize
  5. 複数の vector にまとめて入力

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 高速化テク を使ったりしましょう。

https://ideone.com/dtSfLo


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も出力できますが、 このままでは見辛いので尻尾で改行したり括弧でくくったり、一工夫必要です。

https://ideone.com/AcdV55


余談。 無理してそのまま 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関数は自前の関数なので終端を定義してやらねばなりません。

https://ideone.com/ZkQkKd


多重 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の方がスッキリしてていい感じです。

https://ideone.com/s4aha1


↓以前使ってたゴミ。 よく使う 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);

実用的、ではないと思うなぁ……。

https://ideone.com/whAaYQ

*1:入力読みながらデクリメントして 0-indexed にしたかったりするので嬉しくなかったりもする

*2:目安は 100,000 以上

*3:多分実際にはメモリ周りのコストが若干かかる。

*4:競プロだし多次元配列使おうよって意見もままあると思います。