心臓に悪いC++のエラーとかUnion-Find木とか


  #define rep(i,n) for(int i=0;i<(int)(n);i++)
  int n, k;
  vector <int> t(k), x(k), y(k);
    cin >> n >> k;
    rep(i, k) cin >> t[i] >> x[i] >> y[i];
とすると
 terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

 というエラーが出ます。たぶんGCC4.9での話。
 訳わからんと思って調べるとこれはnewに失敗した時のエラー、つまりメモリ確保に失敗した時のエラーらしい。わかりづらい……。
 C言語を使っていた頃(短かった)はif文にmallocをつっこんでエラーメッセージを出させていたのでなおさらです……。標準化委員会様でもGNU様でもいいからもう少し分かりやすいエラーメッセージを出してくれよ……と思います。というか、世界中の人がそう思っているだろうし一億回くらいこういう議論が交わされてそう。
 ちなみに、自明と言えば自明ですが、もちろんkの入力を待たずにvectorを宣言したのが敗因。手元の環境だとintのデフォルト値が4200718になってました。めっちゃ微妙な数字。ていうか、四十万くらいでもメモリ確保失敗しちゃうんですねえ。
 今日は他にも
  vector <int> x(k);
  rep(i, n){
      int x = x[i];
……

 というのをやらかして、使っているターミナル(ConEmu)の画面がエラーメッセージで埋まりました。300行くらいあったんじゃないだろうか。
 これ、普通の配列だと大丈夫なんですけどねえ。vectorを配列感覚で使うの、やめたほうがいいのでしょうか。C++は名前にうるさいのはまあ分かるんだけど、心臓に悪いエラーメッセージで初心者の心をすり減らすのはマジで勘弁して欲しい。

 久しぶりの更新ですね……。本の感想もバンバン上げようという意気込みはあったのですが蟻本とアニメ鑑賞に時間を吸われています。
 今日のはPOJ1182「食物連鎖」という本当にこれ初級なの的なUnion-Find問題をやったのですが、これ原文中国語なんですね……。「大学がプロコンの邪魔だと思っていた」発言は伊達じゃないというか、中国語の問題まで解き漁るのガチ勢すぎるでしょ……。
 おかげさまでいい時代になったので僕は日本語の問題しかやっていませんが……。
 TLEを食らって焦ったのですが、classをstructに変えて(少しだけ速くなる)iostreamの代わりにcstdioの関数を使ったら(入力がめちゃ多いのでこれは影響が大きい)普通にいけました。
 記念にコードを貼ります。

 というか、Union-Find木の実装ってrank使っても大して速くならなくないですか。
 配列参照の回数が増えるのもあるんだろうが、普通に経路圧縮だけで大丈夫っぽい。
 この実装の場合は要素の集合を持つのではなく、要素の番号それぞれに対する親の番号を持つというのがコツかな、という感じです。ただ、Atcoderとかでdataという配列を使っている人はどうも親の名前を持ってるんじゃないっぽいんですが、よくわかりません……。
 次は本の感想と、あと最近Atomが重すぎてxyzzyに乗り換えた話とかを。ただまあ、xyzzyを使っていて「本当によくできたソフトだなあ」以外の感想がないので厳しいかも……。