Does PHP have built-in data structures?
PhpData StructuresPhp Problem Overview
I'm looking at the PHP Manual, and I'm not seeing a section on data structures that most languages have, such as lists and sets. Am I just blind or does PHP not have anything like this built in?
Php Solutions
Solution 1 - Php
The only native data structure in PHP is array. Fortunately, arrays are quite flexible and can be used as hash tables as well.
However, there is SPL which is sort of a clone of C++ STL.
Solution 2 - Php
PHP offers data structures through the Standard PHP Library (SPL) basic extension, which is available and compiled by default in PHP 5.0.0.
The data structures offered are available with PHP 5 >= 5.3.0, and includes:
###Doubly Linked Lists### A Doubly Linked List (DLL) is a list of nodes linked in both directions to each others. Iterator’s operations, access to both ends, addition or removal of nodes have a cost of O(1) when the underlying structure is a DLL. It hence provides a decent implementation for stacks and queues.
###Heaps### Heaps are tree-like structures that follow the heap-property: each node is greater than or equal to its children, when compared using the implemented compare method which is global to the heap.
###Arrays### Arrays are structures that store the data in a continuous way, accessible via indexes. Don’t confuse them with PHP arrays: PHP arrays are in fact implemented as ordered hashtables.
###Map### A map is a datastructure holding key-value pairs. PHP arrays can be seen as maps from integers/strings to values. SPL provides a map from objects to data. This map can also be used as an object set.
Solution 3 - Php
PHP 7 introduced an extension called ds providing specialized data structures as an alternative to the array.
The ds,
- uses the
Ds\namespace. - has 3 interfaces namely,
Collection,SequenceandHashable - has 8 classes namely,
Vector,Deque,Queue,PriorityQueue,Map,Set,Stack, andPair
For more information checkout the Manual and also This blog post has some awesome information including benchmarks.
Solution 4 - Php
The associative array can be used for most basic data structures hashtable, queue, stack. But if you want something like a tree or heap I don't think they exist by default but I'm sure there are free libraries anywhere.
To have an array emulate a stack use array_push() to add and array_pop() to take off
To have an array emulate a queue use array_push() to enqueue and array_shift() to dequeue
An associative array is a hash by default. In PHP they are allowed to have strings as indexes so this works as expected:
$array['key'] = 'value';
Finally, you can kind of emulate a binary tree with an array with the potential to have wasted space. Its useful if you know you're going to have a small tree. Using a linear array, you say for any index (i) you put its left child at index (2i+1) and right child at index (2i+2).
All of these methods are covered nicely in this article on how to make JavaScript arrays emulate higher level data structures.
Solution 5 - Php
PHP has arrays, which are actually associative arrays and can also be used as sets. Like many interpreted languages, PHP offers all this under one hood instead of providing different explicit data types.
E.g.
$lst = array(1, 2, 3);
$hsh = array(1 => "This", 2 => "is a", 3 => "test");
Also, take a look in the manual.
Solution 6 - Php
PHP's array doubles as both a list and a dictionary.
$myArray = array("Apples", "Oranges", "Pears");
$myScalar = $myArray[0] // == "Apples"
Or to use it as an associative array:
$myArray = array("a"=>"Apples", "b"=>"Oranges", "c"=>"Pears");
$myScalar = $myArray["a"] // == "Apples"
Solution 7 - Php
I think you might want to be a bit more specific, when you say data structures my mind goes in a few directions...
Arrays - They are certainly well documented and available in. (http://us.php.net/manual/en/book.array.php)
SQL Data - Depends on the database you are using, but most are available. (http://us.php.net/manual/en/book.mysql.php)
OOP - Depending on the version objects can be designed and implemented. (http://us.php.net/manual/en/language.oop.php) I had to search for OOP to find this on the php site.
Solution 8 - Php
Of course PHP has data structures. The array in php is incredibly flexible. Some examples:
$foo = array(
'bar' => array(1,'two',3),
'baz' => explode(" ", "Some nice words")
);
Then you have an absolute plethora of array functions available to map/filter/walk/etc the structures, or convert, flip, reverse, etc.
Solution 9 - Php
You can always create your own if you don't feel PHP includes a specific type of data structure. For example, here is a simple Set data structure backed by an Array.
class ArraySet
{
/** Elements in this set */
private $elements;
/** the number of elements in this set */
private $size = 0;
/**
* Constructs this set.
*/
public function ArraySet() {
$this->elements = array();
}
/**
* Adds the specified element to this set if
* it is not already present.
*
* @param any $element
*
* @returns true if the specified element was
* added to this set.
*/
public function add($element) {
if (! in_array($element, $this->elements)) {
$this->elements[] = $element;
$this->size++;
return true;
}
return false;
}
/**
* Adds all of the elements in the specified
* collection to this set if they're not already present.
*
* @param array $collection
*
* @returns true if any of the elements in the
* specified collection where added to this set.
*/
public function addAll($collection) {
$changed = false;
foreach ($collection as $element) {
if ($this->add($element)) {
$changed = true;
}
}
return $changed;
}
/**
* Removes all the elements from this set.
*/
public function clear() {
$this->elements = array();
$this->size = 0;
}
/**
* Checks if this set contains the specified element.
*
* @param any $element
*
* @returns true if this set contains the specified
* element.
*/
public function contains($element) {
return in_array($element, $this->elements);
}
/**
* Checks if this set contains all the specified
* element.
*
* @param array $collection
*
* @returns true if this set contains all the specified
* element.
*/
public function containsAll($collection) {
foreach ($collection as $element) {
if (! in_array($element, $this->elements)) {
return false;
}
}
return true;
}
/**
* Checks if this set contains elements.
*
* @returns true if this set contains no elements.
*/
public function isEmpty() {
return count($this->elements) <= 0;
}
/**
* Get's an iterator over the elements in this set.
*
* @returns an iterator over the elements in this set.
*/
public function iterator() {
return new SimpleIterator($this->elements);
}
/**
* Removes the specified element from this set.
*
* @param any $element
*
* @returns true if the specified element is removed.
*/
public function remove($element) {
if (! in_array($element, $this->elements)) return false;
foreach ($this->elements as $k => $v) {
if ($element == $v) {
unset($this->elements[$k]);
$this->size--;
return true;
}
}
}
/**
* Removes all the specified elements from this set.
*
* @param array $collection
*
* @returns true if all the specified elemensts
* are removed from this set.
*/
public function removeAll($collection) {
$changed = false;
foreach ($collection as $element) {
if ($this->remove($element)) {
$changed = true;
}
}
return $changed;
}
/**
* Retains the elements in this set that are
* in the specified collection. If the specified
* collection is also a set, this method effectively
* modifies this set into the intersection of
* this set and the specified collection.
*
* @param array $collection
*
* @returns true if this set changed as a result
* of the specified collection.
*/
public function retainAll($collection) {
$changed = false;
foreach ($this->elements as $k => $v) {
if (! in_array($v, $collection)) {
unset($this->elements[$k]);
$this->size--;
$changed = true;
}
}
return $changed;
}
/**
* Returns the number of elements in this set.
*
* @returns the number of elements in this set.
*/
public function size() {
return $this->size;
}
/**
* Returns an array that contains all the
* elements in this set.
*
* @returns an array that contains all the
* elements in this set.
*/
public function toArray() {
$elements = $this->elements;
return $elements;
}
}
Solution 10 - Php
PHP can also have an array of arrays which is called a "multidimensional array" or "matrix". You can have 2-dimensional arrays, 3-dimensional arrays, etc.