C/C++

Posts filed under C/C++

わんくま勉強会東京82でごまかした8パズルのパターン数を調べてみたが間違ってた

Filed in C/C++, prog

 昨日のパターンを調べた件が会社のパズル詳しい人におかしいと突っ込まれたので考えてみた。

 偶置換を一個入れ替えると必ず奇置換なんだから確かに$\frac{8!}{2}$になるべき。
 ということでコード書き直し。要するに巡回置換作るところの添字の取り方がおかしかった。
 参照済みの添字の管理をもうちょっとうまくやれそうな気がするけどめんどくなったのでこれで。

 あと地味にalgorithmインクルードしてなかった (職場でIDEONに投げるまで気づかなかった)。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
bool is_pazzleout(const std::vector<int>& seq)
{
std::vector<int> referenced(seq.size(), 0);
int sum = 0;
for (int i = 0; i < seq.size(); i = std::distance(referenced.begin(), std::find(referenced.begin(), referenced.end(), 0))) {
int f = i + 1;
std::set<int> cyclic;
cyclic.insert(f);
referenced[i] = f;
for (int j = i; f != seq[j]; j = seq[j] - 1) {
//            std::cout << "f: " << f << ", seq[" << j << "]: " << seq[j] << std::endl;
cyclic.insert(seq[j]);
referenced[seq[j] - 1] = seq[j];
}
sum += cyclic.size() - 1;
}
return sum % 2;
}
void print(const std::vector<int>& seq)
{
std::cout << "( ";
std::for_each(seq.begin(), seq.end(), [](int x) {
std::cout << x << " ";
});
std::cout << ")";
if (is_pazzleout(seq)) std::cout << "*";
std::cout << std::endl;
}
int main()
{
std::vector<int> complete;
for (int i = 1; i <= 8; ++i) {
complete.push_back(i);
}
do {
print(complete);
} while (std::next_permutation(complete.begin(), complete.end()));
return 0;
}

ストラウストラップのプログラミング入門はじめました

Filed in C/C++, prog,

 こんにちはあおいたんこと長月葵です。

 長月も査読に参加したプログラミングの教科書「ストラウストラップのプログラミング入門」がもうすぐ発売です!
 C++erなら誰もが知ってるストロウストラップ御大が手ずから書いた、C++を使ったプログラミングの入門書として名高いProgramming Principle and Practice Using C++の日本語版です。
 約二年に渡る査読作業の結果妙な訳も概ね無くなって初心者も中級者も上級者も一読しておくべき本に仕上がったと思います。
 Amazonでも予約が始まったみたいなのでリンク貼っときますよ。

 

coutの動作に軽く驚いた

Filed in C/C++

わんくまの方に投稿したんですがなにやらいつ見てもさーびすあんあv(ryなのでこっちにも。

ちょっと古いエントリへのリンクで恐縮ですが。

http://d.hatena.ne.jp/y-hamigaki/20091212#1260635305

wcoutにchar食わせられるの? と言う話題に対してこのURLが示されていたので見てみたら吃驚の動作。

長月は普通の環境でC++使う事はあんまりないのでcout自体まず使わないんですが、たまに使う時もあまり気にせず日本語含みならwcout程度で使ってました。詳しく見るとこんな動きするんですね。

C++のオーバーロードとテンプレートむずかしすなー。

int i の i ってなあに?

Filed in C/C++, prog

 ちょっと前に表題の質問を受けました。更にアクセス解析を見てると同じ質問でGoogleから飛んできてる人が少なからずいたのでお答えします。
 C言語なんかでプログラミングしてるとループカウンタとかでよく見る int i なんですが、回りのプログラマの皆様に聞いてみたところ、多くの人が「int の i なんじゃないの?」と返されました。なるほど確かに int の一時変数なんだから適当に int の頭文字でいいやというのもあるかもしれません。実際の由来も似たような発想なのである意味で正解でしょう。
 しかし実際にはこれC言語以前に発祥が確認されてます。
 今有力とされている由来としては、Fortranの整数型変数を宣言する為の規則が I で始まる識別子であることから来ています。Fortranが最もさかんに使われていた時代や環境では、長い識別子をサポートしていなかった為、識別子の長さも識別子のバリエーションを増やす為に利用されていたそうです。なのでとりあえずループカウンタに整数型が欲しいな程度の物に長い意味のある識別子を使うのはご法度だったので、ループカウンタには I を使うという慣習が出来たようです。
 ちなみにこの逸話はエキスパートCプログラミングにも載っています。このトピック以外の話題も為になる本なので、興味のある方はご一読してみては如何でしょうか。

GoF本第四章その5: Decorator

Filed in C/C++, prog, , 読書感想文

 仕事中に右手人差し指の先を切り、さらに右手中指の爪が割れて先の方が五分の一ほど剥がれかけな長月です。皆様はご健勝でしょうか? 長月は本人も仮想世界への代理人も割と不健康な感じです。皆様はご自愛ください。
 さて、キーボードが少し打ちづらいながらも基本的に左利き寄りの両利きの為割と生活には支障ないのでいつも通りエントリは追加される訳です。今日はもうそろそろ見てる方々も飽きてきたであろう GoF本 第4章から Decorator パターンです。
 Decorator パターンはオブジェクトに動的に責任を追加するパターンです。ロジックとしては前回取り上げた Composite パターンと似ています。Composite パターンは、コンテナとプリミティブなクラスを同じクラス階層に置く事でツリー状にお互いを包含する構造を作り出し、部分と全体に差を無くすパターンでした。Decorator パターンの場合も、Composite パターンでも行われた様に、全体を俯瞰する為のルートクラスを用意し、Decorator に当たるサブクラスではルートクラスのオブジェクトへの参照を持つ事で連鎖します。Composite パターンとの違いはルートクラスのインターフェイスが最大化しない事ですかね。
 Decorator パターンは、個々のオブジェクトに責任を追加し、且つ他のオブジェクトへの影響を最小化すべき時。責任の追加に加えて、責任の削除が出来るべき時。サブクラス化による責任追加が現実的ではない時。等に利用されます。
 Decorator パターンは継承を用いた拡張よりも柔軟です。また、クラス階層の上位のクラスが、所謂「スーパーマンクラス」になる事を防ぎます。
 しかし、ある Decorator クラスが装飾しているクラスはその Decorator クラスと同一ではないので、同一性に期待したコーディングが出来ない。非常に似通った小さなクラスが氾濫する。と言う欠点も持ちます。
 前述の通り Decorator パターンは Composite パターンと似通っています。構造を良く見てみれば内部に持つオブジェクトが一つに制限された Composite パターンに見えます。しかし Decorator パターンはオブジェクトの集約を目的としている訳ではありません。Decorator パターンはオブジェクトに責任を追加します。
 長月は Decorator パターンを余り使った事がないんですよね。もしかしたらやってるかもしれませんが、意識して使った事って少ないです。なんと言うか、動的に責任を追加する場面が余りないというか。そんなトリックが必要になるほど複雑な物を作ってないというか。そもそも殆どプログラム書いてな……げふっ(吐血
 まあそんな訳で今回はここまで、次回はおそらく長月の理解度が本書中一番低い Facade パターンをお送りします。

GoF本第四章その4: Composite

Filed in C/C++, prog, , 読書感想文

 今日は構造に関するパターンの三つ目、Composite パターンをお送りします。
 Composite パターンは複数のオブジェクトを合成します。また、合成されたまとめオブジェクトを一様に扱えるのが特徴です。
 プリミティブなオブジェクトを組み合わせる事で複雑なオブジェクトを構成する事はままあると思います。しかし、その時にそれらのオブジェクトを一様に扱う事に困難を覚えた事はありませんか? 例えば、プリミティブなオブジェクトをまとめて扱う方法としてコンテナへの格納は一手でしょう。しかし、プリミティブなオブジェクトとプリミティブなオブジェクトを集めたコンテナは別物です。いくつかのオブジェクトをまとめた物と、単一のオブジェクトを区別なく扱う。それが Composite パターンの提供する合成です。
 Composite パターンでは、プリミティブなクラスとコンテナクラスを同じクラス階層に置きます。詰まり一つの抽象クラスがコンテナでも、プリミティブなクラスでもあるのです。
 例として GUI コンポーネントを考えてみましょう。GUI コンポーネントには、Button や Label、Inputbox の様なプリミティブなコンポーネントや、Window や Panel 等の、他のコンポーネントを内包するコンポーネントが考えられます。Window クラスや Panel クラスは他のコンポーネントオブジェクトを内包するコンポーネントなので ContainerComponent から派生します。Button クラスや Label クラスはプリミティブなコンポーネントなので PrimitiveComponent から派生します。さて、これらを統一的に扱うにはどうしますか? ContainerComponent と PrimitiveComponent に共通の親クラス Component があれば良いですよね。これで Composite パターンの言う形になりました。これは ContainerComponent をノード、PrimitiveComponent をリーフとしたツリー構造と言えます。Composite パターンは、再帰的に複合オブジェクトを構成していくパターンなのです。
 Composite パターンでは、その構成要素であるノードに当たるクラスも、リーフに当たるクラスも区別しません。その特徴によってクライアント側のコードはノードであるかリーフであるかを意識せずにコーディング出来るようになります。また、部分と全体に区別の無い構造なので、柔軟な構成の変更が出来ます。
 しかし、設計を過度に一般化するというデメリットも持ちます。
 実装の面で言えば、Composite パターンは、その構造上ツリー構造の持つメリットデメリットを同じように持つようです。また、ルートに当たるクラスは自らの子孫であるクラスのインターフェイスをほぼ全て持つことになります。これはインターフェイスの最大化と呼ばれる好ましくない設計の一つです。
 Composite パターンは Decorator パターンと共に良く使用されます。この場合、Decorator パターンは Composite パターン側のインターフェイスに合わせる必要があり、若干割を食うようです。
 Composite パターンを用いた構造では、内部の操作に Iterator パターンが良く用いられます。
 Composite パターンは割と良く使われているはずです。なんと言うか、オブジェクト指向の本を読むと必ずこういった感じの設計について書かれてますし。文中で挙げたコンポーネントクラスの様に、素直に考えれば Composite パターンになる場合も多いからです。
 しかしそれだけに、経験だけで書いている方も多いのではないでしょうか? Composite パターンが持つメリットデメリットを再確認する為にも一度勉強しなおしてみるのも一手ですよ。
 では今回はここまで、次回は Decorator パターンをお送りします。

GoF本第四章その3: Bridge

Filed in C/C++, prog, , 読書感想文

 構造に関するパターンの二つ目は、前回も書いた通り Bridge パターンです。
 Bridge パターンは Handle/Body とも呼ばれ、割と良く使われているパターンだと思います。Bridge パターンはパブリックなクラスの定義と実装を分離し、それらを独立に変更できるようにしたパターンです。
 実装の分離と言うと pimpl イディオムを思い出しますね。あれも Bridge パターンの一形態だと思います。しかし Bridge パターンでは、実装の分離に関する思惑が pimpl イディオムとは違います。Bridge パターンは、実装上の汎化関係にあるクラスの関係を意味上の汎化関係を分離します。一般的に汎化関係は抽象クラスと継承を用いて表現されますが、クラス階層の中に実装上の汎化関係と意味上の汎化関係が混在すると、それぞれを独立に変更する事が困難になります。
 そんな場合、Bridge パターンを用いて実装と意味の階層を分離します。クライアントが参照する物は意味の階層、意味の階層の中で実装上必要とする物は実装の階層で定義する事で、クラス階層単位でのインターフェイスと実装の分離を実現します。
 Bridge パターンは抽出されたクラスとその実装を分離し、実装を動的に選択したり交換したりしなければならない場合、抽出されたクラスとその実装を両方ともサブクラス化によって拡張可能にする場合、抽出されたクラスの実装が変更によってクライアントに影響を与えるべきではない時、C++のような言語で実装を隠蔽したい時、複数のオブジェクト間でクライアントから隠蔽した状態で実装を共有したい場合等に使用されます。
 C++のような言語で実装を隠蔽するというのはまさに pimpl イディオムですね。一番良く使われる Bridge パターンではないでしょうか。
 Bridge パターンと Adapter パターンはクラス同士を繋ぐという関係では同じです。しかし Adapter パターンは既にあるクラス等、設計後に適用される事が多いのに対し、Bridge パターンは抽出されたクラスと実装を分離する為に、言い換えれば外部に向けた設計と実装を分離する為に、設計の早期に適用されます。
 長月は割と最近まで Bridge パターンを軽視していました。Bridge パターンというより pimpl イディオムですね。Exceptional C++ を読んでからは考えを改めたのですが、実装の隠蔽以外の意味で使用する Bridge パターンも馬鹿に出来ませんね。解っているつもりでやっぱり「ああなるほど」と思う所もいくつかありました。いや、本は読むものです。
 では今回はここまで、次回は Composite パターンをお送りします。

GoF本第四章その2: Adapter

Filed in C/C++, prog, , 読書感想文

 今回から数回は構造に関するパターンのカタログです。今回は Adapter パターンを取り上げます。
 Adapter はあるクラスのインターフェイスを別のインターフェイスに変換します。変換と言うとなんだか齟齬があるように感じますね。なんと言うか、所謂ラッパクラスです。
 あるコードの中でクラス Hoge のオブジェクトが使われていた時。何らかの理由で関連性の無い Piyo を同じコードで使いたくなる事があったとします。その時、Hoge と Piyo のインターフェイスがたまたま一致していればコードの修正量は少なくて済みますが、そう言う事は稀で、どうしても Piyo のインターフェイスに合わせて修正する必要が出てきます。Adapter は、Piyo をラッピングしてインターフェイスを合わせる事で、そのジレンマを解消します。長月が実際に遭遇した例で言えば長月の書いた画像クラス AILImage を、とあるライブラリの DIBBitmap 操作関数に渡す為に AILImg2DIBWrapper クラスでラップして渡した事があります。その時は Adapter パターンとか意識してなかったんですが今考えると Adapter パターンですね。これはオブジェクトに対する Adapter パターンと呼ばれます。
 また、上記の例では AILImg2DIBWrappter の中に AILImage のインスタンスを持ち、転送関数で処理を委譲していましたが、向こうのライブラリで用意されている DIBBitmap クラスのインターフェイスと、AILImage の実装を多重継承した AILImg2DIBAdapter も考えられます。DIBBitmap クラスからの継承が必要な場面ではこちらを選ぶべきでしょう。こちらはクラスに対する Adapter パターンと呼ばれます。
 Adapter は再利用したいクラスが望んだインターフェイスを持たない場合や、既存の複数のサブクラスを利用したいが、さらにサブクラス化してインターフェイスを合わせる事が現実的ではない場合、等に活躍します。
 クラスに対する Adapter では、Adapter クラスが再利用されるクラスのサブクラスになる為、メンバ関数をオーバーライド出来ます。その代わり、クラス階層を見たとき、Adapter クラスが再利用されるクラスの下に来るので、再利用されるクラスとそのサブクラス全てを適合させたい場合にはクラスに対する Adapter では上手く行かないという事になります。
 オブジェクトに対する Adapter では、クラスに対する Adapter でのジレンマである、複数のサブクラスを賄う Adapter の構築が可能です。しかし、クラスに対する Adapter と違い、再利用されるクラスのメンバ関数をオーバーライドする事は出来ません。これを実現するには、再利用されるクラスのサブクラスを定義し、そのサブクラスで任意のオーバーライドを行い、サブクラスに対する Adapter を定義する事で実現できますが、余計な間接性を持たせる事にもなります。
 オブジェクトに対する Adapter パターンは Bridge パターンと良く似た構造を持ちます。しかし、Adapter が外部表現 (インターフェイス) に重点を置くのに対して、Bridge は内部表現 (実装) に重点を置きます。また、何らかのオブジェクトをラップする事に関して Adapter パターンは Decorator パターンと似ています。しかし Adapter がインターフェイスを変更するのに対して、Decorator ではインターフェイスを変更せずに機能を追加します。その結果、Decorator の方が透過性が高く、再帰的なオブジェクト構造の構築を可能としています。そして Proxy パターンも再利用されるクラスを自らの背後に隠す点では同じですが、Proxy はインターフェイスを変更しません。
 長月的に Adapter はとても便利です。特にジェネリックスプログラミングで威力を発揮すると思います。ジェネリックスプログラミングでは、ジェネリック関数の内部で特定のインターフェイスを必要とする事が多く、ジェネリック関数に放り込みたいクラスが必要なインターフェイスを持っていない事があります。そう言った時 Adapter はとても重宝します。
 個人的に便利な物が多い構造に関するパターン、次回取り上げるのは Bridge パターンです。所謂ハンドル-ボディイディオムって奴ですね。pimpl イディオムも Bridge パターンと言えますね。C++に於ける pimpl にはソースファイルの依存性軽減とか Bridge パターン本来の目的とは違う物も含まれるので Bridge パターンそのものとは言えないかも知れませんけどね。
 では、今回はここまで。(=゚ω゚)ノシ

GoF本第四章その1: 概要

Filed in C/C++, prog, , 読書感想文

 GoF本も割と久方ぶりに読んでる訳ですが、今読むと前よりちょっと理解できる感じです。一応腕上がってるんですかね?
 今回からは第4章に入ります。第4章は構造に関するパターンが詳解されています。構造に関するパターンの要点は二つ。オブジェクトやクラスを合成する事、まとめられたクラスやオブジェクト群がむやみに強く結合しない事です。「分割し、統治せよ」をオブジェクト指向の世界で如何に実現するか、その妙技を集めた章と言えます。
 いくつかのオブジェクトやクラスを合成したいと言う要求は良く発生します。また、それを前提として書かれるクラスやオブジェクトも多いでしょう。しかし、オブジェクトを合成するだけでは不満なのです。複数のオブジェクトやクラスを持ちつつも、それぞれの依存度を最小化したいのです。影響を局所化出来てこそ大きな構造には価値があります。
 本章では上記の様な要求に対する解が七つ詳解されています。その七つのパターンを列挙しておきます。

 構造に関するパターンはそれぞれいくらかの関連を持ちます。設計の軸になる部分で良く使用されたりするので、これらのパターンの複合的な物になる事が多いようです。それらの関連については本章の最後で語られます。本blogでも、最後に取り上げる予定の Proxy パターンのエントリかまとめのエントリで書く予定です。
 個人的に本章は割と好きです。いろいろなロジックに触れるのが楽しいのです。その意味で第5章の振る舞いに関するパターンも面白いトリックが満載で好きです。本章のパターンは割とどっしりとした印象で、第5章のパターンは派手な印象ですね。ぱっと見て効果が実感しやすい第5章のパターンも良いですが、最終的な開発コスト等、地味ながらも重要な部分で威力を発揮する本章のパターンも長月の脳の肉欲を大きく満足させます。
 ただ、これらのパターンは選択が重要になりますので、本章は特に精読して各パターンをしっかり把握しておきましょう。

GoF本第三章その6: Singleton

Filed in C/C++, prog, , 読書感想文

 さて、今回は第3章最後のパターン、Singleton です。なんと言うかみんな知ってそうですが……
 Singleton はアプリケーション中にあるクラスのインスタンスが一つしか存在しない事と容易なアクセスを保証するパターンです。複数の選択肢はあれど、同時に一つしか存在してはいけない場合に威力を発揮します。グローバル変数のアクセシビリティにインスタンス数の制限を加えた物と言えます。
 Singleton はその簡単な構造とは裏腹に、インスタンスへのアクセスを制限したりコントロールしやすい、制限を掛ける数が任意に調整でき、状態を持て、C++等の静的メンバ関数の仮想化を許さない言語でも仮想関数を扱える等から、クラスメソッドだけのクラスを使うより柔軟性がある。と言うメリットがあります。
 今までに挙げてきた複合オブジェクトの生成に関わるパターン、Abstract Factory や Builder、Prototype 等はアプリケーション内で複数必要となる事が少なく、高いアクセシビリティを必要とするので、Singleton を用いて実装される事が多いでしょう。それで無くとも Singleton は割と便利なので使用する機会は多いと思います。しかし、Singleton は拡張されたグローバル変数なので、グローバル変数が持つ欠点は多くの場合 Singleton にも当てはまります。
 さて、今回まで何度かに渡って生成に関するパターンを扱いましたが、これらはシステムの構成に柔軟性を与える為の物です。Factory Method に代表されるサブクラス化や、Abstract Factory や Builder、Prototype が威力を発揮するオブジェクトコンポジション、これらは柔軟性を高める為の方法論です。それらを上手く使いこなしたアプリケーションに現れるオブジェクト生成の為の設計パターン、それが第3章で詳解されているデザインパターンなのです。
 デザインパターンは若干の複雑度と引き換えに柔軟性をもたらします。パターンの選択肢が増えれば増えるほど設計は洗練されるでしょう。この機にデザインパターンを勉強してみるのは如何でしょうか?


Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Oenology Post Formats
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Posts Calendar
Click to view/hide
2017年9月
« 12月    
 12
3456789
10111213141516
17181920212223
24252627282930

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
アーカイブ
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
最近の投稿
Click to view/hide