cafelier@SRM

競技プログラマのためのC++0xB

21:40 |

長らく C++0x と呼ばれていた C++ の次期国際規格が C++11 となることがほぼ決まった そうです。Topcoder で使えるようになるのが何年先かわかりませんが、Codeforces や、言語に制限のないコンテストでは、新しい g++ や VC++ を選択することで、今でもすでにかなりの機能を使うことができます。ということで布教。みんな使おう。

emplace_back

vector<pair<int,string>> v;
v.emplace_back(123, "hello");

push_back の代わりに使うと、追加したいオブジェクト「のコンストラクタに渡す引数」を指定して要素を増やせます。以前なら v.push_back(make_pair(123, "hello")); や v.push_back(pair<int,string>(123, "hello")); などと書いていたもので、比較するとコピーやキャストが起きる起きない等の違いもありますが、実際問題としては、単純に、いちいちコンストラクタ呼び出し書かなくていいので楽。

可変引数 min/max

cout << min({3,4,2,5,1,6}) << endl;

min(min(x,y),min(z,w)); のようなコードはもう不要。

<tuple>

tuple<int, double, string> t(1, 2.34, "hello");
cout << get<0>(t) << " " << get<1>(t) << endl;

pairは二つ組でしたがtupleなら何個でも。pair<pair<int,int>,int> よサヨウナラ。あと

enum {COST, NODE};
while( !dijkstra_queue.empty() ) {
  pair<double, vert> state = dijkstra_queue.top();
  if( get<NODE>(state) == goal ) ...
}

tupleに限らずpairでも、.first や .second じゃなくて get でアクセスできるので適当にenumでも置いておけばそれっぽい名前でアクセスしてる気分になれます。これが本当に良いコードかはさておき…。

initializer list

map<string, int> eng2int = {
  {"zero", 0},
  {"one",  1},
  {"two",  2},
};

mapやvectorでも、構造体や配列の初期化と同じ { ... } の構文で初期化。テストデータを書くときのお供に。

map::at

const map<string, int> eng2int;
int x = eng2int.at("two");

eng2int["two"] は const では無いので、変換表などを一度mapで作って固定したまま使い回す、という状況では「変更しないのに非constで扱う」か「簡潔なアクセスを捨てて.findで長々しいアクセスをする」の酷い二択を迫られていましたが、atならconstでmapを参照できます。

範囲 for 文

set<int> visited;
for(int v : visited)
  cout << v << endl;

auto

map<vector<int>, long long> memo;
auto it = memo.find(key);
if( it != memo.end() ) return it->second;

この辺りは説明不要と思います。もちろん範囲for文とautoの組み合わせも可です。

unordered_xxx

unordered_map<long long, string> table;

いわゆる O(1) アクセスのハッシュ表。mapではダメで unordered_map でないと…という問題がコンテストででることはほぼないかもしれませんが…

無名関数

vector<string> v = ...;
map<string, int> score = ...;
sort(v.begin(), v.end(), [&](const string& x, const string& y){return score[x] < score[y];});

[] で始めると周囲のローカル変数にはアクセスしない関数、[=] だと値コピー、[&] だと参照で周囲の環境をキャプチャします。もっと細かい制御もできますが、とりあえずは [&] しとけば楽（いい加減すぎて怒られそう）。

iota, all_of, any_of, none_of

if( all_of(v.begin(), v.end(), [](int x){return x>0;}) ) ...;

vector<int> v(100);
iota(v.begin(), v.end(), 0); // v={0,1,2,...,99};

アルゴリズムもいろいろ。無名関数書けるようになったので使いやすさは増しているはず。

※追記

C++11最大の改善点に触れるのを忘れていました！

vector<vector<int>> dp;

> と > の間にスペースいらない！