ドラゴンクエスト III モバイル版 が配信開始されたと聞いてはプレイせずにはいられない、ということで、さっきクリア。
何かやりこみなどするときに影響しそうなのは、光のドレスとドラゴラムの変更くらいかなー。 あとは至ってそのままSFC版でした。GB版のモンスターメダル集めとかを残した方がモバイルには向いてそうだけど、 そうしなかったのはなんでだろう。
std::cout << "Hello, World!" << std::endl;C++の話が続くことに特に意味はないのですが、いや、改めて考えると面白いなーと思ったので。 @DecimalBloat さんのポスト を見て @Cryolite さんのポスト を思い出した上で改めてこの何の変哲もないハローワールドを見てみると、この１行だけでも、 良くも悪くも C++ の色々な側面がつまってるんだなあ、 と 蛇に足をはやしたく なった次第です。
std::cout << "Hello, World!" << std::endl;
「名前空間」 で分類することで、名前の衝突を防げます。
標準ライブラリはすべて、std 名前空間に入っています。
std::cout << "Hello, World!" << std::endl;
ostream という「クラス」のオブジェクトが変数 cout に入っています。
オブジェクト指向な感じです。
cout は「グローバル変数」です。
全ての変数は必ず何かのクラスに属させる必要がある Java 等と違い、
グローバルに変数を置いちゃえます。
std::cout << "Hello, World!" << std::endl;
「演算子オーバーロード」。<< という演算子を、
組み込みの意味（シフト演算）と違う動作をするように多重定義しています。
ただそれだけのように見えますが、実は、ここでは更に、「ADL (Argument Dependent Lookup)」
と呼ばれる、C++の仕様の中でも一二を争うトリッキーな仕組みが発動しています。
この << 演算子の多重定義、cout のメソッドとかではなく、こんな、
namespace std { ostream& operator<<(ostream& os, const char* s) {...} }
std 名前空間にあるグローバル関数なんです。名前空間の中にある関数を、
std::<< などと修飾せずに呼び出せてしまうのは、本来はおかしい。
これを呼び出せるようにするための仕組みが ADL です。引数 cout の型が名前空間
std で宣言されている型だったら、たとえ関数名がstd::修飾されていなくても、
勝手に std:: にも探しに行きます。
演算子のための特殊仕様というわけでもなく、任意の関数呼び出しでADLは発動します。
std::cout << "Hello, World!" << std::endl;
「文字列リテラル」の型はconst charの配列型ですが、上に上げたように、出力関数の引数は
const char*型です。配列がその先頭要素を指すポインタへ入れ替わる、C言語から続く
"配列とポインタがごっちゃになる人が多い問題" の芽の一つがこんなところに…。
std::cout << "Hello, World!" << std::endl;
出力関数の引数、で思い出しました。ここの cout は「参照」の形で
operator<< に渡されてますね。値コピーでもなく、ポインタをとって渡すのでもなく、
「参照」という三本目の柱を立てたのは C++ の特徴的な面かも。
あと、型といえば「const」っていう修飾子もJava等には引き継がれなかった特徴かな。
というか、型と言えば重要なことを忘れてました。ADLの説明の時は簡単のためにちょっと嘘の型定義を張ってました。
namespace std {
template<class traits>
basic_ostream<char,traits>& operator<<(basic_ostream<char,traits>&,
const char*);
}
正しくはこうです。「テンプレート」です。basic_ostream
というクラステンプレートは２つ型パラメータを持つ型で、その１個目が char
な時なら２個目がなんであっても適用される関数テンプレートが、この operator<< です。
std::cout << "Hello, World!" << std::endl;
endl が「関数ポインタ」であることをご存じでしょうか。
改行を出す働きだから実は "\n" という文字列に違いない、と思ったら間違いです。
このコードは std::endl( std::cout << "Hello, World!" ); と書いても同じ動きをします。
endl はそういう関数、この << 演算子は、関数を引数にとる、高階関数です。
std::cout << "Hello, World!" << std::endl;
また演算子オーバーロードですが、今度はグローバル関数じゃなくて cout の「メンバ関数」です。
これはメンバ関数を呼んでます。
C++ の演算子オーバーロードはメンバ関数でもグローバル関数でもできます（一部メンバ関数限定のものもあり）。
参考までに型定義を貼り付けると…
namespace std {
template <class charT, class traits = char_traits<charT> >
class basic_ostream : virtual public basic_ios<charT,traits> {
...
basic_ostream<charT,traits>& operator<<
(basic_ostream<charT,traits>& (*pf)(basic_ostream<charT,traits>&));
};
}
こんなんです。
そういえば、"Hello World １行で" に反するのでノーカンですけど、
こう一歩潜ると「virtual 継承」なんかも出てきてますね。
というわけで、Hello World から眺める C++ をお送りしました。
C++の標準アルゴリズム＆データ構造ライブラリであるSTLですが、
vector と map と sort 関数しか使ったことない、
そんな人が多いんじゃないかと思います。まあ for_each やら transform
やら大抵の関数は凄く簡単なループで手書きできちゃいますし、
というか、C++ (03) の場合関数オブジェクトを作るのが面倒なので、ループで書いた方が楽ですし、ね。
…と思う人でも、 逆に、 「簡単なループで手書き」 するのが難しいようなちょっと凝った機能の関数は、面白いんじゃないでしょうか。 というわけで紹介してみます。 別名、「そんな関数あったんだー」と言われたことがあるものリストです。
int[] a = {1, 2, 3, 4};
next_permutation( a+0, a+4 ); // a = {1, 2, 4, 3} になる
next_permutation( a+0, a+4 ); // a = {1, 3, 2, 4} になる
next_permutation( a+0, a+4 ); // a = {1, 3, 4, 2} になる
データの並び替えパターンを全列挙するための関数です。{1,2,3,4} の並び替え方は24通りあるので、 24回 next_permutation を呼ぶと全部のパターンを作ることができます。 順番当てクイズみたいなのを総当たりで突破するときとかに使えます。 覆面算を総当たりで解くとか。
この関数の機能は知ってる、という人は多いと思うんですけど、実装の仕方はどうでしょうか。 意外とシンプルで面白いので、暇つぶしに考えたりソースを読んだりしてみると楽しいです。
追記：必ずソートしておくこと！！！！！！！！！！！！！！！！！！１１１１
だそうです。どういうことかというと、
next_permutation は {4,3,2,1} から {1,2,3,4} のように戻る瞬間に false を返すので、
それを使って sort(...); do { ここで処理 } while( next_permutation(...) );
と書いて全パターン列挙するイディオムがあるんですが、これをやるときは、必ず最初にソートしないと全部出ません。
気をつけて下さい。
int[] a = {5, 3, 6, 2, 4, 1};
partial_sort( a+0, a+3, a+6 ); // a = {1, 2, 3, 5, 6, 4} か何かになる
「途中までソート」関数。小さい方から何個か（この場合は３個）まではちゃんとソートするんだけど、 あとは適当な並びで放置しておく関数です。 ソートした場合の上位 r 個 を、全部ソートするよりも、最小値をr回取り出すよりも、スピーディに取り出すための関数です。 リンク先のtsubosakaさんの記事に書かれているように、実装は、 ヒープを途中まで作って中途半端にヒープソートする感じのが典型的だと思います。
int[] a = {5, 3, 6, 2, 4, 1};
nth_element( a+0, a+2, a+6 ); // a = {2, 1, 3, 6, 4, 5} か何かになる
「途中まで」度をさらに極めると nth_element になります。 指定した１要素だけはちゃんとソートする関数。 このサンプルでは a+2 を指定しているので、a[2] にだけはソートしたときに入るはずの値… 3 が入ります。 それより左には 3 より小さい物がソートされずに適当な順番で残って、 それより右には 3 より大きい物がソートされずに適当な順番で残ります。 一カ所しかちゃんとしない分、partial_sort よりもっと速いです。
「ソートしたらジャスト r 番目に来る物を知りたい」 「ソートしたときの上位 r 個が欲しいんだけど、その r 個自体はソートされてなくていいのでとにかく速く欲しい」 とかが使いどころです。あとは partial_sort との合わせ技で、 「上位 n 番目から n+r 番目が欲しい」 ときに、まず nth_element で n 番目を固定してから後ろ側を parital_sort で r 個切り出すなど。
俺はヒープソートよりクイックソートが好きだ、というクイックソート派の皆様には朗報ですが、 このアルゴリズムの典型的な実装は「中途半端にクイックソート」です。 クイックソートの１ステップで左右に要素を分けたあと、両方をソートするのではなく、 n番目が入っている側だけ再帰的に中途半端クイックソートを掛けていきます。
俺はマージソートが好きだ、というマージソート派の方々は、 何か中途半端にマージソートして面白い結果を計算するアルゴリズムを編み出すとよいと思います。
int[] a = {1, 2, 3, 4, 5, 6};
rotate( a+0, a+2, a+6 ); // a = {3, 4, 5, 6, 1, 2} になる
{1,2}+{3,4,5,6} だったのを {3,4,5,6}+{1,2}
にぐるっと入れ替えます。
「使いまくってるよ」と A. Alexandrescu さんが言ってたけど具体的にどう使うんだろう。
頻繁にこれを使うならリンクリストをつなぎ替えてrotate実現する方が良さそうにも思うけれど。
この前、
あるGCアルゴリズムの話を聞いてて実装に中途半端rotateは使いたいなーと思ったことはあります。
機能のわかりやすさに比べると、実装は、余計なメモリを使わないでやるとなると意外と頭を使うもので、 自作してみるとこれもちょっと楽しいです。コード量は別に大したことないんですけど、 「一度も試し実行せずに一発で正しい実装を書け」 と言われたら、STLの全アルゴリズムの中でこれが二番目に自信ないですね。 ちなみに一番目はぶっちぎりで inplace_merge です。