Data structures in PHP: Detailed explanation of DS extension

This article mainly brings you a commonplace talk about the data structure in PHP: DS extension. The editor thinks it is quite good, so I will share it with you now and give it as a reference for everyone. Let’s follow the editor to take a look, I hope it can help everyone.

This data structure extension can be installed and used only with PHP7 or above. The installation is relatively simple:

1. Run the command pecl install ds

2. Add extension=ds.so in php.ini

3. Restart PHP or reload the configuration

Collection Interface: Contains this library The basic interface for common functions of all data structures in . It guarantees that all structures are traversable, countable, and can be converted to json using json_encode().

Ds\Collection implements Traversable , Countable , JsonSerializable {
/* 方法 */
abstract public void clear ( void )
abstract public Ds\Collection copy ( void )
abstract public bool isEmpty ( void )
abstract public array toArray ( void )
}

Hashable Interface：which allows objects to be used as keys.

Ds\Hashable {
/* 方法 */
abstract public bool equals ( object $obj )
abstract public mixed hash ( void )
}

Sequence Interface：A Sequence is equivalent to a one-dimensional digital key array, with the exception of a few characteristics:

Values ​​will always be indexed as [0, 1, 2, …, size - 1].

Only allowed to access values ​​by index in the range [0, size - 1].

Use cases：

Wherever you would use an array as a list (not concerned with keys).

A more efficient alternative to SplDoublyLinkedList and SplFixedArray.

Vector Class: Vector is a sequence of values ​​in a continuous buffer that automatically grows and shrinks. It is the most efficient sequential structure, the index of the value maps directly to the index in the buffer, and the growth factor is not bound to a specific multiple or exponent. It has the following advantages and disadvantages:

Supports array syntax (square brackets).

Uses less overall memory than an array for the same number of values.

Automatically frees allocated memory when its size drops low enough.

Capacity does not have to be a power of 2.

get(), set(), push(), pop() are all O(1 ).

But shift(), unshift(), insert() and remove() are all O(n).

Ds\Vector::allocate — Allocates enough memory for a required capacity.
Ds\Vector::apply — Updates all values by applying a callback function to each value.
Ds\Vector::capacity — Returns the current capacity.
Ds\Vector::clear — Removes all values.
Ds\Vector::__construct — Creates a new instance.
Ds\Vector::contains — Determines if the vector contains given values.
Ds\Vector::copy — Returns a shallow copy of the vector.
Ds\Vector::count — Returns the number of values in the collection.
Ds\Vector::filter — Creates a new vector using a callable to determine which values to include.
Ds\Vector::find — Attempts to find a value's index.
Ds\Vector::first — Returns the first value in the vector.
Ds\Vector::get — Returns the value at a given index.
Ds\Vector::insert — Inserts values at a given index.
Ds\Vector::isEmpty — Returns whether the vector is empty
Ds\Vector::join — Joins all values together as a string.
Ds\Vector::jsonSerialize — Returns a representation that can be converted to JSON.
Ds\Vector::last — Returns the last value.
Ds\Vector::map — Returns the result of applying a callback to each value.
Ds\Vector::merge — Returns the result of adding all given values to the vector.
Ds\Vector::pop — Removes and returns the last value.
Ds\Vector::push — Adds values to the end of the vector.
Ds\Vector::reduce — Reduces the vector to a single value using a callback function.
Ds\Vector::remove — Removes and returns a value by index.
Ds\Vector::reverse — Reverses the vector in-place.
Ds\Vector::reversed — Returns a reversed copy.
Ds\Vector::rotate — Rotates the vector by a given number of rotations.
Ds\Vector::set — Updates a value at a given index.
Ds\Vector::shift — Removes and returns the first value.
Ds\Vector::slice — Returns a sub-vector of a given range.
Ds\Vector::sort — Sorts the vector in-place.
Ds\Vector::sorted — Returns a sorted copy.
Ds\Vector::sum — Returns the sum of all values in the vector.
Ds\Vector::toArray — Converts the vector to an array.
Ds\Vector::unshift — Adds values to the front of the vector.

Deque Class: The abbreviation of "double-ended queue", also used in Ds\Queue, has two pointers, head and tail. The pointers can “wrap around” the end of the buffer, which avoids the need to move other values ​​around to make room. This makes shift and unshift very fast — something a Ds\Vector can't compete with. It has the following advantages and disadvantages ：

Supports array syntax (square brackets).

Uses less overall memory than an array for the same number of values.

Automatically frees allocated memory when its size drops low enough.

get(), set(), push(), pop(), shift(), and unshift() are all O(1).

But Capacity must be a power of 2.insert() and remove() are O(n).

Map Class: A continuous collection of key-value pairs, almost the same as an array. Keys can be of any type but must be unique. If added to the map with the same key, the value will be replaced. It has the following advantages and disadvantages:

Keys and values ​​can be any type, including objects.

Supports array syntax (square brackets).

Insertion order is preserved.

Performance and memory efficiency is very similar to an array.

Automatically frees allocated memory when its size drops low enough.

Can't be converted to an array when objects are used as keys.

Pair Class：A pair is used by Ds\Map to pair keys with values.

Ds\Pair implements JsonSerializable {
/* 方法 */
public __construct ([ mixed $key [, mixed $value ]] )
}

Set Class: Unique value sequence. This implementation uses the same hash table as Ds\Map, where values ​​are used as keys and the mapped value is ignored. It has the following advantages and disadvantages:

Values ​​can be any type, including objects.

Supports array syntax (square brackets).

Insertion order is preserved.

Automatically frees allocated memory when its size drops low enough.

add(), remove( ) and contains() are all O(1).

But doesn't support push(), pop(), insert(), shift(), or unshift(). get() is O(n) if there are deleted values ​​in the buffer before the accessed index, O(1) otherwise.

Stack Class： "last in, first out" collection , allowing access and iteration only at the top of the structure.

Ds\Stack implements Ds\Collection {
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Stack copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

Queue Class: "first in, first out" collection, allowing access and iteration only on the front end of the structure.

Ds\Queue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Queue copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

PriorityQueue Class: A priority queue is very similar to a queue, but values ​​are pushed into the queue at a specified priority, with the highest priority The value of is always at the front of the queue, and the "first in, first out" order of elements with the same priority is still retained. Iteration on a PriorityQueue is destructive and is equivalent to continuous pop operations until the queue is empty. Implemented using a max heap.

Ds\PriorityQueue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\PriorityQueue copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ( mixed $value , int $priority )
public array toArray ( void )
}

Related recommendations:

PHP implements stack data structure and bracket matching

PHP stack data structure and bracket matching algorithm example explanation

php data structure sequential linked list and linked linear table example

The above is the detailed content of Data structures in PHP: Detailed explanation of DS extension. For more information, please follow other related articles on the PHP Chinese website!