参考文档#SPL官网

SPL
1
SPL是用于解决典型问题(standard problems)的一组接口与类的集合
  • PHP 作为一门web快速开发语言,我认为重点在于数组
  • 上层接口提供给应用层快速数据的转化处理能力(各种Array函数)
  • 底层实现在于数据结构定义与组织(堆、栈、链表、迭代器等)
  • 核心在于各种算法(线性存储、hash、map)实现
  • SPL給php增添的魅力毫不逊于其他语言(php是世界最好的语言)
SplDoublyLinkedList
  • 双链表 (双向链表)
  • 存储结构,是线性的
  • 每个节点不仅保存自己数据也保留前后节点地址(首尾节点除外)
  • 两端的访问、节点的添加或删除 算法时间复杂度O(1)
  • 栈和队列提供了一个合适的实现(SplStack / SplQueue)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128

    SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
    /*
    ArrayAccess 数据访问接口 简单理解就是实现它的对象可以像数组一样操作

    Countable 可计数的接口 简单理解就是实现它的对象可以被计数总数或长度

    Iterator 继承至Traversable 抽象类 实现它的就等于可用于foreach遍历 (一般对象不能这样玩)

    SplDoublyLinkedList 就是实现咯上面所有接口的类

    */

    /* 方法 */
    public __construct ( void )
    /*
    新增一个指定位置(索引)的元素
    */
    public void add ( mixed $index , mixed $newval )
    /*
    Peeks at the node from the beginning of the doubly linked list
    从链表开始的第一个节点,或者顶部节点
    */
    public mixed bottom ( void )
    /*
    计算当前链表的元素总个数
    */
    public int count ( void )
    /*
    返回当前节点
    */
    public mixed current ( void )
    /*
    返回链表迭代模式 0 1 2 见setIteratorMode
    */
    public int getIteratorMode ( void )
    /*
    验证链表是否为空
    */
    public bool isEmpty ( void )
    /*
    计算当前节点的索引位置
    */
    public mixed key ( void )
    /*
    向后移动一个节点 无参数无返回 配合 valid 使用
    */
    public void next ( void )
    /*
    返回当前索引位置节点是否存在
    */
    public bool offsetExists ( mixed $index )
    /*
    返回当指定索引对应的值 不主动验证有效性 可能引发超长范围异常
    */
    public mixed offsetGet ( mixed $index )
    /*
    简单理解就是更新By key
    */
    public void offsetSet ( mixed $index , mixed $newval )

    /*
    简单理就是 删除 By key
    */
    public void offsetUnset ( mixed $index )
    /*
    简单理就是 移除链表尾部节点 并返回链表
    */
    public mixed pop ( void )
    /*
    简单理就是 移动到上一节点位置 无参数无返回值
    */
    public void prev ( void )
    /*
    简单理就是 在链表尾部新增节点 不改变其他节点索引
    */
    public void push ( mixed $value )
    /*
    重置索引位置 或者指针到链表顶部
    */
    public void rewind ( void )
    /*
    序列化当前链表对象 返回字符串 同原生函数 serialize unserialize
    */
    public string serialize ( void )
    /*
    IT_MODE_LIFO => int(2)
    IT_MODE_FIFO => int(0)
    IT_MODE_DELETE => int(1)
    IT_MODE_KEEP => int(0)

    上面是两组迭代模式

    按迭代方向
    SplDoublyLinkedList::IT_MODE_LIFO (Stack style)
    SplDoublyLinkedList::IT_MODE_FIFO (Queue style)

    按迭代行为
    SplDoublyLinkedList::IT_MODE_DELETE (Elements are deleted by the iterator)
    SplDoublyLinkedList::IT_MODE_KEEP (Elements are traversed by the iterator)

    默认迭代模式 :SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP
    */
    public void setIteratorMode ( int $mode )
    /*
    移除链表中的开始节点 同bottom 但是这个是执行删除 并重排索引位置
    */
    public mixed shift ( void )

    /*
    Peeks at the node from the end of the doubly linked list
    返回链表底部节点
    */
    public mixed top ( void )
    /*
    按照链表类型反序列化字符串,无返回值
    */
    public void unserialize ( string $serialized )

    /*
    在链表顶部插入节点 并重新建立其他节点索引位置
    */
    public void unshift ( mixed $value )
    /*
    主动约束是否越界或元素个数溢出的节点有效性
    */
    public bool valid ( void )
    }
SplStack
  • 继承至双向链表
  • 特殊的线性表
  • 实现栈的功能(不绝对)
  • LIFO 先进后出 首先是压栈(入队列) 然后出栈(出队列) 就像容器一样
SplQueue
  • 继承至双向链表
  • 特殊的线性表
  • 实现队列功能 生产(入队列)->消费(出队列)
  • FIFO 先进先出
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

    // 两个重要函数

    /*
    出队列
    SplQueue::dequeue() is an alias of SplDoublyLinkedList::shift()
    */

    mixed dequeue ( void )
    /*
    入队列 底层实现是push
    */
    void enqueue ( mixed $value )
SplHeap
  • 1
    2
    3
    4
    5
    6
    n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

    堆中某个节点的值总是不大于或不小于其父节点的值
    根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
    常见的堆有二叉堆、斐波那契堆等
  • 遵循堆属性的树状结构

  • 每个节点都大于或等于其子级, 使用对堆全局的已实现的比较方法进行比较
  • 常用于堆排序
  • 算法结构上 堆总是一个完全二叉树
  • 插入结点、删除普通元素和删除最小元素 平均时间复杂度 O(Log n)
  • 抽象类 要使用必须继承并实现其方法 实现类【 SplMaxHeap SplMinHeap 】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
abstract SplHeap implements Iterator , Countable {
/* 方法 */
public __construct ( void )
/*
比较元素以便在筛选时正确地放置在堆中
返回 整数 0 负数
*/
abstract protected int compare ( mixed $value1 , mixed $value2 )
// 返回堆节点数
public int count ( void )
// 返回迭代指针指向的节点
public mixed current ( void )
// 从堆顶部提取一个节点并重建堆
public mixed extract ( void )
// 向堆中添加一个节点并重建堆
public void insert ( mixed $value )
// Tells if the heap is in a corrupted state
// 堆是否有错误或损坏 返回bool
public bool isCorrupted ( void )
// 判断是否为空堆
public bool isEmpty ( void )
// 返回当前堆指针指向的节点的键
public mixed key ( void )
// 迭代指针指向下一节点
public void next ( void )
// 恢复堆
public void recoverFromCorruption ( void )
// 重置迭代指针
public void rewind ( void )
// 返回堆的顶部节点
public mixed top ( void )
public bool valid ( void )
}

Heap Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

$heap = new SplMaxHeap();
$heap->insert(1);
$heap->insert(10);
$heap->insert(100);
$heap->insert(31);
$heap->insert(41);


echo "SplMaxHeap".PHP_EOL;
print_r($heap);

while ($heap->valid()){
print_r($heap->current());
echo PHP_EOL;

$heap->next();
}


$heap = new SplMinHeap();
$heap->insert(1);
$heap->insert(10);
$heap->insert(100);
$heap->insert(31);
$heap->insert(41);
echo "SplMinHeap".PHP_EOL;
print_r($heap);
while ($heap->valid()){
print_r($heap->current());
echo PHP_EOL;

$heap->next();
}

/* 输出 */

SplMaxHeap
SplMaxHeap Object
(
[flags:SplHeap:private] => 0
[isCorrupted:SplHeap:private] =>
[heap:SplHeap:private] => Array
(
[0] => 100
[1] => 41
[2] => 10
[3] => 1
[4] => 31
)

)
100
41
31
10
1
SplMinHeap
SplMinHeap Object
(
[flags:SplHeap:private] => 0
[isCorrupted:SplHeap:private] =>
[heap:SplHeap:private] => Array
(
[0] => 1
[1] => 10
[2] => 100
[3] => 31
[4] => 41
)

)
1
10
31
41
100

SplPriorityQueue

  • 优先级队列
  • FIFO 并且提供权重级别插队机制
  • 区别于继承双向链表的 SplQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

SplPriorityQueue implements Iterator , Countable {
/* 方法 */
public __construct ( void )
public int compare ( mixed $priority1 , mixed $priority2 )
public int count ( void )
public mixed current ( void )
public mixed extract ( void )
public int getExtractFlags ( void )
public void insert ( mixed $value , mixed $priority )
public bool isCorrupted ( void )
public bool isEmpty ( void )
public mixed key ( void )
public void next ( void )
public void recoverFromCorruption ( void )
public void rewind ( void )
/**
Defines what is extracted by SplPriorityQueue::current(), SplPriorityQueue::top() and SplPriorityQueue::extract().

SplPriorityQueue::EXTR_DATA (0x00000001): Extract the data 仅抽取值比较
SplPriorityQueue::EXTR_PRIORITY (0x00000002): Extract the priority 仅抽取优先级
SplPriorityQueue::EXTR_BOTH (0x00000003): Extract an array containing both 数组包含值和优先级
The default mode is SplPriorityQueue::EXTR_DATA.
*/
public void setExtractFlags ( int $flags )
public mixed top ( void )
public bool valid ( void )
}

SplPriorityQueue DEMO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77



$queue = new SplPriorityQueue();
$queue->insert("A",100);
$queue->insert("D",200);
$queue->insert("C",10);
$queue->insert("B",50);
print_r($queue->top());
echo PHP_EOL;

while ($queue->valid()){
print_r($queue->current());
echo PHP_EOL;
$queue->next();
}
/**
默认排序
D

D
A
B
C


*/

/*
// 抽取优先级排序
$queue->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
while ($queue->valid()){
print_r($queue->current());
echo PHP_EOL;
$queue->next();
}*/
/*
200
100
50
10

*/

// 抽取优先级和数据
$queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
while ($queue->valid()){
print_r($queue->current());
echo PHP_EOL;
$queue->next();
}
/*
Array
(
[data] => D
[priority] => 200
)

Array
(
[data] => A
[priority] => 100
)

Array
(
[data] => B
[priority] => 50
)

Array
(
[data] => C
[priority] => 10
)

*/