SymfonyCon Disneyland Paris 2022

Introduction

Efficient data structures for PHP 7, provided as an alternative to the tableau.

See » this blog post for benchmarks, discussion and frequently asked questions.

add a note

User Contributed Notes 1 note

up
1
immemosol
4 months ago
A summary of the namespace.

Known big O notations

ClassName     | add  | contains | get       | hasKey | insert | pop  | push | put  | remove | set  | shift | unshift |
Vector        | _    | ?        | O(1)      | _      | O(n)   | O(1) | O(1) | _    | O(n)   | O(1) | O(n)  | O(n)    |
Stack         | _    | _        | _         | _      | _      | ?    | _    | _    | _      | _    | _     | _       |
Set           | O(1) | O(1)     | O(n OR 1) | _      | _      | _    | _    | _    | O(1)   | _    | _     | _       |
Queue         | _    | _        | _         | _      | _      | ?    | ?    | _    | _      | _    | _     | _       |
PriorityQueue | _    | _        | _         | _      | _      | ?    | ?    | _    | _      | _    | _     | _       |
Map           | _    | _        | O(1)      | O(1)   | _      | _    | _    | O(1) | O(1)   | _    | _     | _       |
Deque         | _    | ?        | O(1)      | ?      | ?      | O(1) | O(1) | _    | ?      | O(1) | O(1)  | O(1)    |

? = method is available and big O is unknown.
_ = method is unavailable, although comparable behavior could be available
      For example: `$object[] = '';` as an alternative to `$object->push('');`.

Except for PriorityQueue, all other classes
(Deque, Map, Queue, Set, Stack, Vector) implement ArrayAccess,

Main:
- interface Sequence: Collection + ArrayAccess
- interface Collection: Traversable, Countable, JsonSerializable
- Vector: Sequential structure, low memory usage
- Stack: Destructive Iteration; LIFO (Last In, First Out)
    note: can only access the item at the top of the stack
- Set: Hashable, Unique Values
- Queue: Destructive Iteration; FIFO (First In, First Out)
    note: can only access the item at the front of the stack
- PriorityQueue: Destructive Iteration; FIFO + Priority
    Like Queue but priority determines order first, FIFO when equal priority
- Map: Hashable, Key Value Sequence (like array in comparable context)
    memory usage: like array, clears memory more often
    note: can use objects as keys, but that inhibits array conversion
- Deque: Double Ended Queue, low memory usage
    note: buffer capacity must be ^2 (a power of 2)

Supporting:
- interface Hashable: allows objects to be used as keys (`->hash()` & `->equals()`, falls back to `spl_object_hash()`)
- class Pair: JsonSerializable, Key Value Pair, used by Map
- and some more.
To Top