创意电子

标题: PHP的SPL扩展库（一）数据结构 [打印本页]

作者: 硬核项目经理 时间: 2021-9-30 15:07
标题: PHP的SPL扩展库（一）数据结构

SPL 库也叫做 PHP 标准库，主要就是用于解决典范问题的一组接口或类的集合。这些典范问题包括什么呢？比如我们今天要讲的数据结构，尚有一些设计模式的实现，就像我们之前讲过的观察者模式相关的接口在 SPL 库中都有提供。话说回来，在 PHP 中，由于语言的特点，实在很多数据结构都和我们用 C 语言实现的略有不同，比如说链表，由于没有结构的概念，所以我们一般会使用类来代表链表的结点。除了这个之外，要手写链表还需要链表的增、删、改、查等操作，而 SPL 库中实在已经帮我们提供了一个双向链表的实现，而且还可以在这个链表的底子上直接实现栈和队列的操作。

双向链表

在 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() 方法都是向链表中添加数据，而 isEmpty() 则用于判断链表是否为空。直接打印显示链表的内容，可以看到链表的内部是一个数组数据。

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() 分别获取的是链表的顶部和底部的数据。而 pop() 和 shift() 则是分别从底部和顶部弹出数据。后面我们会看到，根据设置的不同，它他们也会遵循使用栈照旧队列的方式来弹出数据。

serialize() 方法可以直接获得序列化后的链表内容。count() 方法就是返回链表内元素的数量了。

$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 相关的方法函数是根据偏移值来操作链表内的数据，实在就可以明白成是根据位置下标来操作数据。

在默认环境下，我们遍历链表的话，是雷同于队列的情势举行输出的，也就是先进先出的状态。

for($i=1;$ipush($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() 方法判断当前数据是否有效，next() 用于将链表指针移动到下一个，就可以举行数据的遍历。我们通过设置链表的迭代模式，就可以改变链表的迭代输出规则，比如我们需要雷同栈类型的后进先出。

$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 举行遍历之后，链表里面的数据内容也就变成空的了。默认环境下，这个 IteraotrMode 的内容是 SplDoublyLinkedList::IT_MODE_KEEP | SplDoublyLinkedList::IT_MODE_FIFO 这个值，表现的就是数据保持原来的状态而且使用先进先出的规则。

栈

栈类 SplStack 实在和后面的队列类 SplQueue 一样，都是继承自链表类的，也就是说它们实在就是相当于设置好了 IteratorMode 的链表对象。所以它们的方法函数实在都没有什么太大的区别。

// 栈$stack = new SplStack();for($i=1;$ipush($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;$ienqueue($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() 的操作，底部添加顶部弹出。

堆

堆栈堆栈，总会有人把堆和栈说成是一个东西，实在它们可是完全不同的两个数据结构哦。栈是线性的逻辑结构，而堆则一般是树形的逻辑结构，当然，它们的存储结构都是可以用相同的链表或顺序表来表现的。在堆中，有大顶堆和小顶堆的概念，SPL 也为我们分别提供了这两种实现。（不相识堆的同砚可以自行查阅相关资料）

大顶堆

$maxHeap = new SplMaxHeap();for($i=1;$iinsert($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:1var_dump($maxHeap->isCorrupted()); // bool(false)$maxHeap->recoverFromCorruption();

SplMaxHeap 类就是用于生成大顶堆实例的类模板。它通过 insert() 方法插入数据，通过 extract() 方法抽取数据，同样也包括 count() 和 top() 这类的常用方法函数，以及遍历相关的那些方法函数。

另外，堆的操作中还包括两个方法函数，分别用于判断堆是否处于破坏状态 isCorrupted() 以及从破坏状态恢复 recoverFromCorruption() 相关的操作函数。

小顶堆

小顶堆的内容和大顶堆就完全一样了，只是它的内部结构不同，大顶堆是父结点总是最大的，而小顶堆就是反过来父结点总是最小的数据。

$minHeap = new SplMinHeap();for($i=1;$iinsert($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)大顶堆实现的优先队列

除了大顶堆和小顶堆的平凡操作之外，SPL 库中尚有一个通过大顶堆来实现的优先队列的类模板。

$pQueue = new SplPriorityQueue();for($i=1;$iinsert($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)

它的操作方法函数和堆的操作方法函数都是一样的，只是 insert() 方法中多了一个参数可以设置数据的优先级。通过设置不同的优先级我们可以看到数据以及遍历输出的效果都会发生变革，顺序都是以优先级来确定的。

固定数组

什么叫固定数组呢？在 PHP 中，数组这个结构非常强大，它即可以是平凡下标类型的数组，也可以 HashMap键值对情势的数组，它的长度也是不受限制的，只要内存够就可以灵活地处理数组的长度。不过在静态语言中，特别是我们学习过的 C 语言中，数组都是固定长度的，也就是说，数组的内存大小是在数组初始化的时候就确定好的，如果超出了数组长度的操作发生，就会产生越界问题。照旧通过一个例子来看吧。

// 数组$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 数组，我们添加了两个数据之后在这个数组中只有两个元素。下面的 SplFixedArray 类实例化出来的 fArr 则是固定数组。它在实例化的时候必须传递一个构造参数来指定数组长度。可以看到，fArr 输出的效果是固定有 5 个数据的，而且我们没有赋值的数据都会给一个默认的 NULL 值。是不是和 C 的数组一样一样的。

当然，固定数组就会有数组下标越界的问题了。

$fArr[6] = 'h'; // Fatal error: Uncaught RuntimeException: Index invalid or out of range

不过我们可以手动地修改数组的大小来改变数据的长度。

$fArr->setSize(7);$fArr[6] = 'h';var_dump($fArr->getSize()); // int(7)

现在，数组的长度就是 7 了，可以存放 7 条数据。它也可以直接从一个平凡数组转换过来，不过需要注意的是，转换数组必须是数字下标类型的数组，字符串键的 HashMap 数组是不可以的哦。

$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

剩下的就是和其它数据结构一样的一些操作方法函数了。

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

既然它是一种数组对象，那么迭代实在不消这么麻烦的，我们直接通过 for 和 foreach 就可以了。它和其它的数组结构一样，都实现了 Iterator 和 Countable 这两个接口，都是可以通过 for 和 foreach 来举行遍历的。

foreach($fArr as $f){ var_dump($f);}for($i=0;$iattach($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 对象存储映射类中添加数据。它的第二个参数可以指定一个数据内容，实在就可以看作是平凡数组中的值。

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) {// }

其它的遍历查询操作都是和其它数据结构的操作雷同的，这里就不多说了。其中比较特别的是 detach() 方法是删除数据的，getHash() 则是获取这个对象在存储集合中的 Hash 值的，这个值也可以看做是这个对象在这个对象映射集合中的下标，我们其它的针对对象的操作判断实在是都是在内部转换成这个数组下标来举行操作的。

总结

实在这一圈学习下来，突然发现有了 SPL 的这几个数据结构之后，我们在 PHP 下面还真不太需要关心什么数据结构方面的实现了，直接通用点就上个双向链表就完了，简单的就只是写算法了。好吧，学习照旧要扎实点，数据结构和算法真正要学习的实在是它内部的头脑和逻辑。当然，既然已经提供了，那么我们寻常的业务开发中照旧更建议直接使用 SPL 的这些数据结构来处理！

测试代码：

https://github.com/zhangyue0503/dev-blog/blob/master/php/2021/01/source/3.PHP的SPL扩展库（一）数据结构.php

参考文档：

https://www.php.net/manual/zh/spl.datastructures.php

欢迎光临创意电子 (https://wxcydz.cc/)