データ構造

SplDoublyLinkedList — SplDoublyLinkedList クラス
- SplDoublyLinkedList::add — 特定のインデックスに新しい値を追加/挿入する
- SplDoublyLinkedList::bottom — 双方向リンクリストの最初のノードを取得する
- SplDoublyLinkedList::count — 双方向リンクリストの要素数を数える
- SplDoublyLinkedList::current — 現在の配列の要素を返す
- SplDoublyLinkedList::getIteratorMode — 反復処理のモードを返す
- SplDoublyLinkedList::isEmpty — 双方向リンクリストが空かどうかを調べる
- SplDoublyLinkedList::key — 現在のノードのインデックスを返す
- SplDoublyLinkedList::next — 次のエントリに移動する
- SplDoublyLinkedList::offsetExists — 指定した $index が存在するかどうかを返す
- SplDoublyLinkedList::offsetGet — 指定した $index の値を返す
- SplDoublyLinkedList::offsetSet — 指定した $index の値を $value に設定する
- SplDoublyLinkedList::offsetUnset — 指定した $index の値を削除する
- SplDoublyLinkedList::pop — 双方向リンクリストの末尾からノードを取り出す
- SplDoublyLinkedList::prev — 前のエントリに移動する
- SplDoublyLinkedList::push — 双方向リンクリストの末尾に要素を追加する
- SplDoublyLinkedList::rewind — イテレータを先頭に巻き戻す
- SplDoublyLinkedList::serialize — ストレージをシリアライズする
- SplDoublyLinkedList::setIteratorMode — 反復処理のモードを設定する
- SplDoublyLinkedList::shift — 双方向リンクリストの先頭からノードを取り出す
- SplDoublyLinkedList::top — 双方向リンクリストの最後のノードを取得する
- SplDoublyLinkedList::unserialize — ストレージをアンシリアライズする
- SplDoublyLinkedList::unshift — 双方向リンクリストの先頭に要素を追加する
- SplDoublyLinkedList::valid — 双方向リンクリストにまだノードがあるかどうかを調べる
SplStack — SplStack クラス
SplQueue — SplQueue クラス
- SplQueue::dequeue — キューからノードを取り出す
- SplQueue::enqueue — 要素をキューに追加する
SplHeap — SplHeap クラス
- SplHeap::compare — 要素を比較し、ヒープ内の適切な位置に置く
- SplHeap::count — ヒープ内の要素数を数える
- SplHeap::current — イテレータが指す現在のノードを返す
- SplHeap::extract — ヒープの先頭からノードを取り出す
- SplHeap::insert — ヒープに要素を挿入する
- SplHeap::isCorrupted — ヒープが壊れているかを調べる
- SplHeap::isEmpty — ヒープが空かどうかを調べる
- SplHeap::key — 現在のノードのインデックスを返す
- SplHeap::next — 次のノードに移動する
- SplHeap::recoverFromCorruption — 破壊されたヒープを復旧し、それ以降の操作をできるようにする
- SplHeap::rewind — イテレータを先頭に巻き戻す (何もしない)
- SplHeap::top — ヒープの先頭のノードを取り出す
- SplHeap::valid — ヒープにまだノードがあるかどうかを調べる
SplMaxHeap — SplMaxHeap クラス
- SplMaxHeap::compare — 要素を比較し、ヒープ内の適切な位置に置く
SplMinHeap — SplMinHeap クラス
- SplMinHeap::compare — 要素を比較し、ヒープ内の適切な位置に置く
SplPriorityQueue — SplPriorityQueue クラス
- SplPriorityQueue::compare — 要素の優先順位を比較し、ヒープ内の適切な位置に置く
- SplPriorityQueue::count — キュー内の要素数を数える
- SplPriorityQueue::current — イテレータが指す現在のノードを返す
- SplPriorityQueue::extract — ヒープの先頭からノードを取り出す
- SplPriorityQueue::getExtractFlags — 展開する時のフラグを取得する
- SplPriorityQueue::insert — キューに要素を挿入する
- SplPriorityQueue::isCorrupted — 優先度付きキューが壊れているかを調べる
- SplPriorityQueue::isEmpty — キューが空かどうかを調べる
- SplPriorityQueue::key — 現在のノードのインデックスを返す
- SplPriorityQueue::next — 次のノードに移動する
- SplPriorityQueue::recoverFromCorruption — 破壊されたキューを復旧し、それ以降の操作をできるようにする
- SplPriorityQueue::rewind — イテレータを先頭に巻き戻す (何もしない)
- SplPriorityQueue::setExtractFlags — 取り出しモードを設定する
- SplPriorityQueue::top — キューの先頭のノードを取り出す
- SplPriorityQueue::valid — キューにまだノードがあるかどうかを調べる
SplFixedArray — SplFixedArray クラス
- SplFixedArray::__construct — 新しい固定長配列を作成する
- SplFixedArray::count — 配列のサイズを返す
- SplFixedArray::current — 現在の配列の要素を返す
- SplFixedArray::fromArray — PHP の配列を SplFixedArray インスタンスにインポートする
- SplFixedArray::getIterator — 配列を走査するためのイテレータを取得する
- SplFixedArray::getSize — 配列のサイズを取得する
- SplFixedArray::jsonSerialize — JSON に変換可能な値の表現を返す
- SplFixedArray::key — 現在の配列の添字を返す
- SplFixedArray::next — 次のエントリに進む
- SplFixedArray::offsetExists — 指定した添字が存在するかどうかを返す
- SplFixedArray::offsetGet — 指定した添字の値を返す
- SplFixedArray::offsetSet — 指定した添字の新しい値を設定する
- SplFixedArray::offsetUnset — 指定した添字の値を消去する
- SplFixedArray::rewind — イテレータを先頭に巻き戻す
- SplFixedArray::__serialize — SplFixedArray オブジェクトをシリアライズする
- SplFixedArray::setSize — 配列のサイズを変更する
- SplFixedArray::toArray — 固定長配列から PHP の配列を返す
- SplFixedArray::__unserialize — data パラメータを SplFixedArray オブジェクトに復元する
- SplFixedArray::valid — 配列にまだ要素があるかどうかを調べる
- SplFixedArray::__wakeup — アンシリアライズ後に配列を再初期化する
SplObjectStorage — SplObjectStorage クラス
- SplObjectStorage::addAll — 別のストレージからすべてのオブジェクトを追加する
- SplObjectStorage::attach — オブジェクトをストレージに追加する
- SplObjectStorage::contains — ストレージに特定のオブジェクトが含まれるかどうかを調べる
- SplObjectStorage::count — ストレージ内のオブジェクトの数を返す
- SplObjectStorage::current — 現在のストレージの要素を返す
- SplObjectStorage::detach — オブジェクトをストレージから取り除く
- SplObjectStorage::getHash — 中に含むオブジェクトの一意な識別子を算出する
- SplObjectStorage::getInfo — イテレータの現在のエントリに関連づけられたデータを返す
- SplObjectStorage::key — イテレータの現在位置を返す
- SplObjectStorage::next — 次のエントリに移動する
- SplObjectStorage::offsetExists — オブジェクトがストレージ内に存在するかどうかを調べる
- SplObjectStorage::offsetGet — オブジェクトに関連づけられたデータを返す
- SplObjectStorage::offsetSet — ストレージ内のオブジェクトにデータを関連づける
- SplObjectStorage::offsetUnset — ストレージからオブジェクトを取り除く
- SplObjectStorage::removeAll — 別のストレージに含まれているオブジェクトを現在のストレージから取り除く
- SplObjectStorage::removeAllExcept — 別のストレージに含まれているもの以外のすべてのオブジェクトを現在のストレージから取り除く
- SplObjectStorage::rewind — イテレータをストレージの最初の要素に巻き戻す
- SplObjectStorage::serialize — ストレージをシリアライズする
- SplObjectStorage::setInfo — イテレータの現在のエントリに関連づけるデータを設定する
- SplObjectStorage::unserialize — ストレージの文字列表現をアンシリアライズする
- SplObjectStorage::valid — イテレータの現在のエントリが有効かどうかを返す

SPL では、標準的なデータ構造を提供しています。ここで、それらを実装ごとに分類してまとめます。

双方向リンクリスト

双方向リンクリスト (Doubly Linked List: DLL) は、双方向のノードへのリンクを持つノードのリストです。イテレータの操作、両隣へのアクセス、ノードの追加や削除のコストは、データ構造が DLL の場合は O(1) となります。これは、スタックやキューを実装するのに適しています。

SplDoublyLinkedList
- SplStack
- SplQueue

ヒープ

ヒープは、ツリー風の構造です。ヒープ特有の性質として、個々のノードはその子ノードと等しいかそれより大きな値となります。値の比較は、ヒープ全体の比較メソッドとして実装されているものを使用します。

SplHeap
- SplMaxHeap
- SplMinHeap
SplPriorityQueue

配列

配列は、データを連続的に格納してインデックス経由でアクセスできるようにした構造です。 PHP の配列と混同しないようにしましょう。PHP の配列は、実際のところは順序つきハッシュテーブルとして実装されています。

SplFixedArray

マップ

マップは、キー/値のペアからなるデータ構造です。 PHP の配列は、整数値/文字列を値と対応させたマップとみなすことができます。 SPL では、オブジェクトとデータを対応させるマップを提供しています。このマップは、オブジェクトの集合として扱うことができます。

SplObjectStorage

SplDoublyLinkedList クラス

はじめに

SplDoublyLinkedList クラスは、双方向リンクリストの主要な機能を提供します。

クラス概要

SplDoublyLinkedList

implements Iterator Countable ArrayAccess Serializable

/* 定数 */

public const int SplDoublyLinkedList::IT_MODE_LIFO;

public const int SplDoublyLinkedList::IT_MODE_FIFO;

public const int SplDoublyLinkedList::IT_MODE_DELETE;

public const int SplDoublyLinkedList::IT_MODE_KEEP;

/* メソッド */

public void add(int $index, mixed $value)

public mixed bottom()

public int count()

public mixed current()

public int getIteratorMode()

public bool isEmpty()

public int key()

public void next()

public bool offsetExists(int $index)

public mixed offsetGet(int $index)

public void offsetSet(intnull $index, mixed $value)

public void offsetUnset(int $index)

public mixed pop()

public void prev()

public void push(mixed $value)

public void rewind()

public string serialize()

public int setIteratorMode(int $mode)

public mixed shift()

public mixed top()

public void unserialize(string $data)

public void unshift(mixed $value)

public bool valid()

定義済み定数

イテレーションの方向

SplDoublyLinkedList::IT_MODE_LIFO: スタックのように、LIFO (最後に入れたものを最初に取り出す) の順で走査されます。
SplDoublyLinkedList::IT_MODE_FIFO: キューのように、FIFO(先入れ先出し) の順で走査されます。

イテレーションの振る舞い

SplDoublyLinkedList::IT_MODE_DELETE: 走査された要素を削除します。
SplDoublyLinkedList::IT_MODE_KEEP: 走査されても要素を削除しません。

SplStack クラス

はじめに

SplStack クラスは、スタックの主要な機能を提供します。双方向リンクリストのイテレータのモードを SplDoublyLinkedList::IT_MODE_LIFO に設定することで実装しています。

クラス概要

SplStack

extends SplDoublyLinkedList

/* 継承した定数 */

public const int SplDoublyLinkedList::IT_MODE_LIFO;

public const int SplDoublyLinkedList::IT_MODE_FIFO;

public const int SplDoublyLinkedList::IT_MODE_DELETE;

public const int SplDoublyLinkedList::IT_MODE_KEEP;

/* 継承したメソッド */

public void add(int $index, mixed $value)

public mixed bottom()

public int count()

public mixed current()

public int getIteratorMode()

public bool isEmpty()

public int key()

public void next()

public bool offsetExists(int $index)

public mixed offsetGet(int $index)

public void offsetSet(intnull $index, mixed $value)

public void offsetUnset(int $index)

public mixed pop()

public void prev()

public void push(mixed $value)

public void rewind()

public string serialize()

public int setIteratorMode(int $mode)

public mixed shift()

public mixed top()

public void unserialize(string $data)

public void unshift(mixed $value)

public bool valid()

例

例1 SplStack の例


<?php
$q = new SplStack();
$q[] = 1;
$q[] = 2;
$q[] = 3;
foreach ($q as $elem)  {
 echo $elem."\n";
}
?>

上の例の出力は以下となります。

3
2
1

SplQueue クラス

はじめに

SplQueue クラスは、キューの主要な機能を提供します。双方向リンクリストのイテレータのモードを SplDoublyLinkedList::IT_MODE_FIFO に設定することで実装しています。

クラス概要

SplQueue

extends SplDoublyLinkedList

/* 継承した定数 */

public const int SplDoublyLinkedList::IT_MODE_LIFO;

public const int SplDoublyLinkedList::IT_MODE_FIFO;

public const int SplDoublyLinkedList::IT_MODE_DELETE;

public const int SplDoublyLinkedList::IT_MODE_KEEP;

/* メソッド */

public mixed SplQueue::dequeue()

public void SplQueue::enqueue(mixed $value)

/* 継承したメソッド */

public void add(int $index, mixed $value)

public mixed bottom()

public int count()

public mixed current()

public int getIteratorMode()

public bool isEmpty()

public int key()

public void next()

public bool offsetExists(int $index)

public mixed offsetGet(int $index)

public void offsetSet(intnull $index, mixed $value)

public void offsetUnset(int $index)

public mixed pop()

public void prev()

public void push(mixed $value)

public void rewind()

public string serialize()

public int setIteratorMode(int $mode)

public mixed shift()

public mixed top()

public void unserialize(string $data)

public void unshift(mixed $value)

public bool valid()

例

例2 SplQueue の例


<?php
$q = new SplQueue();
$q[] = 1;
$q[] = 2;
$q[] = 3;
foreach ($q as $elem)  {
 echo $elem."\n";
}
?>

上の例の出力は以下となります。

1
2
3

例3 SplQueue を使ってタスクを効率的に処理する


<?php
$q = new SplQueue();
$q->setIteratorMode(SplQueue::IT_MODE_DELETE);
// ... enqueue some tasks on the queue ...
// process them
foreach ($q as $task) {
    // ... process $task ...
    // add new tasks on the queue
    $q[] = $newTask;
    // ...
}
?>

SplHeap クラス

はじめに

SplHeap クラスは、ヒープの主要な機能を提供します。

クラス概要

abstract SplHeap

implements Iterator Countable

/* メソッド */

protected int compare(mixed $value1, mixed $value2)

public int count()

public mixed current()

public mixed extract()

public true insert(mixed $value)

public bool isCorrupted()

public bool isEmpty()

public int key()

public void next()

public bool recoverFromCorruption()

public void rewind()

public mixed top()

public bool valid()

SplMaxHeap クラス

はじめに

SplMaxHeap クラスは、ヒープの主要な機能を提供し、最大値を先頭に保ちます。

クラス概要

SplMaxHeap

extends SplHeap

/* メソッド */

protected int SplMaxHeap::compare(mixed $value1, mixed $value2)

/* 継承したメソッド */

protected int compare(mixed $value1, mixed $value2)

public int count()

public mixed current()

public mixed extract()

public true insert(mixed $value)

public bool isCorrupted()

public bool isEmpty()

public int key()

public void next()

public bool recoverFromCorruption()

public void rewind()

public mixed top()

public bool valid()

SplMinHeap クラス

はじめに

SplMinHeap クラスは、ヒープの主要な機能を提供し、最小値を先頭に保ちます。

クラス概要

SplMinHeap

extends SplHeap

/* メソッド */

protected int SplMinHeap::compare(mixed $value1, mixed $value2)

/* 継承したメソッド */

protected int compare(mixed $value1, mixed $value2)

public int count()

public mixed current()

public mixed extract()

public true insert(mixed $value)

public bool isCorrupted()

public bool isEmpty()

public int key()

public void next()

public bool recoverFromCorruption()

public void rewind()

public mixed top()

public bool valid()

SplPriorityQueue クラス

はじめに

SplPriorityQueue クラスは、優先順位つきキューの主要な機能を提供します。最大ヒープを使用して実装しています。

注意: 優先度が等しい要素の順番は 未定義 です。優先度が等しい要素の順序は、挿入された順序と異なるかもしれません。

クラス概要

SplPriorityQueue

implements Iterator Countable

/* 定数 */

public const int SplPriorityQueue::EXTR_BOTH;

public const int SplPriorityQueue::EXTR_PRIORITY;

public const int SplPriorityQueue::EXTR_DATA;

/* メソッド */

public int compare(mixed $priority1, mixed $priority2)

public int count()

public mixed current()

public mixed extract()

public int getExtractFlags()

public true insert(mixed $value, mixed $priority)

public bool isCorrupted()

public bool isEmpty()

public int key()

public void next()

public bool recoverFromCorruption()

public void rewind()

public int setExtractFlags(int $flags)

public mixed top()

public bool valid()

定義済み定数

SplPriorityQueue::EXTR_BOTH
SplPriorityQueue::EXTR_PRIORITY
SplPriorityQueue::EXTR_DATA

SplFixedArray クラス

はじめに

SplFixedArray クラスは配列の主要な機能を提供します。 SplFixedArray と通常の PHP の配列との主な違いは、 SplFixedArray は手動でリサイズしなければならないことと、整数値で指定した範囲内の添字しか使用できないところです。これにより、標準の array よりメモリ消費が少なくて済みます。

クラス概要

SplFixedArray

implements IteratorAggregate ArrayAccess Countable JsonSerializable

/* メソッド */

public __construct(int $size = 0)

public int count()

public mixed current()

public static SplFixedArray fromArray(array $array, bool $preserveKeys = true)

public Iterator getIterator()

public int getSize()

public mixed jsonSerialize()

public int key()

public void next()

public bool offsetExists(int $index)

public mixed offsetGet(int $index)

public void offsetSet(int $index, mixed $value)

public void offsetUnset(int $index)

public void rewind()

public array __serialize()

public bool setSize(int $size)

public array toArray()

public void __unserialize(array $data)

public bool valid()

public void __wakeup()

変更履歴

バージョン	説明
8.2.0	マジックメソッド SplFixedArray::__serialize と SplFixedArray::__unserialize が、SplFixedArray に追加されました。
8.1.0	SplFixedArray は、 JsonSerializable を実装するようになりました。
8.0.0	SplFixedArray は、 IteratorAggregate を実装するようになりました。これより前のバージョンでは、 Iterator を実装していました。

例

例1 SplFixedArray の使用例


<?php
// 固定長の配列を初期化します
$array = new SplFixedArray(5);

$array[1] = 2;
$array[4] = "foo";

var_dump($array[0]); // NULL
var_dump($array[1]); // int(2)

var_dump($array["4"]); // string(3) "foo"

// 配列のサイズを 10 に拡大します
$array->setSize(10);

$array[9] = "asdf";

// 配列のサイズを 2 に縮めます
$array->setSize(2);

// 以下は RuntimeException: Index invalid or out of range となります
try {
    var_dump($array["non-numeric"]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}

try {
    var_dump($array[-1]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}

try {
    var_dump($array[5]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}
?>

上の例の出力は以下となります。

NULL
int(2)
string(3) "foo"
RuntimeException: Index invalid or out of range
RuntimeException: Index invalid or out of range
RuntimeException: Index invalid or out of range

SplObjectStorage クラス

はじめに

SplObjectStorage クラスは、オブジェクトをデータに対応させたり、データを渡さずオブジェクトセットとして使用したりします。これらはどちらも、オブジェクトを一意に特定したい場合に便利です。

クラス概要

SplObjectStorage

implements Countable Iterator Serializable ArrayAccess

/* メソッド */

public int addAll(SplObjectStorage $storage)

public void attach(object $object, mixed $info = null)

public bool contains(object $object)

public int count(int $mode = COUNT_NORMAL)

public object current()

public void detach(object $object)

public string getHash(object $object)

public mixed getInfo()

public int key()

public void next()

public bool offsetExists(object $object)

public mixed offsetGet(object $object)

public void offsetSet(object $object, mixed $info = null)

public void offsetUnset(object $object)

public int removeAll(SplObjectStorage $storage)

public int removeAllExcept(SplObjectStorage $storage)

public void rewind()

public string serialize()

public void setInfo(mixed $info)

public void unserialize(string $data)

public bool valid()

例

例1 SplObjectStorage をセットとして使用


<?php
// オブジェクトセット
$s = new SplObjectStorage();

$o1 = new stdClass;
$o2 = new stdClass;
$o3 = new stdClass;

$s->attach($o1);
$s->attach($o2);

var_dump($s->contains($o1));
var_dump($s->contains($o2));
var_dump($s->contains($o3));

$s->detach($o2);

var_dump($s->contains($o1));
var_dump($s->contains($o2));
var_dump($s->contains($o3));
?>

上の例の出力は以下となります。

bool(true)
bool(true)
bool(false)
bool(true)
bool(false)
bool(false)

例2 SplObjectStorage をマップとして使用


<?php
// オブジェクトとデータを対応させます
$s = new SplObjectStorage();

$o1 = new stdClass;
$o2 = new stdClass;
$o3 = new stdClass;

$s[$o1] = "data for object 1";
$s[$o2] = array(1,2,3);

if (isset($s[$o2])) {
    var_dump($s[$o2]);
}
?>

上の例の出力は以下となります。

array(3) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
}