PHP的SPL擴展庫（一）數(shù)據(jù)結構
SPL 庫也叫做 PHP 標準庫，主要就是用于解決典型問題的一組接口或類的集合。這些典型問題包括什么呢？比如我們今天要講的數(shù)據(jù)結構，還有一些設計模式的實現(xiàn)，就像我們之前講過的觀察者模式相關的接口在 SPL 庫中都有提供。話說回來，在 PHP 中，由于語言的特點，其實很多數(shù)據(jù)結構都和我們用 C 語言實現(xiàn)的略有不同，比如說鏈表，由于沒有結構的概念，所以我們一般會使用類來代表鏈表的結點。除了這個之外，要手寫鏈表還需要鏈表的增、刪、改、查等操作，而 SPL 庫中其實已經(jīng)幫我們提供了一個雙向鏈表的實現(xiàn)，并且還可以在這個鏈表的基礎上直接實現(xiàn)棧和隊列的操作。
雙向鏈表
在 SPL 庫中，雙向鏈表只需要實例化一個 SplDoublyLinkedList 類就可以了，然后我們就可以對這個實例化之后的雙向鏈表對象進行各種操作。
$dll = new SplDoublyLinkedList();
var_dump($dll->isEmpty()); // bool(true)
$dll->push(200);
$dll->push(300);
$dll->unshift("五號");
$dll->add(2, "六號");
var_dump($dll->isEmpty()); // bool(false)
var_dump($dll);
// object(SplDoublyLinkedList)#1 (2) {
// ["flags":"SplDoublyLinkedList":private]=>
// int(0)
// ["dllist":"SplDoublyLinkedList":private]=>
// array(4) {
// [0]=>
// string(6) "五號"
// [1]=>
// int(200)
// [2]=>
// string(6) "六號"
// [3]=>
// int(300)
// }
// }
從代碼中可以看出，push() 、 unshift() 、add() 方法都是向鏈表中添加數(shù)據(jù)，而 isEmpty() 則用于判斷鏈表是否為空。直接打印顯示鏈表的內(nèi)容，可以看到鏈表的內(nèi)部是一個數(shù)組數(shù)據(jù)。
var_dump($dll->top()); // int(300)
var_dump($dll->bottom()); // string(6) "五號"
var_dump($dll->pop()); // int(300)
var_dump($dll->shift()); // string(6) "五號"
var_dump($dll->serialize()); // string(25) "i:0;:i:200;:s:6:"六號";"
var_dump($dll->count()); // int(2)
top() 和 bottom() 分別獲取的是鏈表的頂部和底部的數(shù)據(jù)。而 pop() 和 shift() 則是分別從底部和頂部彈出數(shù)據(jù)。后面我們會看到，根據(jù)設置的不同，它他們也會遵循使用棧還是隊列的方式來彈出數(shù)據(jù)。
serialize() 方法可以直接獲得序列化后的鏈表內(nèi)容。count() 方法就是返回鏈表內(nèi)元素的數(shù)量了。
$dll->offsetSet(1, '修改成新六號');
var_dump($dll->offsetGet(1)); // string(18) "修改成新六號"
var_dump($dll->offsetExists(1)); // bool(true)
$dll->offsetUnset(1);
var_dump($dll->offsetExists(1)); // bool(false)
offset 相關的方法函數(shù)是根據(jù)偏移值來操作鏈表內(nèi)的數(shù)據(jù)，其實就可以理解成是根據(jù)位置下標來操作數(shù)據(jù)。
在默認情況下，我們遍歷鏈表的話，是類似于隊列的形式進行輸出的，也就是先進先出的狀態(tài)。
for($i=1;$i<5;$i++){
$dll->push($i);
}
var_dump($dll->getIteratorMode()); // int(0)
$dll->rewind();
while($dll->valid()){
echo '============', PHP_EOL;
echo 'key:', $dll->key(), PHP_EOL;
echo ' current:', $dll->current(), PHP_EOL;
$dll->next();
}
// ============
// key:0
// current:200
// ============
// key:1
// current:1
// ============
// key:2
// current:2
// ============
// key:3
// current:3
// ============
// key:4
// current:4
通過 rewind() 將鏈表指針恢復到開頭，然后通過 valid() 方法判斷當前數(shù)據(jù)是否有效，next() 用于將鏈表指針移動到下一個，就可以進行數(shù)據(jù)的遍歷。我們通過設置鏈表的迭代模式，就可以改變鏈表的迭代輸出規(guī)則，比如我們需要類似棧類型的后進先出。
$dll->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
$dll->rewind();
while($dll->valid()){
echo 'IT_MODE_LIFO============', PHP_EOL;
echo 'key:', $dll->key(), PHP_EOL;
echo ' current:', $dll->current(), PHP_EOL;
$dll->next();
}
// IT_MODE_LIFO============
// key:4
// current:4
// IT_MODE_LIFO============
// key:3
// current:3
// IT_MODE_LIFO============
// key:2
// current:2
// IT_MODE_LIFO============
// key:1
// current:1
// IT_MODE_LIFO============
// key:0
// current:200
另外，它還有一個比較好玩的迭代模式，就是直接邊遍歷，邊刪除。
$dll->setIteratorMode(SplDoublyLinkedList::IT_MODE_DELETE);
$dll->rewind();
while($dll->valid()){
echo 'IT_MODE_DELETE============', PHP_EOL;
echo 'key:', $dll->key(), PHP_EOL;
echo ' current:', $dll->current(), PHP_EOL;
$dll->next();
}
var_dump($dll);
// object(SplDoublyLinkedList)#1 (2) {
// ["flags":"SplDoublyLinkedList":private]=>
// int(1)
// ["dllist":"SplDoublyLinkedList":private]=>
// array(0) {
// }
// }
在使用 IT_MODE_DELETE 進行遍歷之后，鏈表里面的數(shù)據(jù)內(nèi)容也就變成空的了。默認情況下，這個 IteraotrMode 的內(nèi)容是 SplDoublyLinkedList::IT_MODE_KEEP | SplDoublyLinkedList::IT_MODE_FIFO 這個值，表示的就是數(shù)據(jù)保持原來的狀態(tài)并且使用先進先出的規(guī)則。
棧
棧類 SplStack 其實和后面的隊列類 SplQueue 一樣，都是繼承自鏈表類的，也就是說它們其實就是相當于設置好了 IteratorMode 的鏈表對象。所以它們的方法函數(shù)其實都沒有什么太大的區(qū)別。
// 棧
$stack = new SplStack();
for($i=1;$i<5;$i++){
$stack->push($i);
}
var_dump($stack->getIteratorMode()); // int(6)
var_dump($stack);
// object(SplStack)#2 (2) {
// ["flags":"SplDoublyLinkedList":private]=>
// int(6)
// ["dllist":"SplDoublyLinkedList":private]=>
// array(4) {
// [0]=>
// int(1)
// [1]=>
// int(2)
// [2]=>
// int(3)
// [3]=>
// int(4)
// }
// }
$stack->rewind();
while($stack->valid()){
echo '============', PHP_EOL;
echo 'key:', $stack->key(), PHP_EOL;
echo ' current:', $stack->current(), PHP_EOL;
$stack->next();
}
// ============
// key:3
// current:4
// ============
// key:2
// current:3
// ============
// key:1
// current:2
// ============
// key:0
// current:1
隊列
SplQueue 隊列相對于鏈表類和棧類來說，多了兩個方法。
// 隊列
$queue = new SplQueue();
for($i=1;$i<5;$i++){
$queue->enqueue($i);
}
var_dump($queue->getIteratorMode()); // int(4)
var_dump($queue);
// object(SplQueue)#3 (2) {
// ["flags":"SplDoublyLinkedList":private]=>
// int(4)
// ["dllist":"SplDoublyLinkedList":private]=>
// array(4) {
// [0]=>
// int(1)
// [1]=>
// int(2)
// [2]=>
// int(3)
// [3]=>
// int(4)
// }
// }
$queue->rewind();
while($queue->valid()){
echo '============', PHP_EOL;
echo 'key:', $queue->key(), PHP_EOL;
echo ' current:', $queue->current(), PHP_EOL;
echo ' info:', $queue->dequeue(), PHP_EOL;
$queue->next();
}
// ============
// key:0
// current:1
// info:1
// ============
// key:1
// current:2
// info:2
// ============
// key:2
// current:3
// info:3
// ============
// key:3
// current:4
// info:4
enqueue() 和 dequeue() 方法分別就是入隊和出隊的意思，其實就可以看成是 push() 和 shift() 的操作，底部添加頂部彈出。
堆
堆棧堆棧，總會有人把堆和棧說成是一個東西，其實它們可是完全不同的兩個數(shù)據(jù)結構哦。棧是線性的邏輯結構，而堆則一般是樹形的邏輯結構，當然，它們的存儲結構都是可以用相同的鏈表或順序表來表示的。在堆中，有大頂堆和小頂堆的概念，SPL 也為我們分別提供了這兩種實現(xiàn)。（不了解堆的同學可以自行查閱相關資料）
大頂堆
$maxHeap = new SplMaxHeap();
for($i=1;$i<5;$i++){
$maxHeap->insert($i);
}
var_dump($maxHeap);
// object(SplMaxHeap)#4 (3) {
// ["flags":"SplHeap":private]=>
// int(0)
// ["isCorrupted":"SplHeap":private]=>
// bool(false)
// ["heap":"SplHeap":private]=>
// array(4) {
// [0]=>
// int(4)
// [1]=>
// int(3)
// [2]=>
// int(2)
// [3]=>
// int(1)
// }
// }
var_dump($maxHeap->count()); // int(4)
var_dump($maxHeap->top()); // int(4)
var_dump($maxHeap->extract()); // int(4)
var_dump($maxHeap->count()); // int(3)
var_dump($maxHeap->top()); // int(3)
var_dump($maxHeap);
// object(SplMaxHeap)#4 (3) {
// ["flags":"SplHeap":private]=>
// int(0)
// ["isCorrupted":"SplHeap":private]=>
// bool(false)
// ["heap":"SplHeap":private]=>
// array(3) {
// [0]=>
// int(3)
// [1]=>
// int(1)
// [2]=>
// int(2)
// }
// }
$maxHeap->rewind();
while($maxHeap->valid()){
echo '============', PHP_EOL;
echo 'key:', $maxHeap->key(), PHP_EOL;
echo ' current:', $maxHeap->current(), PHP_EOL;
$maxHeap->next();
}
// ============
// key:2
// current:3
// ============
// key:1
// current:2
// ============
// key:0
// current:1
var_dump($maxHeap->isCorrupted()); // bool(false)
$maxHeap->recoverFromCorruption();
SplMaxHeap 類就是用于生成大頂堆實例的類模板。它通過 insert() 方法插入數(shù)據(jù)，通過 extract() 方法抽取數(shù)據(jù)，同樣也包括 count() 和 top() 這類的常用方法函數(shù)，以及遍歷相關的那些方法函數(shù)。
另外，堆的操作中還包括兩個方法函數(shù)，分別用于判斷堆是否處于損壞狀態(tài) isCorrupted() 以及從損壞狀態(tài)恢復 recoverFromCorruption() 相關的操作函數(shù)。
小頂堆
小頂堆的內(nèi)容和大頂堆就完全一樣了，只是它的內(nèi)部結構不同，大頂堆是父結點總是最大的，而小頂堆就是反過來父結點總是最小的數(shù)據(jù)。
$minHeap = new SplMinHeap();
for($i=1;$i<5;$i++){
$minHeap->insert($i);
}
var_dump($minHeap);
// object(SplMinHeap)#5 (3) {
// ["flags":"SplHeap":private]=>
// int(0)
// ["isCorrupted":"SplHeap":private]=>
// bool(false)
// ["heap":"SplHeap":private]=>
// array(4) {
// [0]=>
// int(1)
// [1]=>
// int(2)
// [2]=>
// int(3)
// [3]=>
// int(4)
// }
// }
var_dump($minHeap->top()); // int(1)
大頂堆實現(xiàn)的優(yōu)先隊列
除了大頂堆和小頂堆的普通操作之外，SPL 庫中還有一個通過大頂堆來實現(xiàn)的優(yōu)先隊列的類模板。
$pQueue = new SplPriorityQueue();
for($i=1;$i<5;$i++){
$pQueue->insert($i, random_int(1,10));
}
var_dump($pQueue);
// object(SplPriorityQueue)#6 (3) {
// ["flags":"SplPriorityQueue":private]=>
// int(1)
// ["isCorrupted":"SplPriorityQueue":private]=>
// bool(false)
// ["heap":"SplPriorityQueue":private]=>
// array(4) {
// [0]=>
// array(2) {
// ["data"]=>
// int(3)
// ["priority"]=>
// int(10)
// }
// [1]=>
// array(2) {
// ["data"]=>
// int(4)
// ["priority"]=>
// int(7)
// }
// [2]=>
// array(2) {
// ["data"]=>
// int(1)
// ["priority"]=>
// int(3)
// }
// [3]=>
// array(2) {
// ["data"]=>
// int(2)
// ["priority"]=>
// int(2)
// }
// }
// }
while($pQueue->valid()){
var_dump($pQueue->extract());
}
// int(3)
// int(4)
// int(1)
// int(2)
它的操作方法函數(shù)和堆的操作方法函數(shù)都是一樣的，只是 insert() 方法中多了一個參數(shù)可以設置數(shù)據(jù)的優(yōu)先級。通過設置不同的優(yōu)先級我們可以看到數(shù)據(jù)以及遍歷輸出的結果都會發(fā)生變化，順序都是以優(yōu)先級來確定的。
固定數(shù)組
什么叫固定數(shù)組呢？在 PHP 中，數(shù)組這個結構非常強大，它即可以是普通下標類型的數(shù)組，也可以 HashMap鍵值對 形式的數(shù)組，它的長度也是不受限制的，只要內(nèi)存夠就可以靈活地處理數(shù)組的長度。不過在靜態(tài)語言中，特別是我們學習過的 C 語言中，數(shù)組都是固定長度的，也就是說，數(shù)組的內(nèi)存大小是在數(shù)組初始化的時候就確定好的，如果超出了數(shù)組長度的操作發(fā)生，就會產(chǎn)生越界問題。還是通過一個例子來看吧。
// 數(shù)組
$norArr = [];
$norArr[1] = 'b';
$norArr[4] = 'f';
var_dump($norArr);
// array(2) {
// [1]=>
// string(1) "b"
// [4]=>
// string(1) "f"
// }
$fArr = new SplFixedArray(5);
$fArr[1] = 'b';
$fArr[4] = 'f';
var_dump($fArr);
// object(SplFixedArray)#7 (5) {
// [0]=>
// NULL
// [1]=>
// string(1) "b"
// [2]=>
// NULL
// [3]=>
// NULL
// [4]=>
// string(1) "f"
// }
norArr 是普通的 PHP 數(shù)組，我們添加了兩個數(shù)據(jù)之后在這個數(shù)組中只有兩個元素。下面的 SplFixedArray 類實例化出來的 fArr 則是固定數(shù)組。它在實例化的時候必須傳遞一個構造參數(shù)來指定數(shù)組長度。可以看到，fArr 輸出的結果是固定有 5 個數(shù)據(jù)的，并且我們沒有賦值的數(shù)據(jù)都會給一個默認的 NULL 值。是不是和 C 的數(shù)組一樣一樣的。
當然，固定數(shù)組就會有數(shù)組下標越界的問題了。
$fArr[6] = 'h'; // Fatal error: Uncaught RuntimeException: Index invalid or out of range
不過我們可以手動地修改數(shù)組的大小來改變數(shù)據(jù)的長度。
$fArr->setSize(7);
$fArr[6] = 'h';
var_dump($fArr->getSize()); // int(7)
現(xiàn)在，數(shù)組的長度就是 7 了，可以存放 7 條數(shù)據(jù)。它也可以直接從一個普通數(shù)組轉換過來，不過需要注意的是，轉換數(shù)組必須是數(shù)字下標類型的數(shù)組，字符串鍵的 HashMap 數(shù)組是不可以的哦。
$fArr2 = SplFixedArray::fromArray(range(1,3));
var_dump($fArr2);
// object(SplFixedArray)#8 (3) {
// [0]=>
// int(1)
// [1]=>
// int(2)
// [2]=>
// int(3)
// }
// $fArr3 = SplFixedArray::fromArray(['new'=>1, 'old'=>2]);
// var_dump($fArr3);
// PHP Fatal error: Uncaught InvalidArgumentException: array must contain only positive integer keys
剩下的就是和其它數(shù)據(jù)結構一樣的一些操作方法函數(shù)了。
var_dump($fArr->count()); // int(7)
var_dump($fArr->offsetGet(2)); // NULL
$fArr->offsetSet(2, 'new');
var_dump($fArr->offsetGet(2)); // string(3) "new"
var_dump($fArr->offsetExists(2)); // bool(true)
$fArr->offsetUnset(2);
var_dump($fArr->offsetExists(2)); // bool(false)
$fArr->rewind();
while($fArr->valid()){
echo '============', PHP_EOL;
echo 'key:', $fArr->key(), PHP_EOL;
echo ' current:', $fArr->current(), PHP_EOL;
$fArr->next();
}
// ============
// key:0
// current:
// ============
// key:1
// current:b
// ============
// key:2
// current:
// ============
// key:3
// current:
// ============
// key:4
// current:f
// ============
// key:5
// current:
// ============
// key:6
// current:h
既然它是一種數(shù)組對象，那么迭代其實不用這么麻煩的，我們直接通過 for 和 foreach 就可以了。它和其它的數(shù)組結構一樣，都實現(xiàn)了 Iterator 和 Countable 這兩個接口，都是可以通過 for 和 foreach 來進行遍歷的。
foreach($fArr as $f){
var_dump($f);
}
for($i=0;$i<count($fArr);$i++){
var_dump($fArr[$i]);
}
對象數(shù)據(jù)映射
最后一種數(shù)據(jù)結構，對象數(shù)據(jù)映射。這是個什么鬼？最簡單直接的理解其實就是把一個對象當成是 【鍵】，然后以這些鍵形成一個數(shù)組結構。
$os = new SplObjectStorage();
$o1 = new stdClass;
$o2 = new stdClass;
$o3 = new stdClass;
$o4 = new stdClass;
$o5 = new stdClass;
$os->attach($o1);
$os->attach($o2);
$os->attach($o3);
$os->attach($o4, 'd4');
$os->attach($o5, 'd5');
var_dump($os);
// object(SplObjectStorage)#9 (1) {
// ["storage":"SplObjectStorage":private]=>
// array(5) {
// ["00000000736a0aba000000002f97228d"]=>
// array(2) {
// ["obj"]=>
// object(stdClass)#10 (0) {
// }
// ["inf"]=>
// NULL
// }
// ["00000000736a0abb000000002f97228d"]=>
// array(2) {
// ["obj"]=>
// object(stdClass)#11 (0) {
// }
// ["inf"]=>
// NULL
// }
// ["00000000736a0abc000000002f97228d"]=>
// array(2) {
// ["obj"]=>
// object(stdClass)#12 (0) {
// }
// ["inf"]=>
// NULL
// }
// ["00000000736a0abd000000002f97228d"]=>
// array(2) {
// ["obj"]=>
// object(stdClass)#13 (0) {
// }
// ["inf"]=>
// string(2) "d4"
// }
// ["00000000736a0abe000000002f97228d"]=>
// array(2) {
// ["obj"]=>
// object(stdClass)#14 (0) {
// }
// ["inf"]=>
// string(2) "d5"
// }
// }
// }
是不是有點意思，attach() 就可以向這個 SplObjectStorage 對象存儲映射類中添加數(shù)據(jù)。它的第二個參數(shù)可以指定一個數(shù)據(jù)內(nèi)容，其實就可以看作是普通數(shù)組中的 值 。
var_dump($os->count()); // int(5)
$os->detach($o2);
var_dump($os->count()); // int(4)
var_dump($os->contains($o2)); // bool(false)
var_dump($os->contains($o3)); // bool(true)
var_dump($os->getHash($o4)); // string(32) "000000003e67a2330000000040e598c9"
var_dump($os->offsetGet($o4)); // string(2) "d4"
$os->offsetSet($o4, 'new d4');
var_dump($os->offsetGet($o4)); // string(6) "new d4"
var_dump($os->offsetExists($o4)); // bool(true)
$os->offsetUnset($o4);
var_dump($os->offsetExists($o4)); // bool(false)
$os->rewind();
$os[$o1] = 'new d1';
while($os->valid()){
echo '============', PHP_EOL;
echo 'key:', $os->key(), PHP_EOL;
if($os->getInfo() === NULL){
$os->setInfo('new iter info');
}
echo ' info:', $os->getInfo(), PHP_EOL;
echo ' current:', PHP_EOL;
var_dump($os->current());
$os->next();
}
// ============
// key:0
// info:new d1
// current:
// object(stdClass)#10 (0) {
// }
// ============
// key:1
// info:new iter info
// current:
// object(stdClass)#12 (0) {
// }
// ============
// key:2
// info:d5
// current:
// object(stdClass)#14 (0) {
// }
其它的遍歷查詢操作都是和其它數(shù)據(jù)結構的操作類似的，這里就不多說了。其中比較特別的是 detach() 方法是刪除數(shù)據(jù)的，getHash() 則是獲取這個對象在存儲集合中的 Hash 值的，這個值也可以看做是這個對象在這個對象映射集合中的下標，我們其它的針對對象的操作判斷其實是都是在內(nèi)部轉換成這個數(shù)組下標來進行操作的。
總結
其實這一圈學習下來，突然發(fā)現(xiàn)有了 SPL 的這幾個數(shù)據(jù)結構之后，我們在 PHP 下面還真不太需要關心什么數(shù)據(jù)結構方面的實現(xiàn)了，直接通用點就上個雙向鏈表就完了，簡單的就只是寫算法了。好吧，學習還是要扎實點，數(shù)據(jù)結構和算法真正要學習的其實是它內(nèi)部的思想和邏輯。當然，既然已經(jīng)提供了，那么我們平常的業(yè)務開發(fā)中還是更建議直接使用 SPL 的這些數(shù)據(jù)結構來處理！
測試代碼：
https://github.com/zhangyue0503/dev-blog/blob/master/php/2021/01/source/3.PHP的SPL擴展庫（一）數(shù)據(jù)結構.php
參考文檔：
https://www./manual/zh/spl.datastructures.php
