C++が使えたい 項目7(現行のC++への移行 – 1)

サバです。
3章にはいります!

今回も、表とその下の解説は無駄に長いので、適当に流し読みしてください!

 

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

 

項目7 オブジェクト作成時の()と{}の違い

結論:{}を使うならstd::initializer_listコンストラクタに気をつける

 

C++11はオブジェクト作成時の初期化に(){}を使い分けられます。ただし、組み込み型(プリミティブ型)変数の初期化には = も使えるため、初期化代入がごっちゃに理解されることが多いようです。自分もそうでした。

 

 

 

 

・初期化方法まとめ

重要なのは組み込み型の = 初期化特殊であることです。
ここではユーザ定義型(構造体・クラス)の例として Widget という型名を用います。

組み込み型
(クラス・構造体以外)
int Integer1 = 0;
int Integer2( 0 );
int Integer3{ 0 };
すべて同じ意味
0 で int 型変数を作成・初期化
= でも初期化をすることができる
初期化であって代入ではない
ユーザ定義型
(クラス・構造体)
Widget widget1( 0 );
Widget widget2{ 0 };
すべて同じ意味
Widgetのコンストラクタに 0 を渡して、Widgetオブジェクトを作成・初期化
  • ここにでは省略しましたが、{} の代わりに = {} も使用できます。全く同じ意味です。
  • ちなみにユーザ定義型で、下コード widget5 のように初期化をしない場合、デフォルトコンストラクタによって暗黙的に初期化されます。個人的には初期化を忘れたバグの根源なのか、デフォルト初期化したいのかが分からないので、widget6 の明示的初期化が良いと思います。
    Widget widget5;
    Widget widget6{};
    どちらもデフォルトコンストラクタで初期化

  • コンパイラによっては1変数を受け取るユーザ定義型のコンストラクタなら = でも初期化できるようです。

 

 

 

 

 

・初期化の統一記法

C++は変態なので変数を初期化する場所・場合がたくさんあります。
そんな中でも {} だけは統一的にすべての初期化を行うことができます。{}すんごい!!

組み込み型int integer1 = 0;
int integer2();
int integer3{};
= () {} 全てで初期化できます。
全てデフォルト値0での初期化です。
ユーザ定義型 Widget widget1();
Widget widget2{};

// NG : 二度手間
Widget widget3 = Widget{};

= では期待通りの初期化はできません。一時オブジェクトを作成し、ムーブコンストラクタでムーブ初期化するという二度手間になります。
(最適化されなければ)
宣言初期化子 class Widget
{
    int member1 = 0;
    int member2{};

    // メソッド?
    int member3();

};
() では初期化できません。
コンパイラにとってはメソッド
(メンバ関数)宣言にしか見えません。
コンストラクタ初期化子class Widget
{
    int member1;
    int member2;

public:  
    Widget(int value)
        : member1{ value }
        , member2( value )

    {}
};

= では初期化できません。
メンバを初期化するためのもので、代入するためのものではありません。(適当に理由を付けました)
コピーできないオブジェクトstd::atomic<int> ai{ 0 };

// Error : 関数は削除されてる
std::atomic<int> ai =
        std::atomic<int>{ 0 };

コピーやムーブを出来ないように設計されたオブジェクトは = 等を使えません。

左の例ではムーブコンストラクタが消されているため、エラーとなります。

template
との組み合わせ
template<typename T> decltype(auto) func()
{
    // どっち?
    return T::Whats();
}
こんな状況で () 初期化を使うのはやめましょう。Whats という static 関数呼び出しにしか見えません。
このコードで Whats オブジェクトの初期化をしていた時は、
バグの発見に大分骨を折りそうです。
  • 上の例を見ると {} だけいつでも初期化に使えることが分かります。

 

 

 

 

 

 

・ {} 初期化の型チェック機能

{} 初期化は統一記法以外にも型チェックという利点があります。
縮小変換(精度が落ちる変換)が必要な初期化が行われた場合、コンパイラがエラーを出してくれます。(コンパイラによっては警告)

int  pi { 3.14 };              // Error

double
  x{}, y{} z{};
int  sum { x + y + z };    // Error
 double 型から int 型への暗黙的な縮小変換
 (精度が落ちる・値が壊れるような型変換)
bool flag { 2 };               // Errorint 型から bool 型への暗黙的な縮小変換
  • エラーを避けるためには static_cast を使いましょう
    int pi{ static_cast<int>( 3.14 ) };

 

 

 

 

 

・{} 初期化の落とし穴

{} は凄い!ですが、致命的な問題があります。
それは std::initializer_list との相性問題です。
std::initializer_list を取るコンストラクタを持つオブジェクトを {} 初期化すると、縮小変換をしてでも、力ずくでこの std::initializer_list コンストラクタを使おうとします。

class Widget
{

    // コンストラクタ1
    Widget( int value )
    {}
    // コンストラクタ2
    Widget( std::initializer_list<bool> list ) 
    {}

};

int main()
{
    // コンストラクタ2を呼び出す
    Widget w{ 100 } // 縮小変換 Error も

    return 0;
}

main 関数内で、Widget の
コンストラクタ1
を呼び出しているように見えますが、
コンストラクタ2
が呼び出されます。
 

コンストラクタ1 を呼び出すには () を使った初期化をする必要があります。
 

また、{} 初期化は型チェックを行うため、この場合 Error や Warning が発生します。

  • コンパイラには {} が std::initializer_list にしか見えないのでしょうか…
  • 力ずくで変換できない場合、つまり、暗黙の型変換方法がない場合は、こんなことになりません。 例えば、std::initializer_list<bool> ではなく、 std::initializer_list<std::string>であった場合は、int 型から std::string 型への暗黙の型変換方法がないため、コンストラクタ1 が呼び出されます。

 

残念ながらこの相性問題の代表例は STL です。
std::vector も std::initializer_list をとるコンストラクタを持つため、こんな頭痛が痛い問題が起きます。

// { 10, 1 }
std::vector<int> vec1{ 10, 1 };
要素数2で、それぞれの値が 10, 1 となる
std::vector を作成
// { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
std::vector<int> vec2( 10, 1 );
要素数10で、すべての値が 1 となる
std::vector を作成
// { 100 }
std::vector<int> vec3{ 100 };
要素が 100 のみで要素数1となる
std::vector を作成
// { 0, 0, 0, … ( x 100) }
std::vector<int> vec4( 100 );
要素数100で、すべての要素をデフォルト値( 0 )で初期化した std::vector を作成
  • std::vector は {} だけじゃすべての初期化ができない… {} は初期化の統一記法じゃなかった!!!

 

初期化するオブジェクトに std::initializer_list をとるものがないか事前に確認しましょう。std::initializer_list をとるコンストラクタを定義するときは本当に必要なのか考えましょう。

 

 

 

 

 

 

Effective Modern C++ の中では、(), {} どちらの初期化も長所・短所を持つため、いずれかの記法を優先して使うように決め、必要に応じてもう一方を使おうとまとめられています。

 

 

 

 

< 前の項目へ   次の項目へ >  // そのうち…

C++が使えたい 項目6(auto – 2)

サバです。
autoについては最後の項目です(まだ二つ目)

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

項目5 auto が期待とは異なる型を推論する場面では ETII を用いる

 

結論:autoは明示的キャストと併用しよう

ETIIはC++的で明示的な型キャスト、static_cast を使ってauto変数を初期化する方法です。

auto itsInteger = static_cast<int>(64 * 0.2);    // キャストでint型変数として推論させる。
  • これを使ったらauto使えるし、どんな型と目的でキャストしてるのか明示的でわかりやすいよね!って話です。

 

また、std::vector<bool> を使うときにこの操作が必要な場合があります。
というのもstd::vector<bool>の [ ] 演算子は bool& ではない変な型を返してくるからです。

std::vector<int> vecInt = {1, 2, 3};
decltype( veclnt[0] );
auto front = vecInt[0];
decltype → int& // 分かる。内部要素への参照。
front       → int   // 期待通り。
std::vector<bool> vecBool = {true, true};
decltype( vecBool[0] );
auto front = vecBool[0];
decltype → std::vector<bool>::reference // WTF
front       → std::vector<bool>::reference // WTF

うーんこの…。そこでこの std::vector<bool> 使う時だけETIIしよって話です。

std::vector<bool> vecBool = {true, true};
auto front = static_cast<bool>( vecBool[0] )
front → bool   // 期待通り
  • もちろんbool型以外のstd::vectorはこんなことないです。ふつうです。こいつが変態なだけです。
  • めんどい…
  • 今にでもstd::vector<bool>に殴り掛かれそうなら、殴り掛かる前に下の内容を読んでみてください。

 

 

 

・深淵を覗きに行くために…

std::vector<bool>はうん○こ。ではなくちゃんと理由があるみたいです。

bool型のベクターはメモリを節約するため、内部でビット演算を使用して値を保持しています。となると、要素一つあたりのサイズは1ビット。でもC++の参照が指し示すことができるのはバイト単位…(参照は内部的にはポインタであるため)あれ? ビット単位な各要素への参照ってできないじゃん。じゃあ参照受け取って、各要素の値を直接変更するとかもできないじゃん! って当然なるわけです。

そこでstd::vector<bool>::reference君の登場です。下記のコードのように、ぱっと見いい感じに動作するよう彼は実装されています。この書き方だけならいつもの通りです。

std::vector<bool> vecBool = {false, false};
vecBool[0] = true;
vecBool[1] = true;
{false, false} // vecBool の中身
{true, false}
{true, true}

 

しかし、上記の注意点だけでは終わらず、追加でもう一つが紹介されています。
それは[]演算子の戻り値は値渡しでも、実質的には参照渡しであるということです。
例を挙げると、以下のようなコードは未定義動作です。

auto first = std::vector<bool>{false, false}[0];   //参照渡しと実質的に同義な値渡し
first = true;                                                        // 死んだオブジェクトに代入する未定義動作
  • std::vector<bool>::reference 君は、各要素を参照してるっぽく動作するため、ビットとして存在する実態にアクセスするための情報を持っています。実装方法によっては、ポインタとそこから何ビット目かといった感じの情報です。
  • 上記例では、std::vector<bool>::reference を first は受け取ります。そのため first は std::vector<bool>{false, false} と宣言された右辺値の内部を指し示すポインタを持つことになります。
  • 右辺値は一行だけの命です。つぎのセミコロンが来たらそこで死にます。
  • つまりfirst = true と代入している時点で、first 内部のポインタは、すでに死んだvectorが存在していた位置を指し示します。このコードは代入によってメモリ空間をぐちゃぐちゃにできるわけです。
  • このようなバグは、関数の戻り値(値渡し)でももちろん起こりえます。
  • std::vector<bool>怖い…

 

std::vector<bool>::referenceのような、ほかの型の模倣や拡張を目的としたクラスを、プロクシクラス(proxy class)とか言うらしいです。

このようなクラスの存在に気づくためには、ヘッダファイルの実装を自分で見ようねという話みたいです。C++楽じいなぁ…

 

C++は楽しい。

 

 

< 前の項目へ   次の項目へ >  // そのうち…

C++が使えたい 項目5(auto – 1)

サバです。
前回の記事は投稿後に大分変更・加筆をしたので、チラ見してくださいお願いします。
それに加えて、詰め込みすぎたので今回から1項目くらいずつで行きたいと思います。

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

 

項目5 明示的型宣言よりも auto を優先する

 

結論:いいものはどんどん使おう!

IDEあるならとりま使いましょう。ぐう有能。
(もちろん注意するとこもあるみたいですが…

具体的な使用例(特に変数宣言範囲for文!!)

変数宣言auto value = 0; int
範囲for文for (const auto& content : container) { }範囲for文 + auto&は最強
関数の戻り値auto func(){ return “auau”; }const char *
ラムダ式の引数 auto lambda = [](auto& arg)

    std::cout << arg;
};
これはC++14以降の機能

 

 

 

 

・auto ? なにそれおいしいの?

    つ autoはおいちい。(前回の記事)
   もし良ければ下にある「autoの利点」もどうぞ…
     ( このサイトが大好き。 : cpprefjp) // 神様です。いつもありがとうございます。
  

 

 

 

 

・深淵を覗きに行くために…

 auto の利点

 ・変数の初期化忘れがなくなる

    auto i = 0;
  • 型推論のために必ず初期値を指定する必要がある。

 

 ・コンパイラが適切な型を選んでくれる

    std::vector<int> vec;
    auto size = vec.size(); 
  • std::vector<int>のサイズを表す非負整数型は std::vector<int>::size_type だけど、そんな長いの覚えてコーディングする必要がなくなる。

 

 ・労力が減る

    std::vector<int> data(10)

    for (auto& val : data)
        std::cin >> val;

    for (auto ite = data.crbegin(); ite != data.crend(); ++ite)
        std::cout << *ite << std::endl;

  • 入力から10個の整数を受け取って逆順で出力するプログラム
  • std::vector<int> の int を書き換えるだけでどんな型にも対応できる(double, std::string, long, etc…)
  • イテレータの型指定で悩むこともなくなる
  • コンパイラに任せた方がヒューマンエラーは減る。楽しよう!

 

 

私は脳死して使うようにしています。autoだいしゅき。
C++に追加されたということは、いいからだまって使えという機能のはずですから。(盲信)

 

 

< 前の項目へ   次の項目へ >

C++が使えたい 項目1~4(型推論)

サバです。最近EffectiveModernC++をやっと買えたと思ったら、ついでに期末試験が迫ってきてしまったので、現実逃避しながらその内容について書いてきたいと思います。(本の内容を自分解釈で出力しとけば忘れたときに楽かなぁ…とも思ったので!)
この本にとっかかりやすくなってもらえるとうれしいなぁ

 

<注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

 

 

1章 型推論

 

項目1 テンプレートの型推論を理解する

 

結論:大体期待通り!

C++の深淵は闇の中だとしても、templateは晴れた日のあなたの部屋くらい明るい。
C++なんて、第一に安全、第二に効率を考えて、Cから派生したってことだけ分かっていれば、もう何も怖くない!!(そう願いたい…)
まさにtemplateはそんな感じ。(希望的観測)

 

template<typename T>  と宣言したとき、Tの使い方は参照について考えると3つあります。

1. void f (T arg) { }      : arg は値渡し

  • const , volatileは完全になかったことにされる

2. void f (T& arg) { }   : arg は参照渡し

  • この関数使うときに右辺値の引数をぶち込むとエラー

3. void f (T&& arg) { } : arg はユニバーサル参照渡し

  • ユニバーサル参照 : 左辺値参照・右辺値参照のどちらもイける両刀使い

 

上記の f を f (value) と呼び出したとき、 Targ  の
推論される型を表に入れるとこうなります。大体…期待通りです。(volatileもconstと同じ)

T + &TT&T&&
TargTargTarg
int value;intintintint&int&int&
int& value;intintintint&int&int&
int&& value;intintintint&int&int&
const int value;intintconst intconst int&const int&const int&
const int& value;intintconst intconst int&const int&const int&
const int&& value;intintconst intconst int&const int&const int&
f ( 1 )   // 何か右辺値intinterrorerrorintint&&
  • Tの時、constも参照も取れるのは、値渡しでできた複製(仮引数)がどうなろうとコピー元(実引数)には関係ないからです。
  • エラーが出るのは、右辺値を書き換えても意味がなく、リテラルの参照が存在したらわけわかめになるからだとおもいます。(適当)
  • ユニバーサル参照はいろいろ変態なので覚えるのが大変そうです…

 

 

・template? 知らない子ですね

  君は、関数にを渡すだけの退屈な日々を過ごす中で、
  型も渡せたらいいのにと思ったことはあるかい?
  そういうことだよ。()

 

 

・深淵を覗きに行くために…
 (闇のコードを読むことに興味がある方は知っているべき?)

ついでにポインタ、配列、関数も入れてみましょう

T + & + αTT&T&&
TargTargTarg
const int * const value;const int *const int *const int * constconst int * const &const int * constconst int * const &
int value[4];int *int *int [4]int (&)[4]int [4]int (&)[4]
void value( int );void (*)(int)void (*)(int)void (int)void (&)(int)void (int)void (&)(int)
  • int value[4] は長さ4の int 型配列、void value( int ) は int 型引数一つを受け取る void 関数です。
  • 注目するは青文字です。値渡しでは配列や関数をポインタとして推論しています。これはC言語由来の動作で、配列や関数がポインタに成り下がる(本当はポインタじゃないけどポインタのふりをする)という動作をするためです。
  • 参照渡しはポインタのふりをする必要がないため、配列・ポインタの参照型として推論されます。

 

Tにconstつけるとこうなります。
 (VS2017でこうなるを確認できたけど理由がよくわかってなかったり…

T + const + &const Tconst T&const T&&
TargTargTarg
int value;intconst intintconst int&errorerror
int& value;intconst intintconst int&errorerror
int&& value;intconst intintconst int&errorerror
const int value;intconst intintconst int&errorerror
const int& value;intconst intintconst int&errorerror
const int&& value;intconst intintconst int&errorerror
f ( 1 )   // 何か右辺値intconst intintconst int&intconst int &&
  • const T&& は要らない子だと思ってたけど右辺値だけ受け取りたいときに使える…?
  • 右辺値と右辺値参照が頭の中でこんがらがってあぁぁぁぁ 
  • 迷ったら const 参照使ってれば一番よさそうですね

 

ポインタになるとこうなります
  ※ const が長くて表にはまらなかったのでcとしました

T + const + *T *T * constconst T *const T * const
TargTargTargTarg
int * value;   int   int*   int   int* c int c int* int c int* c
int * const value;   int   int*   int   int* c int c int* int c int* c
const int * value;c intint*c intc int* c int c int* int c int* c
const int * cosnt  value;c intc int*c intc int* c int c int* int c int* c
  • const とポインタの関係が完璧に分かっているconst教信者の方なら、const T * とか T * const とかしたときはどうなるか、すぐに予想できましたよね?(震え声)

 

ね? templateって、素直ないい子…だよ…ね?

 

 

 

 

 

 

 

項目2 autoの型推論を理解する

 

結論templateと同じ!以上!解散!


とは言えない
みたいです…
1か所だけ異なって、auto value = {1, 2, 3, 4, 5, 12}; と{}で書いたときのみ、
value は std::initializer_list<T>という型に推論されます。

左右は全く同じ意味
auto i = 1;int i = 1;
const auto ci = i;const int ci = i;
const auto d = 1.0;const double d = 1.0;
auto d2 = d;double d2 = d;
auto& ir = i;int& ir = i;
const auto& cir = irconst int& cir = ir;
auto& cir2 = cir;const int& cir2 = cir;
auto hentai = {1};std::initializer_list<int> hentai = {1};
auto hentai = {1, 1.0};error (intなのかdoubleなのか、少しでも曖昧なため)

 

 

・auto? 知らない子ですね 

  C++にはイテレータというtemplateクラス版ポインタがあるんだけど、
  そいつが指す変数の「」を取得するためにこんなコードは書きたくないよね?

  template<typename Iterator>
  void PrintValue(Iterator iterator)
  {
      std::iterator_traits<iterator>::value_type value = *iterator;
      std::cout << value;
  }

  大丈夫。こんなの覚えなくていい。そう、autoならね。

  template<typename Iterator>
  void PrintValue(Iterator iterator)
  {
      auto value = *iterator;
      std::cout << value;
  }

 

 

・深淵を覗きに行くために…

ラムダ式の引数や関数の戻り値など、関数の定義等にもautoを使えますが、
これはtemplateの型推論になるらしいです。

    auto lambda = [](auto arg){ };
    lambda({1, 3, 4});   // error std::initializer_list<int>と推論できない

    auto plsGiveMe_initializer_list()
    {
        return {1, 2, 3};    // error std::initializer_list<int>と推論できない
    }

また、std::initialzier_list<>の型推論には以下のようにC++のバージョンに左右される面があります。(デフォルトのVisualStudio2017は、C++17以降の方の動作をします。)

ソースコード推論結果
C++14以前C++17以降
auto value = {0, 1, 2};std::initializer_list<int> value = {0, 1, 2};std::initializer_list<int> value= {0, 1, 2};
auto value = {0};std::initializer_list<int> value = {0};std::initializer_list<int> value = {0};
auto value{0, 1, 2};std::initializer_list<int> value = {0, 1, 2};error
auto value{0};std::initializer_list<int> value = {0};int value = 0;

 

 

 

 

 

 

 

 

項目3 decltypeを理解する

 

結論 : そのまんま型が返ってくる!(大体そのまんま)

 

decltypeにも例外的な動作が一つあります。
単純に名前ではない左辺値式をあたえたときは
参照がもれなく付いてくるというものです。

int n;                         // 左辺値式 n
decltype(n) → int      // 単純に名前だけの左辺値式
decltype((n)) → int& // この場合は()が付いたため複雑な左辺値式と判定されるらしい…

 

項目2の変数と次の関数を使います。   void kansu(int, double){}  

左右は全く同じ意味
decltype(i)int
decltype(cir2)const int&
decltype(hentai)std::initializer_list<int>
decltype(kansu(0, 0))void
decltype(kansu)void ( int, double )
decltype((i))int&      // 唯一の例外
decltype((i + 1 + 0.1))double  // 右辺値式は例外に含まれない

 

 

・decltype? 知らない子ですね

知らなくても大丈夫。ゴリゴリtemplate書くようになるまで必要になることはないから。
それに、必要になったらいやでも覚えなきゃいけないから。(未来の自分がそう言ってる気がする)

 

・深淵を覗きに行くために…

decltypeは、autoの用に変数の型・関数の戻り値を推論するのに使えます。書式は以下の通りです。
ただし推論の方法はdecltypeのものであり、auto や template とは異なります。

左右は全く同じ意味
decltype(auto) value = 0;
decltype(auto) func()
{
    return 0;
}
int value = 0;          // 0 はint型
int func()                 // 0 はint型
{
    return 0;   
}
const int n = 0;
decltype(auto) value = n;
decltype(auto) func()
{
    return n;
}
cont int n = 0;
const int value = n;  //templateやautoはintと推論
const int func()        //templateやautoはintと推論
{
    return n;
}
int n = 0;
decltype(auto)
value = (n); // 複雑な左辺値式
decltype(auto) func()
{
    return (n);     // 複雑な左辺値式
}
int n = 0;
int&
value = n;          // 参照が付きます
int& ILoveDecltype() // 参照が付きます
{
    return n;
}
decltype(auto) value = {1, 2, 3};
decltype(auto) func()
{
    return {1, 2, 3}; // std::initializer_list<int> ?
}
error
(autoを使いますが、型の推論方法はdecltypeのものです。そのためstd::initializer_list<int>とは推論できません。)

 

 

 

 

 

 

 

項目4 推論された型を確認する

 

結論 : IDEに頼ろう!

IDE(VisualStudioとかとかとか)で気になるトークンにマウスオーバー。
これが一番(個人比)
Boost.TypeIndexというBoostライブラリも紹介されていました。
でも変な型が出る可能性は十分あるという…

そのほかにはコンパイルエラーで確認する方法、場合によっては見づらい・不正確な型名を表示する可能性がある方法なども紹介されていました。

 

 

 

 

 

 

 

< 前の項目へ   次の項目へ >

ICPC2018国内予選参加記 Tech-ONC

こんばんえるえる〜〜
毎度ガナリヤです!
部室行かなくてすいません!活動はしてるんです!集中力の問題で家でやってます・・・(お兄さん許して・・・)
今日は、ICPC国内予選に参加したので、来年のリベンジのために参加記を残しておこうとおもいます。
 
 

チーム Tech-ONC

チームTech-ONCはTNP部員かつ、同じ競技プログラミングバイト先の三人で構成されています。
思考力・実装力担当の我らが部長!こしょう!
C++の魔法使い!サバ!
手広無力おじさん!ガナリヤ!
の三人です。
このチームの特徴として

  • 普段アルバイトで、競技プログラミング問題制作を行っている
  • 得意なことがそれぞれ違い、バランスが取れている
  • 三人共コーディングを担当できる
  • いい意味でも悪い意味でも、そこまで競技プログラミングコーディング力が離れていない(他チームは、一人だけ無茶苦茶強いところが多かったりする)

という点があります。
僕が誘わせていただき、引き受けていただきて本当に嬉しかったです!


参加記

事前準備

統計の授業を三人で抜け出してご飯を食べる。
チョコレートがおいしかった。
その後、コーディング場に移動し、それぞれマクロや本の準備をしていた。
その間、サバがVisualStudio設定RTAしてて面白かったです、来年は僕も設定できるようになりたい

16:10頃、監督の先生が到着(本当に引き受けていただきありがとうございます!)
雑談をしつつ、そわそわしながら開始を待つ。
  

ICPC予選開始

16:30から予選開始。
サバニキが印刷をぶん回しつつ、僕がA問題の紙を読み、こしょうがB問題の紙を読み始めました。
その間、サバがVisualStudioの設定やマクロの準備をしており、縁の下の力持ちでした!(またnext_combinationの実装もしてもらってしまった・・・来年までにはもっと簡単な実装にします・・・)サバありがとう!

A問題 所得格差は、N人の合計の平均を取って、平均より小さい人数を数えるだけの問題で非常に簡単でやるだけでした。年々A問題は簡単になっている気がする・・・
ハラハラしつつ、doubleのガバに気をつけてAC

  

B問題とC問題

A問題を解いた後、こしょうがB問題へ。
僕とサバでC問題に移動。

こしょうにきが解いている間、C問題を二人で話し合う。
C問題 みなとハルカス

C問題は、整数bが与えられ、1~Nまでの中で連続した整数の和がbに一致する中で、最長のものを出力せよという問題でした。
二人で話し合った結果、部分累積和で10^8までぶん回すか、しゃくとり法で実装するかの二択になりました。
ここで壮大なミス。
絶対に部分累積和じゃ通らないのに、部分累積和の案を採用。ふたりともしゃくとり法はあまりお得意なお気持ちではないため、部分累積和に逃げてしまった・・・、このミスが無ければDの実装が間に合ったかもしれない(申し訳ない)

間違った部分累積和の実装が行けそうになったとき、こしょうの実装でエラーが発生していた模様。
コードを印刷してもらって、エディタを空けてもらって入れ替わりで僕が嘘解法を実装。
ちなみに、今回のB問題はCよりずっと難しかったようで、さらっと解いてるこしょうやっぱやばい。

嘘解法のCを実装した僕
「できた!天才か〜〜〜?」←嘘解法で喜んでいるクズの図
10^9の実装のため、テストケースだけ通して、もう一度こしょうと交代。
こしょうがB問題の添字ミスと、問題文の勘違いに気づいたらしく難なくAC。こしょうにきは、問題文読み間違い以外基本的にすべて通している(すごい(すごい))

その後、こしょうに変わってもらって、投げていたテストケースを見ると、数が合っておらず、嘘解法であったことに気づく(当たり前だよなぁ?)
急いで、しゃくとり法で実装してAC。やっぱ最初からしゃくとり法にするべきでした、チキっちゃだめやね・・・
  

D問題

ここから毎回僕たちが苦戦しているD問題以降パートへ。

サバニキがD問題とE問題に目をつけていて、問題概要や、解き方のコツを教えてもらった。
D問題 全チームによるプレーオフは、サッカーの試合をするとき、すべてのチームの勝敗が一致し、全員で仲良しになる総数は何個あるか?という問題だった。

僕とサバでDはやべえな・・・となり、他の問題をいろいろ見ていた。よくよく考えるとこれが悪手だった気がする。最初からずっとDのみに取り組んでいれば、時間が間に合ったかもしれない(悔しい・・・)

その後、こしょうもDに参戦し、こしょうとサバが解き方の方針を教えてくれた。(5人なら、必ず全てのチームが2勝2敗とか、普段の自分一人のコーディングなら絶対に気づけてない・・・)

その後しばらく三人でDにうなり続け、うだうだ言いながら、意見を出しつつ、next_combinationで1と0の組み合わせを求めれば計算量はあまり増えないということに気づく(正直合ってるか分からん)
よくわからないまま、時間が無いため、僕が突発的に考えた多分正攻法ではない、汚いアイディアを実装することに。
僕とこしょうでペアプロしつつ、サバがnext_combinationの実装をしてくれた(来年までにはもっと分かりやすいライブラリつくる許して・・・)
こしょうとサバのこしょうを借りつつ、ガバガバ実装を行い、時間と戦いつつ、コーディングが完成。
奇跡に祈りつつ、実行したところ、添字エラー。添字エラーを解消している中で、時間になってしまった・・・

  


振り返り

ICPCに参戦してみて、すんごい楽しかったです。
他の人と、問題を解くためのアイディア出し合ったり、ふざけながら問題通すのって、学生のうちしかできない気がする(仕事になると、ふざけることはできない・・・)
また、自分の実装の弱さに気付かされた回でもありました・・・。他の二人の実装がすごい綺麗で、僕のコーディングがかなり汚いので、デバッグしづらくて二人がかなり僕のコードを追うの辛かったと思います。もっと簡潔なコーディングできるよう目指していきたいです。

何はともあれ、すごい楽しかった
来年もこの三人でTech-ONCとして出るという話をした。
来年は三人共、競技プログラミングがうまくなり、僕はAtCoder年内中に青色、来年のICPCまでに黄色になっているはずなので(希望的観測)、来年のチーム名はTech-ONS(O(N^2))でしょうか・・・

何も考えず、今日あったことをそのまま書いているだけで、読みづらいと思います。すいません。
それぐらい楽しかったです
明日はSoundHound頑張ろうと思います!

ガナリヤでした!

テンプレートを見ていくだけ

祝!テンプレート肥大化!

   
   
このブログには僕しか住んでいない気が・・・
にじさんじ箱推しガチ勢ガナリヤです。
今回は、自分の使用しているテンプレートが自分でも管理しきれなくなったため、公開しつつ見直していこうと思います。
この記事の一番下にお借りしたサイトなどを記述させていただきます。


まずは全体のソースコードを貼っていこうと思います。

はえ〜すっごい長い
でも、コンパイルは余裕で通るし、コード読みやすくなるしええやろ!(無謀)

   
少しずつパーツごとに見ていこうと思います!
   


include


//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>

using namespace std;

c++では、includeで使用する関数などのヘッダファイルを取り込んで使用します。
中身の実体であるcppファイルはたいてい別にあって、ヘッダファイルは宣言のみを基本的に行うのですが、標準ライブラリはすべてヘッダファイルに実装しているみたいですね。
   
   

typedef

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<int> VI;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<VI> VVI;
typedef vector<VB> VVB;
typedef vector<string> VS;
typedef vector<VLL> VVLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<int, string> PIS;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;

long longなど、よく使用する型名や、vectorなどはエイリアスをつけています。
正直あまり使用しないもののほうが多いですな・・・
   
   

数値・文字列

//数値・文字列
//------------------------------------------
inline int toInt(string s) {
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}

inline LL toLongLong(string s) {
    LL v;
    istringstream sin(s);
    sin >> v;
    return v;
}

template<class T>
inline string toString(T x) {
    ostringstream sout;
    sout << x;
    return sout.str();
}

inline VC toVC(string s) {
    VC data(s.begin(), s.end());
    return data;
}

template<typename List>
void SPRIT(const std::string &s, const std::string &delim, List &result) {
    result.clear();
    string::size_type pos = 0;
    while (pos != string::npos) {
        string::size_type p = s.find(delim, pos);
        if (p == string::npos) {
            result.push_back(s.substr(pos));
            break;
        } else {
            result.push_back(s.substr(pos, p - pos));
        }
        pos = p + delim.size();
    }
}

string TRIM(const string &str, const char *trimCharacterList = " \t\v\r\n") {
    string result;
    string::size_type left = str.find_first_not_of(trimCharacterList);
    if (left != string::npos) {
        string::size_type right = str.find_last_not_of(trimCharacterList);
        result = str.substr(left, right - left + 1);
    }
    return result;
}

template<typename T>
bool VECTOR_EXISTS(vector<T> vec, T data) {
    auto itr = std::find(vec.begin(), vec.end(), data);
    size_t index = distance(vec.begin(), itr);
    if (index != vec.size()) {
        return true;
    } else {
        return 0;
    }
}

#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)
#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)

数が多いので一つ一つ見ていきます。

  • toIntは文字列を受け取って数字にして返します。こういうの合ったほうが何かと便利ですね。速度は遅いですが・・・
  • toLongLongはtoIntのLL版
  • toStringは引数を受け取ってStringにして返します。ostringstreamってなんなんですかね・・・
  • toVCは文字列を受け取ってvectorのcharを返します。なんだかんだ変換する必要が多々あるので便利です。
  • TRIM関数は文字列をきれいにして返します。ただ、普通の場合入力は整理されているためあまり使いませんね・・・
  • VECTOR_EXISTSはテンプレートを使用し、vectorを受け取って特定のdataが存在するかどうかを返します。自分でmain内に書けるレベルですが、読みやすくするためよく使用します。
  • UPPERとLOWERは文字列を受け取ってstd::transformで大文字と小文字に変換します。このレベルは普通string型のメソッドにあるべきだと思うんですけど!!!
       
    SPRIT関数はちょっと癖が強いため以下にコードを書いていこうと思います。

    
    int main() {
    
        string str = "abc def gji";
        VS inputs;
        
        SPRIT(str, " ", inputs);
    
        return 0;
    }
    
    

これはSPRIT関数は3つの引数を受取ります。
第一引数は入力文字
第二引数は文字を分割するためのトークン文字列
第三引数は分割された結果を格納するvectorです。
vectorを使用しているので、何個に分割されるか考える必要がなく、自動で返ってくるので便利ですね・・・

   
 

四捨五入


//四捨五入 nLen=小数点第N位にする
//------------------------------------------

//四捨五入
double ceil_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.9);
    return dOut * pow(10.0, -nLen);
}

//切り捨て
double floor_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut);
    return dOut * pow(10.0, -nLen);
}

//切り上げ
double round_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.5);
    return dOut * pow(10.0, -nLen);
}

//n桁目の数の取得
int take_a_n(int num, int n) {
    string str = toString(num);
    return str[str.length() - n] - '0';
}

ceil, floor, round関数の拡張のようです。
自分でもまだ仕組みをよく理解していないため、勉強しようと思います。
標準ライブラリの関数より、小数点以下の桁数を指定できるため細かいです。
take_a_nはそのままです。/=10とかするのが面倒なので文字列にしてから取り出してます。

   
   

進数

//進数
//------------------------------------------

//"1111011" → 123
int strbase_2to10(const std::string &s) {
    int out = 0;
    for (int i = 0, size = s.size(); i < size; ++i) {
        out *= 2;
        out += ((int) s[i] == 49) ? 1 : 0;
    }
    return out;
}

//"123" → 1111011
int strbase_10to2(const std::string &s) {
    int binary = toInt(s);
    int out = 0;
    for (int i = 0; binary > 0; i++) {
        out = out + (binary % 2) * pow(static_cast<int>(10), i);
        binary = binary / 2;
    }
    return out;
}

//"ABC" 2748
int strbase_16to10(const std::string &s) {
    int out = stoi(s, 0, 16);
    return out;
}

//1111011 → 123
int intbase_2to10(int in) {
    string str = toString(in);
    return strbase_2to10(str);
}

//123 → 1111011
int intbase_10to2(int in) {
    string str = toString(in);
    return strbase_10to2(str);
}

int intbase_16to10(int in) {
    string str = toString(in);
    return strbase_16to10(str);
}

//123→ "7B"
string intbase_10to16(unsigned int val, bool lower = true) {
    if (!val)
        return std::string("0");
    std::string str;
    const char hc = lower ? 'a' : 'A';     // 小文字 or 大文字表記
    while (val != 0) {
        int d = val & 15;     // 16進数一桁を取得
        if (d < 10)
            str.insert(str.begin(), d + '0');  //  10未満の場合
        else //  10以上の場合
            str.insert(str.begin(), d - 10 + hc);
        val >>= 4;
    }
    return str;
}

//整数を2進数表記したときの1の個数を返す
LL bitcount64(LL bits) {
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);
    return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);
}


普通の人は用意してないと思うレベルで用意しています。
TechFULの中級編をやり続けるとこうなります。
ハゲるかと思いました。
strbaseは文字列を受け取ってint型を返します。
intbaseはint型を受け取ってint型を返します。
bitcount64の2進数にしたときの1の個数を数える関数のビット演算の仕組みがよくわかっていないので要学習ですね・・・

比較


//comparison
//------------------------------------------
#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define C_MIN(a, b) ((a)<(b)?(a):(b))
#define C_ABS(a, b) ((a)<(b)?(b)-(a):(a)-(b))

c++の標準ライブラリのmin, maxがクソなので使っています。
理由としてはminの片方にlong longなどをぶち込むと反応してくれません。平成アホくさ丸。
ただ、文字列とかぶち込むとC_ABSなどは実行時エラーを吐くので気をつけましょう。

   
   

コンテイナー


//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define REVERSE(c) reverse((c).begin(), (c).end())
#define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.)
#define SUML(obj) accumulate((obj).begin(), (obj).end(), 0LL)
#define UB(obj, n) upper_bound((obj).begin(), (obj).end(), n)
#define LB(obj, n) lower_bound((obj).begin(), (obj).end(), n)
#define BS(v, n) binary_search(ALL(v), (n))
#define PB push_back
#define MP make_pair

   
ここらへんは他の方のテンプレートでもよく見ますね・・・小文字派の方もいらっしゃいますが・・・
大体は見ての通りマクロで、vectorなどのSTLをいじるものです。
マクロとか利用したほうが速度だけでなく、ソースコードがかなり読みやすくなりました。
使ってみると、結構欠かせないものになる気がします。
   
   

入出力



//input output
//------------------------------------------
#define GL(s) getline(cin, (s))
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define OUT(d) std::cout<<(d);
#define OUT_L(d) std::cout<<(d)<<endl;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<(d);
#define EL() std::cout << "\n";
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}


入出力で使用するものです。

  • GLはgetlineの略で予め宣言してあったstring変数に一行分格納します。大体使用するときはこのあとSPRIT関数に直結ですね・・・
  • INITは入出力がガバガバに多いときは使用します。ただ、これやってギリギリセーフなときは、どこか計算量がガバガバに多い気がします。
  • OUT, OUT_Lはcoutの「<<」が面倒なので使用しています。
  • FOUTはdouble型の小数を表示するときに、指定桁をnで、表示内容をdで指定することで、○○桁に対応することができます。
  • SHOW_VECTORはvector型をぶち込むことでさらっとアサートで表示してくれます。vector型の中身をさらっと確認したいときにデバッグ用で使用してます。
       
       

REP


//repetition
//------------------------------------------
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)å
#define REP(i, n)  FOR(i,0,n)
#define RREP(i, n) for(int i = n;i >= 0;i--)
#define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i)
#define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i)
#define REPLL(i, n) for(LL i=0;i<LL(n);++i)
#define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i)
#define FOREACH(x, v) for(auto &(x) : (v))
#define FORITER(x, v) for(auto (x) = (v).begin(); (x) != (v).end(); ++(x))

これも他の方のテンプレートでもよく見かけますね・・・
大体の内容はこれで書くことができます。
ただ、indexが複雑なときは普通にforで書いたり、正直–iなどのときはRREPで合ってるのか怖いので、forで書いちゃいますね・・・
FOREACHや、FORITERは、STLなどのset,mapなど、indexが扱いづらいものに使用することが多いです。

   
   

math


//math
//--------------------------------------------

//min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
    if (min <= aim && aim <= max) {
        return true;
    } else {
        return false;
    }
}


template<class T>
inline T SQR(const T x) { return x * x; }

template<class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
    if (!y)return 1;
    else if ((y & 1) == 0) {
        return SQR(POW(x, y >> 1));
    } else return POW(x, y ^ 1) * x;
}


template<typename T>
constexpr T ABS(T x) {
    static_assert(is_signed<T>::value, "ABS(): argument must be signed");
    return x < 0 ? -x : x;
}

//partial_permutation nPr 順列
//first・・最初の数
//middle・・r(取り出す数)
//last・・n(全体数)
template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
    reverse(middle, last);
    return next_permutation(first, last);
}

//combination nCr 組み合わせ
//first1・・最初の数
//last1==first2・・r(取り出す数)
//last2・・n(全体数)
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator first1, BidirectionalIterator last1, BidirectionalIterator first2,
                      BidirectionalIterator last2) {
    if ((first1 == last1) || (first2 == last2)) {
        return false;
    }
    BidirectionalIterator m1 = last1;
    BidirectionalIterator m2 = last2;
    --m2;
    while (--m1 != first1 && !(*m1 < *m2)) {
    }
    bool result = (m1 == first1) && !(*first1 < *m2);
    if (!result) {
        while (first2 != m2 && !(*m1 < *first2)) {
            ++first2;
        }
        first1 = m1;
        std::iter_swap(first1, first2);
        ++first1;
        ++first2;
    }
    if ((first1 != last1) && (first2 != last2)) {
        m1 = last1;
        m2 = first2;
        while ((m1 != first1) && (m2 != last2)) {
            std::iter_swap(--m1, m2);
            ++m2;
        }
        std::reverse(first1, m1);
        std::reverse(first1, last1);
        std::reverse(m2, last2);
        std::reverse(first2, last2);
    }
    return !result;
}

ガナリヤの情弱ポイントがバレちゃいますね・・・
数学が苦手なら予め用意していればいいだけの話だ!!!成長はしないが!

  • BETWEENはminとmaxの間にデータがあるかboolを返します。TechFULのErrorを避けるのが面倒だったので作りました。
  • SQRは二乗です。
  • POWはxをy回累乗したものを返します。こういうのはmain内にあるとコードが汚くなるのでありがたいです。標準ライブラリより、型の対応が多いためよく使用します。
  • ABSも同様の理由でよく使用します。
  • next_partial_permutationはnPrの順列をvector型などで取り出すために使用します。do while(next_permutation())の形で使用するとvector型の要素が自動で変更されていくため便利です。仕組みはよくわかりません
  • next_combinationは、標準ライブラリから落選してしまったようなので海外文献から探して使用しています。組み合わせを実現し、do whileで使用します。国内のブログなどには、利用例がないため、ちょっとまだ完璧に使い方が分かりきってはないです・・・
       
       

数学法則

   


//numeric_law
//--------------------------------------------

template<typename T>
constexpr bool ODD(T x) {
    return x % 2 != 0;
}

template<typename T>
constexpr bool EVEN(T x) {
    return x % 2 == 0;
}

//最大公約数
template<class T>
inline T GCD(const T x, const T y) {
    if (x < 0)return GCD(-x, y);
    if (y < 0)return GCD(x, -y);
    return (!y) ? x : GCD(y, x % y);
}

//最小公倍数
template<class T>
inline T LCM(const T x, const T y) {
    if (x < 0)return LCM(-x, y);
    if (y < 0)return LCM(x, -y);
    return x * (y / GCD(x, y));
}

//ax + by = 1
//x,yが変数に格納される
template<class T>
inline T EXTGCD(const T a, const T b, T &x, T &y) {
    if (a < 0) {
        T d = EXTGCD(-a, b, x, y);
        x = -x;
        return d;
    }
    if (b < 0) {
        T d = EXTGCD(a, -b, x, y);
        y = -y;
        return d;
    }
    if (!b) {
        x = 1;
        y = 0;
        return a;
    } else {
        T d = EXTGCD(b, a % b, x, y);
        T t = x;
        x = y;
        y = t - (a / b) * y;
        return d;
    }
}

//素数
template<class T>
inline bool ISPRIME(const T x) {
    if (x <= 1)return false;
    for (T i = 2; SQR(i) <= x; i++)if (x % i == 0)return false;
    return true;
}

//素数をtrueとして返す
template<class T>
VB ERATOSTHENES(const T n) {
    VB arr(n, true);
    for (int i = 2; i < SQR(n); i++) {
        if (arr[i]) {
            for (int j = 0; i * (j + 2) < n; j++) {
                arr[i * (j + 2)] = false;
            }
        }
    }
    return arr;
}

// a <= x < b の素数を返す
template<typename T>
VB ERATOSTHENES(const T a, const T b) {
    VB small = ERATOSTHENES(b);
    VB prime(b - a, true);

    for (int i = 2; (T) (SQR(i)) < b; i++) {
        if (small[i]) {
            for (T j = max(2, (a + i - 1) / i) * i; j < b; j += i) {
                prime[j - a] = false;
            }
        }
    }

    return prime;
}

//約数
template<class T>
vector<T> DIVISOR(T n) {
    vector<T> v;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) {
                v.push_back(n / i);
            }
        }
    }
    sort(v.begin(), v.end());
    return v;
}

//組み合わせ個数
template<typename T>
T NCR(T n, T r) {
    T ans = 1;
    for (T i = n; i > n - r; --i) {
        ans = ans * i;
    }
    for (T i = 1; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

//行列
int MATRIZ_CHAIN(VI &p, VVI &s) {
    const static int INF = 1 << 20;
    const int n = p.size() - 1;
    VVI X(n, VI(n, INF));
    s.resize(n, VI(n));
    for (int i = 0; i < n; ++i) X[i][i] = 0;
    for (int w = 1; w < n; ++w)
        for (int i = 0, j; j = i + w, j < n; ++i)
            for (int k = i; k < j; ++k) {
                int f = p[i] * p[k + 1] * p[j + 1];
                if (X[i][k] + X[k + 1][j] + f < X[i][j]) {
                    X[i][j] = X[i][k] + X[k + 1][j] + f;
                    s[i][j] = k;
                }
            }
    return X[0][n - 1];
}

//最長増加部分列
VI LIS(const VI &a) {
    const static int INF = 99999999;
    const int n = a.size();
    VI A(n, INF);
    VI id(n);
    for (int i = 0; i < n; ++i) {
        id[i] = distance(A.begin(), lower_bound(A.begin(), A.end(), a[i]));
        A[id[i]] = a[i];
    }
    int m = *max_element(id.begin(), id.end());
    VI b(m + 1);
    for (int i = n - 1; i >= 0; --i)
        if (id[i] == m) b[m--] = a[i];
    return b;
}

//最長共通部分列 string->toVC
template<typename T>
vector<T> LCS(const vector<T> &a, const vector<T> &b) {
    const int n = a.size(), m = b.size();
    vector<VI> X(n + 1, VI(m + 1));
    vector<VI> Y(n + 1, VI(m + 1));
    REP(i, n) {
        REP(j, m) {
            if (a[i] == b[j]) {
                X[i + 1][j + 1] = X[i][j] + 1;
                Y[i + 1][j + 1] = 0;
            } else if (X[i + 1][j] < X[i][j + 1]) {
                X[i + 1][j + 1] = X[i][j + 1];
                Y[i + 1][j + 1] = +1;
            } else {
                X[i + 1][j + 1] = X[i + 1][j];
                Y[i + 1][j + 1] = -1;
            }
        }
    }
    vector<T> c;
    for (int i = n, j = m; i > 0 && j > 0;) {
        if (Y[i][j] > 0) --i;
        else if (Y[i][j] < 0) --j;
        else {
            c.PB(a[i - 1]);
            --i;
            --j;
        }
    }
    REVERSE(c);
    return c;
}

//コイン C総額 cs使用できるコインの種類
VI money_change(int C, VI &cs) {
    const int INF = 99999999;
    int n = cs.size();
    VI xs(C + 1, INF);
    VI ys(C + 1);
    xs[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int c = 0; c + cs[i] <= C; ++c) {
            if (xs] > xs + 1) {
                xs] = xs + 1;
                ys] = c;
            }
        }
    }
    VI zs;
    for (int c = C; c > 0; c = ys) {
        zs.push_back(c - ys);
    }
    return zs;
}


   
長すぎぃ!
でも合ったほうが便利だからええやろ(甘え)

  • ODDは奇数かどうか判定します。inlineをつけてないのでつけようかと思います。
  • GCDは引数x, yの最大公約数を算出します。ユークリッドの互除法をしています。
  • LCMは最小公倍数を算出します。ab = GCD(a,b)*LCM(a,b)という法則があるため、GCDで算出した答えを利用してLCMを算出します。
  • EXTGCDはax+by=1となるx,yが格納されます。仕組みがまだ良くわかってないです。
  • ISPRIMEは引数が素数かどうか判定します。一つの数字のみでいいならこちらを使います。
  • ERATOSTHENESは素数のふるいを行います。配列に格納しておいて、素数を見つけるとSQR(n)分まで回すことで素数以外をfalseにすることで早く計算できます。
  • DIVISORは約数を算出してvectorにして返します。n*nのsqrt以内に半分の素数は存在するため、そちらで算出し、i!=n/iで反対側の素数を算出しています。
  • NCRはnCrの意味で組み合わせを算出します。ただいま、先にかけ算を行っており、数がおおきいとオーバーフローしてしまうため、改善が必要かもしれませんね。
  • LISは部分増加列を算出します。ここらへんはよく出るので、どんな仕組みだったからって確認するために記述させていただいてます。
  • LCSは二つの文字列の部分増加列です。もはや辞書的な役割です。
       
       

confirmation

   


//confirmation
//--------------------------------------------

//clear memory
#define CLR(a, b) memset((a), (b),sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


   
メモリーの初期化(配列に限る)や、デバッグで使用するマクロです。
fillをまだマクロで定義してないのでfillも実装しとこうと思います。

   
   
   
  


あ〜すっげぇキツかったぞ〜
自分が以下にライブラリに頼っているかがバレましたね・・・(バレてるんだよなぁ・・・)
マクロを使うと結構楽に、はやく書けますし、よくわからん数学の部分をオーバーラップできます。
自分なりのテンプレートを作って競プロやると、結構楽しいかもしれません。
僕は、結構使えそうなマクロ作ったり探したりする時間が、競プロの中で一番好きです。(こんな人間になってはいけない)

P.S.

かえみと尊い・・・尊くない・・・?

ドメイン超えに一日を費やした話

こんばんは・・・
毎度おなじみガナリヤです!

今回は、NodeJsのクロスドメイン超えの話です。
初めての技術系ブログになるんですかね・・・

宣伝

現在、昔TNPにあったらしいICPC対策室なるものが、再び復活しようとしています。
活動内容としては、競技プログラミングを行い、実装力・アルゴリズム力をつけるというものです。
・・・正直、大学生からプログラミングを初めている身としては、アルゴリズムが世知辛いのじゃぁ〜

そんなこんなで、ICPU対策室復活に向けて、Discordの秋田大学ICPU対策室サーバーを立て、現在競技プログラミングを便利にするBotを製作中です。

問題

DiscordのBotはいろいろなプログラミング言語で作れますが、ガナリヤは現在Javascriptで記述しています。
Javascriptの特徴は何と言っても、クライアント側のブラウザで動くというところです。
最近では、NodeJsというサーバー側で実行するエンジンを使用することで、クライアント側だけでなく、サーバー側までJavascriptで制作出来るようになりました。
もしかしたら、世の中世知辛くないのかもしれないのじゃ・・・

そんなNodeJsとJavascriptで、HackerRankから、一ヶ月後までのコンテスト情報を取得するコマンドを作成しようとしていました。
HackerRankの情報はxml形式で取得できるため

  1. jQueryでxml形式で取得
  2. 取得したxml形式をxml2jsでJSON形式へ
  3. JSONからmomentを使って適切なコンテストのみ取得

という工程で行おうと思っていました・・・

事件発生

jQueryがガバガバでした。
おじさんが、jQueryで外部サイトの情報を取得しようとすると「それ以上はいけない」と、xmlが取得できませんでした。
取得できない理由はクロスドメイン問題にあります。

理想としては上のような状態です。
自分のクライアントとサーバーと、欲しい情報があるサーバーがそれぞれ通信できています。
しかし、最近のjQueryはクソみたいな発展を果たし(最近はほぼ使われなくなってきている)、他のサーバーとの通信が行えず、同じドメインしか通信できなくなりました。
これがクロスドメイン問題です。

改善策

改善策を色々と探した結果最初の改善策は以下のものでした。
1. phpファイルを利用してデータ取得のみをphpで行う。
2. 人力でxml形式を取得しておき、サーバーにためておく。

1の方法はうまく行きませんでした。理由としては、使用しているデプロイ先が基本的にjsのみであり上手に動作しなかったのが原因です。
2の方法は取りたくありませんでした。人力はクソ。さてはウンチだなおめー

結局・・・

npmモジュールでいいのないかなと探していたら、やっぱありました(最初からやr)
こちらのcheerioです。
クロスドメインも、モジュール内でいい感じにうまくやってくれているらしく、非常にありがたいですね・・・
コードは、きれいにしてからあげます・・・////

 

これもうわかんねえな

 改行がうまくwordpress内でされないので改善したい。

Unity 2Dライトについて

お久しぶりです。またもやガナリヤです。
最近はバイト先でうまく教えられなくて辛い毎日です。
もっとうまく教えたいものですね・・・・

現在けもふれパズルのリファクタリングを行うためのクラス構造を考えており、することが特に今はないため、Unityを再び触っています。
去年はC#の基礎と、使い方もわかっていないのに、インターフェースとかTのtypenameとかをやってたためUnityがさっぱりわかってませんでした。
今、久しぶりに触ってみると多少わかるようになっており、時間が立つのは早いものだと感じました(もう三年生になってしまうのですね・・)

Unity2Dにおいて、画像を光らせる方法を模索したので自分用にここでまとめておこうと思います。

1.Post Effect
現在のUnityのバージョン2017では、画面に行うエフェクトを使うためには、Unity公式が配布しているunity post processing stackというアセットがあります。
これは、調べたところによると、Unityのエディタでフレームとして出力したあと、post Processing stack が、それを更に加工して出力しています。
つまり、出来上がったものをさらに、調味料とかを入れて完成させているわけですね・・・(わかってない)
使い方としては、
1.アセットのダウンロード
2.メインカメラにPost Processing Behaviourをアタッチ
3.プロジェクトのcreateからPost Processing Profileを作成
4.PostProcessingProfileをメインカメラのPostProcessingBehaviourにアタッチします。
これであとは、PostProcessingProfileをちょちょっと弄るだけで、いろいろな画面エフェクトが行えるというわけらしいのです。
今回は、Bloomを使用しますが、それはこのあとに記述していこうと思います。

2.Emission
Unityには
・シェーダー
・マテリアル
と言うものがあるらしいのです。
シェーダーは、Unity内のゲームオブジェクトのレンダリングの際に、どのように表現するかを記述するらしいのです。(表面をどれくらい光らせるか、模様はどうするかなど・・・)
マテリアルは、シェーダーやSpriteなどを含み、ゲームオブジェクトの属性としてアタッチする際につけるらしいです。
つまり、マテリアル=シェーダー+テクスチャ+色とか・・
の上記の式が成り立つはずです。

そして、EmissionはシェーダーであるStandardSharderの項目に含まれており
「その物体がどのくらいライトを反射し、他に影響をあたえるか」
を表しています。
Emissionが高いほど、自分の色を光らせて周囲の物体に影響をあたえることができるのです!(3D)

ん・・・・・?Diffuseシェーダーとは何が違うねん・・?

調べたところによると、
Emissionは、他にライトがなくてもある程度光る(自分の持つColor+Emissionのため)
Diffuseは、他にあるライトを反射して、初めて光る
という違いのようです。

このEmissionとDiffuseというシェーダーを使えば光らせられる!
・・・と思っていた時期が僕にもありました。
3Dではこの方法でうまく行ったのです・・・
しかし、2Dでは、ライトのレンダリングの関係なのか
EmissionでもDiffuseでも、オブジェクト自体のみが多少光り、他の物体に何も影響を与えます!
ああいけません!(ピングー)

そこで次の方法を考えました。

3.Point Lightを使う
 結局ライトを使えばよいのではという発送に至りました。
Unityではライトを簡単に使うことができます。
Create→Lightで自分の好きなライトを選択すればシーンに配置されます。
Lightの種類はたくさんありますが、だいたい使うのは2つです。
一つ目はDirectionalLight、これは太陽光などの、どの角度なのかはあまり関係なく、シーンに配置すれば、すべての場所が明るくなります。基本光りとして使えますね・・
二つ目は、PointLight、これは、懐中電灯などの、ある一定の範囲のみを明るくするときに使用することができます。

PointLightを使えば特定のものを明るくできる!
そう思っていたじk(ry

僕の作りたいゲームはスマホ向け・・・
しかも、PointLightを多分50個ほど生成することになります。
これは無理だぁ・・・

4.Emission+PostProcessingEffect
最終的にこの内容に至りました。
シェーダーの項目であるEmissionと、PostProcessingに含まれているBloomを使用します。

まず、Emissionを1以上に設定してオブジェクトを白く光らせます。(この時、エディタ上では、HDRと表示されます。HDRは、物体の表示するRGB(255,255,255)の明るさの範囲を超えているよ!、という意味で、HDRにすることで、普段は表現できない明るさを表現することができます。この表現できない明るさが、他の物体に影響を与えるということらしいです(3D))

Emissionを利用することで、オブジェクトが少し白く光りました。
そこにPostProcessingのBloomを使用します。
Bloomは、すでに描画されたフレーム内の白色に近い部分を抜き取り、白色の部分をぼやかして乗算することで、まるで光っているような表現を行うことができます。
Intensity(光の強さ)やtherouseなんとか(光らせる白色の閾値)を設定することでどのぐらい光らせるかを決められます。

Emissionでオブジェクトを少し白く光らせ、Bloomでそれをぼやかすことで、まるでオブジェクトが自分で発光しているかのような表現を行うことができそうです。
この方法で新しいスマホゲームを作ってみようと思います。

わかりづらい記事かつ、情報もあやふやですみません。Unity初心者のため、まだ仕組みがよくわかってません。
いずれ画像も追加していこうと思います。

つたない文章でしたがお許し下さい!
ガナリヤでした!