A vector is a linear data structure where values are stored sequentially and also the size grows and shrinks automatically. Vector is one of the most efficient linear data structures as the value's index is mapped directly with the index of the buffer and allows faster access. DS vector class allows us to use the PHP array syntax for operations, but internally, it has less memory consumption than PHP array. It has constant time operations for push, pop, get, and set. Here is an example of vector:

$vector = new DsVector(["a", "b", "c"]); 
echo $vector->get(1)."
"; 
$vector[1] = "d"; 
echo $vector->get(1)."
"; 
$vector->push('f'); 
echo "Size of vector: ".$vector->count(); 

As we can see from the preceding code, we can define a vector using the PHP array syntax and also get or set values using array syntax. One difference is that we cannot add a new index using PHP array syntax. For that, we have to use the push method of the vector class. Trying to set or get an index that is not there will cause OutofRangeException to be thrown during runtime. Here is the output of the preceding code:

b
d
Size of vector: 4

Map

A map is a sequential collection of key-value pairs. A map is similar to an array, and the key can be a string, integer, and so on, but the key has to be unique. In DS map class, the key can be of any type, including an object. It allows PHP array syntax for operations and also preserves the insertion order. The performance and memory efficiency is also similar to the PHP array. It also automatically frees memory when the size drops to low. If we consider the following performance chart, we can see that map implementation in DS library is much faster than PHP array when we are removing items from a big array:

Set

A set is also a sequence, but a set can only contain unique values. A set can store any value, including object, and also support array syntax. It preserves the insertion order and also automatically frees memory when the size drops to low. We can achieve add, remove, and contain operations in constant time. However, this set class does not support push, pop, shift, insert, and unshift functions. The set class has some very useful set operation functions built in, such as diff, intersect, union, and so on. Here is an example of the set operation:

$set = new DsSet(); 
$set->add(1); 
$set->add(1); 
$set->add("test"); 
$set->add(3); 
echo $set->get(1);

In the preceding example code, there will be only one entry of 1 as set cannot have duplicate values. Also, when we are getting the value of 1, this indicates the value at index 1. So, the output will be test for the preceding example. One question might arise here that why not we use array_unique here to build a set. The following comparison chart might be the answer we are looking for:

As we can see from the preceding chart, as the array size grows, array unique function will take more time to compute compared to our set class in the DS library. Also, the set class takes lesser memory compared to PHP array as the size grows:

Stack and queue

The DS library also has implementations of stack and queue data structures. DSStack uses DSVector internally, and DSQueue uses DSDeque internally. Both stack and queue implementation have similar performance compared to SPL implementation of stack and queue. The following chart shows this:

Deque

The deque (pronounced as deck), or the double ended queue, is used for the DSQueue implementation internally. The deque implementation in this package is very efficient in memory usage and also performs get, set, push, pop, shift, and unshift operations in constant time of O(1). However, one of the disadvantages of DSDeque is the insert or remove operation, which has O(n) complexity. Here is a performance comparison between DSDeque and SPL doubly linked list:

Priority queue

You have already learned that priority queues are important for many algorithms. Having an efficient priority queue is very important for us as well. So far, we have seen that we can implement from our own using heap or use the SPL priority queue for our solutions. However, the DSPriorityQueue is more than twice as fast as SplPriorityQueue and uses only five percent of its memory. This makes DSPriorityQueue 20 times more memory efficient compared to SplPriorityQueue. The following chart shows the comparison:

From our discussion in the last few sections, we can conclude that the DS extension is really efficient for data structures and far better compared to SPL for similar implementations. Though the benchmark can vary a little from platform to platform and internal configurations, it shows that the new DS extension is promising and might be very helpful for developers. One thing to remember is that the library does not have built-in heap or tree data structure yet, so we cannot have a built-in hierarchical data structure from this library.