C++

はじめにC++には、int、char、doubleなど、さまざまなデータ型が用意されています。本記事では、これらのデータ型のサイズと、表現できる値の範囲をプログラムで求める方法を解説します。データ型の範囲を求める仕組みデータ型のサイズはバイト単位で取得できるため、8を掛ければビット数に変換できます。ビット数をnとすると、符号付き整数の場合、最小値は「-2^(n-1)」、最大値は「2^(n-1) - 1」となります。一方、符号なし整数には負の数が存在しないため、範囲は「0」から「2^n - 1」までです。サンプルコード#include <iostream> #include <

はじめに C++でコンソールやファイルに出力を行う際、多くの開発者が無意識にstd::endlを使用しています。しかし、実はこの習慣がパフォーマンスの大きなボトルネックになることがあります。本記事では、std::endlを避けるべき理由と、その代替手段について詳しく解説します。 std::endlが実際に行っていること 多くの人はstd::endlを単なる改行文字だと思っていますが、実際には2つの処理を実行しています。 カーソルを次の行へ移動させる(改行) 出力バッファを強制的にフラッシュする つまり、std::endlは改行するたびにバッファのフラッシュ(強制書き出し)も同時に行ってい

fork()システムコールは、1つのプロセスを2つのプロセスに分割するために使用されます。fork()関数が0を返した場合はそのプロセスが子プロセスであり、0以外を返した場合は親プロセスであると判断できます。この記事では、プロセスを4つに分割し、それらをボトムアップ（下から上）の順序で実行する方法を解説します。まず、fork()関数を2回連続で呼び出します。最初のfork()で子プロセスが生成され、次のfork()でもう1つの子プロセスが生成され、さらに内側のfork()からは自動的に孫プロセスが作られます。結果として、親プロセス1つ、子プロセス2つ、孫プロセス1つの計4つのプロセスが存在する

reference_wrapperとはC++のstd::reference_wrapperは、参照（T&）をコピー構築可能かつコピー代入可能なオブジェクトでラップするクラステンプレートです。<functional>ヘッダーで定義されており、名前空間std内で提供されます。std::reference_wrapperのインスタンスは本質的にはオブジェクトですが、暗黙的にT&へ変換することが可能です。そのため、基となる型を参照引数として受け取る関数に対して、通常のオブジェクトと同じように渡すことができます。主な特徴コピー構築・コピー代入が可能な「参照のような」振る舞いを

この記事では、C++を使って中空（ホロー）のピラミッドとダイヤモンドのパターンを生成する方法を解説します。塗りつぶし（ソリッド）のピラミッドパターンは比較的簡単に作成できますが、中空にするにはいくつかの工夫が必要です。ポイントは、ループと条件分岐を組み合わせて「星を出す位置」と「空白を入れる位置」を制御することです。 中空ピラミッドの出力 ピラミッドでは、1行目に星（*）を1つだけ出力し、最終行にはn個の星を連続して出力します。それ以外の行では、行頭と行末にちょうど2つの星を出力し、その間は空白で埋めます。これにより、輪郭だけの中空ピラミッドが完成します。 サンプルコード #include &

この記事では、C++でfork()システムコールを使って子プロセスを生成する方法を解説します。さらに、親プロセスと子プロセスそれぞれで異なる計算を実行してみます。具体的には、親プロセスでは配列内の偶数の合計値を求め、子プロセスでは奇数の合計値を求めます。fork()の仕組みfork()が呼び出されると、戻り値として整数が返されます。この戻り値が0より大きい場合、現在実行中のコードは親プロセス側にあります。一方、戻り値が0の場合は子プロセス側です。また、プロセスの生成に失敗した場合は-1が返されます。この戻り値を判定に使うことで、親プロセスと子プロセスの処理を簡単に切り分けることができます。なお

RTTI（実行時型情報）とはこの記事では、C++におけるRTTI（Runtime Type Information：実行時型情報）について詳しく解説します。RTTIとは、プログラムの実行時にオブジェクトのデータ型に関する情報を取得・判定できる仕組みのことです。これにより、実行中のプログラム内でオブジェクトの実際の型を動的に判別することが可能になります。ただし、この機能が有効になるのは、クラスに少なくとも1つの仮想関数（virtual関数）が定義されている場合のみです。つまり、RTTIは多態性（ポリモーフィズム）を持つクラスに対してのみ利用できます。仮想関数がない場合の例次のサンプルコードは、仮

C++のChronoライブラリとはこの記事では、C++標準ライブラリの一つであるChronoライブラリについて解説します。Chronoライブラリは、日付や時刻を扱うために用意されたライブラリです。タイマーやクロック（時計）の実装は、システムごとに異なる仕様となっています。そのため、時間をより高い精度で扱いたい場合には、このChronoライブラリを利用するのが有効です。Chronoライブラリの大きな特徴は、時間間隔（duration）と時点（time point）という概念を分離することで、特定の精度に依存しない柔軟な設計が可能になっている点にあります。durationオブジェクトによる時間の表

C++における例外処理（Exception Handling）とは、プログラムの実行中に発生するエラー（ランタイムエラー）を適切に処理するための仕組みです。例外とは、実行時に送出されるイベントのことを指し、C++ではすべての標準例外が std::exception クラスを基底クラスとして定義されています。 もし例外を捕捉しなければ、プログラムは例外メッセージを出力した後に異常終了してしまいます。例外はハンドリング可能なランタイムエラーであり、適切に処理することでプログラムの堅牢性を大きく向上させることができます。 標準例外クラスの階層構造 C++標準では、例外は <exception&

「反転数（Inversion Count）」とは、配列を昇順にソートされた状態にするために必要な要素の入れ替え回数を表す指標です。配列がすでにソートされている場合、反転数は 0 となり、逆に配列が完全に逆順に並んでいる場合、反転数は最大値になります。この記事では、配列内の反転数を数えるC++プログラムを実際に作成しながら、その考え方と実装方法をわかりやすく解説します。反転数とは配列内の2つの要素 a[i] と a[j] について、i < j かつ a[i] > a[j] が成り立つとき、このペアを「反転（inversion）」と呼びます。配列全体に存在する反転ペアの総数が反転数です

本記事では、連結リスト（リンクリスト）を使用して二分探索木（Binary Search Tree: BST）を実装するC++プログラムを紹介します。二分探索木は、各ノードが最大2つの子を持つ木構造データであり、「左の子には親より小さい値、右の子には親より大きい値」を配置する規則に従うことで、高速なデータの挿入・検索を実現できるデータ構造です。アルゴリズムプログラム全体の流れは、以下の疑似コードのとおりです。開始 ツリーのノードを入力として受け取る。 データ d、左ポインタ l、右ポインタ r を持つ構造体 nod を定義する。 ノードをツリーに挿入する関数 create

Bツリー（B木）は、1つのノードが2つ以上の子ノードを持つことができる、二分探索木を一般化した木構造です。自己平衡型のデータ構造の一種であり、データを常にソート済みの状態で保持しながら、対数時間 O(log n) での順次アクセス・検索・挿入・削除を実現します。この特性から、データベースやファイルシステムなど、大量のデータを効率的に扱う必要がある分野で広く採用されています。本記事では、次数6のBツリーをC++で実装するプログラムを、アルゴリズムの流れとともに解説します。アルゴリズムノードを木に挿入する関数 insert() の処理の流れは以下の通りです。開始 ノードを木に挿入するための

本記事では、2つの異なる配列に格納された要素の中央値（メジアン）を求めるC++プログラムについて解説します。両方の配列が同じ要素数 n を持つ場合、マージ処理を行わずに中央位置の2つの値だけを追跡することで、効率よく中央値を計算できます。アルゴリズム基本的な考え方は次のとおりです。両配列の先頭から順に小さい方の要素を比較しながら読み進め、全体で中央にあたる2つの値（n1 と n2）を記録していきます。最後にその平均を返すことで中央値が得られます。Begin 関数 Median() は、配列 a1[]、a2[] および要素数 n を引数として受け取る: i と j を 0 で、n

B+ツリーは、1つのノードが2つ以上の子を持つことができる点で、二分探索木を一般化したデータ構造です。自己平衡化を行う木構造の一種であり、ソート済みのデータを保持しながら、対数時間（O(log n)）での逐次アクセス、検索、挿入、削除を可能にします。B+ツリーは、各ノードがキーのみを保持するB木と捉えることもできます。さらに、最下層にリンクされた葉ノードからなるレベルを追加した構造になっています。この特徴により、範囲検索や順次アクセスが効率的に行えるため、データベースやファイルシステムで広く採用されています。アルゴリズム以下は、B+ツリーにノードを挿入する際の基本的な流れです。Begin

デカルトツリー（Cartesian Tree）は、数列から構築できる二分木の一種です。木を中順走査（inorder traversal）すると元の数列がそのまま復元でき、さらに各ノードの値が子ノードの値以下になるというヒープ性質を満たします。本記事では、C++を使ってデカルトツリーを実装する方法を、アルゴリズムの解説からサンプルコード、実行結果まで詳しく紹介します。 デカルトツリーとは デカルトツリーは、次の2つの性質を持つ二分木です。 中順走査すると、元の入力数列と同じ順序で要素が得られる 親ノードの値は、常に子ノードの値以下である（最小ヒープ性質） この性質により、デカルトツリーは「T

本記事では、二分探索木（BST）における二重順走査（Double Order Traversal）を実装するC++プログラムを紹介します。二重順走査とは、各部分木の根ノードを2回訪問する走査手法です。通常の行きがけ順・通りがけ順・帰りがけ順とは異なり、左部分木を辿る前後で根を再度出力する点が特徴です。アルゴリズムプログラムは以下の手順で動作します。Begin クラス BST は以下の関数を持つ: insert() = 木に要素を挿入する: 根ノードを設定する。 ノードの値が根より大きければ右の子として、 そうでなければ左の子と

本記事では、配列を分割（パーティション）する手法を用いて、配列内のk番目に小さい要素を求めるC++プログラムを解説します。この手法はクイックソートの考え方を応用したもので、配列全体をソートすることなく、目的の要素だけを効率的に特定できる点が特徴です。 アルゴリズム まず、ピボットを基準に配列を分割する CreatePartition() 関数と、その結果をもとにk番目に小さい要素が存在する範囲を再帰的に絞り込む Partition() 関数を使用します。 Begin 関数 CreatePartition() は 配列 a、下限 l、上限 h を引数にとる in := l、pi

2つのソート済み配列をマージせずに中央値を求めるには、二分探索を応用した分割統治法が効率的です。時間計算量は O(log(min(m,n))) で実現できます。ここでは、同じサイズの2つの配列に対する基本的なアプローチを C++ で実装し、アルゴリズムの流れとコード例を解説します。 アルゴリズムの概要 各部分配列の開始インデックスと終了インデックスを引数に median() 関数を呼び出す。 部分配列の長さを e1 - s1 + 1 で計算する。 長さが 1 または 2 の場合（基本ケース）、直接中央値を計算して返す。 両配列の中央値 m1, m2 を比較する。

本記事では、O(n²)の計算量で配列内の最大部分配列の和を求めるC++プログラムを紹介します。この手法は「素朴な手法（ナイーブ法）」と呼ばれ、あらゆる長さの部分配列を効率よく走査することで最大値を導き出します。 アルゴリズム 開始 配列の要素を入力として受け取る。 部分配列の長さを 1 から n まで変化させるループを作成する。 そのループの中に、さらにネストした別のループを作り、 その長さにおける最初の部分配列の和を計算する。 残りの部分配列の和については、直前の和に次の要素を加え、 ウィンドウから外れる先頭の要素を引くことで効率的に求める。

データ構造におけるリンクリスト（連結リスト）とは、データ要素を線形に格納するコレクションです。リストの各要素（ノード）は「データ本体」と「次のノードへの参照（ポインタ）」という2つの項目で構成され、最後のノードは null への参照を持ちます。また、リンクリストの入口となるノードは「ヘッド（head）」と呼ばれます。循環双方向リンクリスト（Circular Doubly Linked List）では、隣り合う2つの要素が previous（前）ポインタと next（次）ポインタによって相互に接続されています。さらに特徴的なのは、末尾のノードが next ポインタで先頭ノードを指し、先頭のノード