Sets

suggest change

A set is an unordered collection of distinct, unique values. Unlike languages such as Python or JavaScript, PHP does not offer a built-in Set keyword. However, PHP developers commonly represent sets using associative array keys, built-in array set functions, or the Ds\Set class from the PECL Data Structures extension.

Simulating Sets with Associative Array Keys (Idiomatic & O(1))

The standard and most efficient idiom in native PHP uses array keys. Because PHP associative array keys are stored in an internal hash table and must be unique, lookups and insertions run in $O(1)$ time:

class StringSet {
    private array $elements = [];

    public function add(string $value): void {
        $this->elements[$value] = true;
    }

    public function remove(string $value): void {
        unset($this->elements[$value]);
    }

    public function contains(string $value): bool {
        return isset($this->elements[$value]);
    }

    public function toArray(): array {
        return array_keys($this->elements);
    }

    public function count(): int {
        return count($this->elements);
    }
}

// Usage:
$tags = new StringSet();
$tags->add('php');
$tags->add('programming');
$tags->add('php'); // Ignored, already exists

var_dump($tags->contains('php'));    // bool(true)
var_dump($tags->contains('python')); // bool(false)
var_dump($tags->toArray());          // ['php', 'programming']

[!NOTE] When using array keys, keys are restricted to integers and strings. PHP will automatically cast integer-like numeric strings (such as "42") to integer 42.

Set Operations with Array Functions

PHP provides several built-in functions designed for set operations:

1. Union

Combine two arrays and filter out duplicate elements:

$setA = ['apple', 'banana', 'cherry'];
$setB = ['banana', 'date', 'apple'];

// Union: items present in A, B, or both
$union = array_values(array_unique(array_merge($setA, $setB)));
// ['apple', 'banana', 'cherry', 'date']

If your sets are represented by array keys, the array union operator (+) is much faster:

$setKeyA = ['apple' => true, 'banana' => true];
$setKeyB = ['banana' => true, 'cherry' => true];

$unionKeys = $setKeyA + $setKeyB; // keys: 'apple', 'banana', 'cherry'

2. Intersection

Find elements common to both sets:

$setA = ['apple', 'banana', 'cherry'];
$setB = ['banana', 'date', 'fig'];

// Value-based intersection:
$intersection = array_values(array_intersect($setA, $setB));
// ['banana']

// Key-based intersection (much faster):
$interKeys = array_intersect_key($setKeyA, $setKeyB);
// ['banana' => true]

3. Difference (Relative Complement)

Find elements in set A that are not in set B:

$setA = ['apple', 'banana', 'cherry'];
$setB = ['banana', 'date'];

// Difference: elements in A but not in B
$diff = array_values(array_diff($setA, $setB));
// ['apple', 'cherry']

// Key-based difference:
$diffKeys = array_diff_key($setKeyA, $setKeyB);
// ['apple' => true]

Using the Ds\Set Extension

For projects with the ext-ds PECL extension enabled, Ds\Set provides a native, object-oriented set that supports any hashable value, including objects:

use Ds\Set;

$setA = new Set([1, 2, 3, 4]);
$setB = new Set([3, 4, 5, 6]);

// Set operations
$union = $setA->union($setB);               // Set {1, 2, 3, 4, 5, 6}
$intersect = $setA->intersect($setB);       // Set {3, 4}
$difference = $setA->diff($setB);           // Set {1, 2}
$symmetric = $setA->xor($setB);             // Set {1, 2, 5, 6}

var_dump($setA->contains(2)); // bool(true)

Summary Comparison

Approach Membership Test Time Key/Element Constraints Requires Extension
in_array($val, $arr) $O(N)$ (slow) Any value None
Array keys (isset($arr[$val])) $O(1)$ (fast) String / Int only None
Ds\Set $O(1)$ (fast) Objects, Strings, Ints, etc. ext-ds PECL

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents