C++ データ構造

C++ は、配列、構造体、クラスなどの基本的なものから、高度な STL コンテナまで、さまざまなデータ構造を提供しています。例えば、vector、mapとunordered_mapなど。

以下では、C++ でよく使われるデータ構造と、その特徴と使い方について詳しく説明します。

1. 配列（Array）

配列は最も基本的なデータ構造であり、同じ型のデータの集まりを格納するために使用されます。

特徴：

  • サイズは固定で、一度宣言するとサイズを変更できません。
  • 要素に直接アクセスでき、時間計算量は O(1) です。
  • サイズが既知で、要素の型が同じ集合を扱うのに適しています。

サンプル

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // 最初の要素を出力

長所と短所：

  • 長所：アクセス速度が速く、メモリがコンパクトです。
  • 短所：サイズが固定で動的に拡張できず、サイズが不明なデータセットには適しません。

2. 構造体（Struct）

構造体は、異なる型のデータを組み合わせて、独自のデータ型を形成することを可能にします。

特徴：

  • 異なる型のメンバ変数を含めることができます。
  • データの基本的なカプセル化を提供しますが、機能は限られています。

例：

サンプル

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Alice を出力

3. クラス（Class）

クラスは、C++ でオブジェクト指向プログラミングに使用される中核的な構造であり、メンバ変数とメンバ関数を定義できます。構造体とstruct類似していますが、より強力で、継承、カプセル化、ポリモーフィズムなどの特性をサポートします。

特徴：

  • メンバ変数、メンバ関数、コンストラクタ、デストラクタを含むことができます。
  • カプセル化、継承、ポリモーフィズムなどのオブジェクト指向の特性をサポートします。

サンプル

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // 出力: Name: Bob, Age: 30

4. 連結リスト（Linked List）

連結リストは動的なデータ構造で、一連のノードで構成され、各ノードはデータと次のノードを指すポインタを含みます。

特徴：

  • サイズを動的に調整でき、あらかじめ容量を定義する必要はありません。
  • 挿入と削除の操作効率が高く、時間計算量は O(1)（リストの先頭または末尾での操作）です。
  • 線形探索で、時間計算量は O(n) です。

サンプル（単方向リスト）

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // 新しいノードを挿入

長所と短所：

  • 長所：サイズが動的で、頻繁な挿入や削除の場面に適しています。
  • 短所：ランダムアクセスの効率が低く、配列のように直接アクセスするほど速くありません。

5. スタック（Stack）

スタックは後入れ先出し（LIFO, Last In First Out）のデータ構造で、再帰や深さ優先探索などの場面でよく使われます。

特徴：

  • 挿入と削除はスタックの先頭（トップ）でのみ行えます。
  • 時間計算量は O(1) です。

サンプル

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // 2 を出力
s.pop();

長所と短所：

  • 長所：操作が簡単で効率が高い。
  • 短所：スタックの先頭でしか操作できず、他の要素にアクセスするには先頭の要素をポップする必要があります。

6. キュー（Queue）

キューは先入れ先出し（FIFO, First In First Out）のデータ構造で、幅優先探索やタスクスケジューリングなどの場面でよく使われます。

特徴：

  • 挿入操作はキューの末尾で行われ、削除操作は先頭で行われます。
  • 時間計算量は O(1) です。

サンプル

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // 1 を出力
q.pop();

長所と短所：

  • 長所：タスクスケジューリングなど、データを順番に処理する場面に適しています。
  • 短所：要素にランダムアクセスできません。

7. 両端キュー（Deque）

両端キューは、両端で挿入と削除を行うことができ、スタックとキューの組み合わせです。

特徴：

  • 両端で挿入と削除が可能です。
  • 時間計算量は O(1) です。

サンプル

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // 2 を出力
dq.pop_front();

長所と短所：

  • 長所：柔軟な双方向操作が可能。
  • 短所：メモリ使用量が大きめで、両端での頻繁な操作が必要な場面に適しています。

8. ハッシュテーブル（Hash Table）

ハッシュテーブルは、キーと値のペアでデータを格納するデータ構造で、高速な検索、挿入、削除操作をサポートします。C++ では、unordered_mapがハッシュテーブルの実装です。

特徴：

  • ハッシュ関数を使用して要素を高速に特定し、時間計算量は O(1) です。
  • 要素の順序は保証されません。

サンプル

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // 10 を出力

長所と短所：

  • 長所：検索、挿入、削除操作の効率が高い。
  • 短所：要素の順序が保証されず、ハッシュ衝突が発生すると性能が低下します。

9. マップ（Map）

mapは順序付きのキーと値のペアのコンテナで、内部実装は赤黒木です。とunordered_mapは異なり、キーの順序を保証し、検索、挿入、削除の時間計算量は O(log n) です。

特徴：

  • 要素がキーの順序で並ぶことを保証します。
  • 二分探索木を使用して実装されます。

サンプル

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // 10 を出力

長所と短所：

  • 長所：要素が順序付けられており、データを順番に処理する必要がある場面に適しています。
  • 短所：操作効率はunordered_mapよりわずかに低いです。

10. 集合（Set）

setは、一意の要素を格納するための順序付き集合で、内部実装は同じく赤黒木です。要素が重複せず、順序付けられていることを保証します。

特徴：

  • 要素の一意性を保証します。
  • 要素は自動的に昇順で並びます。
  • 時間計算量は O(log n) です。

サンプル

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // 1 を出力

長所と短所：

  • 長所：自動ソートと一意性の保証。
  • 短所：挿入と削除の効率は順序なし集合には及びません。

11. 動的配列（Vector）

vectorは、C++ 標準ライブラリが提供する動的配列の実装で、容量を動的に拡張でき、ランダムアクセスをサポートします。

特徴：

  • サイズを動的に調整します。
  • ランダムアクセスをサポートし、時間計算量は O(1) です。
  • 容量が不足すると動的に拡張され、時間計算量は償却 O(1) です。

サンプル

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // 1 を出力

長所と短所：

  • 長所：ランダムアクセスと動的拡張をサポート。
  • 短所：中間の要素の挿入と削除の効率が低い。
その他の拡張