Guía de Estructuras de Datos Nativas para PHP |

¿Qué es `ext-ds`?

ext-ds es una extensión de PHP que proporciona estructuras de datos nativas como alternativa eficiente al array genérico de PHP. Están implementadas en C, por lo que ofrecen mejor rendimiento de memoria y velocidad en operaciones específicas.

La versión 2 es un rediseño mayor: pasó de 11 tipos + 3 interfaces a 5 tipos + 1 interfaz, simplificando enormemente la API.

Instalación

# Debian/Ubuntu (puede variar según la versión de PHP)
sudo apt install php8.5-ds

# Vía PECL
pecl install ds

# Habilitar en php.ini
extension=ds.so        # Linux/Mac
extension=php_ds.dll   # Windows

# Polyfill para IDE y entornos sin la extensión
composer require php-ds/php-ds

Tipos disponibles

`Ds\Seq` — Secuencia unificada

Una secuencia ordenada e indexada de valores.

Los índices siempre son [0, 1, 2, ..., n-1].
Soporta sintaxis de array ($seq[0]).
Buffer contiguo en memoria → cache-friendly.

$seq = new Ds\Seq([10, 20, 30]);
// o bien:
$seq = \Ds\seq([10, 20, 30]);

Métodos de `Ds\Seq`

// ── Agregar / eliminar ──────────────────────────────────────────────────────
$seq->push(mixed ...$values): void        // Agrega al final
$seq->pop(): mixed                        // Elimina y retorna el último
$seq->unshift(mixed ...$values): void     // Agrega al inicio
$seq->shift(): mixed                      // Elimina y retorna el primero
$seq->insert(int $index, mixed ...$values): void  // Inserta en posición
$seq->remove(int $index): mixed           // Elimina por índice

// ── Acceso ──────────────────────────────────────────────────────────────────
$seq->get(int $index): mixed              // Obtiene valor por índice
$seq->set(int $index, mixed $value): void // Actualiza valor por índice
$seq->first(): mixed                      // Primer elemento
$seq->last(): mixed                       // Último elemento
$seq[$index]                              // Sintaxis de array

// ── Búsqueda ────────────────────────────────────────────────────────────────
$seq->contains(mixed ...$values): bool    // Verifica existencia
$seq->find(mixed $value): int|false       // Retorna índice o false

// ── Transformación ──────────────────────────────────────────────────────────
$seq->filter(?callable $fn): Ds\Seq       // Filtra valores
$seq->map(callable $fn): Ds\Seq           // Transforma valores (nuevo Seq)
$seq->apply(callable $fn): void           // Transforma valores (in-place)
$seq->reduce(callable $fn, mixed $init = null): mixed
$seq->merge(iterable $values): Ds\Seq     // Une con otro iterable (nuevo Seq)

// ── Ordenamiento ────────────────────────────────────────────────────────────
$seq->sort(?callable $comparator): void   // Ordena in-place
$seq->sorted(?callable $comparator): Ds\Seq // Retorna copia ordenada
$seq->reverse(): void                     // Invierte in-place
$seq->reversed(): Ds\Seq                  // Retorna copia invertida
$seq->rotate(int $rotations): void        // Rota elementos

// ── Utilidades ──────────────────────────────────────────────────────────────
$seq->count(): int
$seq->isEmpty(): bool
$seq->clear(): void
$seq->slice(int $index, ?int $length): Ds\Seq
$seq->join(string $glue = ''): string
$seq->sum(): int|float
$seq->capacity(): int
$seq->allocate(int $capacity): void
$seq->toArray(): array
$seq->copy(): Ds\Seq                      // Copia superficial

Ejemplos de uso

// Como lista simple
$frutas = \Ds\seq(['manzana', 'pera', 'uva']);
$frutas->push('mango');
echo $frutas->first();   // manzana
echo $frutas->pop();     // mango

// Como Stack (LIFO)
$pila = new Ds\Seq();
$pila->push('primero');
$pila->push('segundo');
echo $pila->pop();       // segundo

// Como Queue (FIFO)
$cola = new Ds\Seq();
$cola->push('A');
$cola->push('B');
echo $cola->shift();     // A

// Transformar y filtrar
$nums = \Ds\seq([1, 2, 3, 4, 5]);
$pares = $nums->filter(fn($n) => $n % 2 === 0);   // Seq{2, 4}
$dobles = $nums->map(fn($n) => $n * 2);            // Seq{2, 4, 6, 8, 10}
$suma = $nums->reduce(fn($c, $n) => $c + $n, 0);  // 15

// Iterar de forma segura (COW)
foreach ($seq as $valor) {
    $seq->push(999);  // Seguro — itera sobre la copia original
}

`Ds\Map` — Mapa ordenado

Colección ordenada de pares clave-valor. Las claves pueden ser de cualquier tipo, incluyendo objetos.

Mantiene el orden de inserción.
Las claves son únicas; asignar la misma clave reemplaza el valor.
Soporta sintaxis de array ($map['clave']).

$map = new Ds\Map(['a' => 1, 'b' => 2]);
// o bien:
$map = \Ds\map(['a' => 1, 'b' => 2]);

Métodos de `Ds\Map`

// ── Escritura ────────────────────────────────────────────────────────────────
$map->put(mixed $key, mixed $value): void    // Inserta o actualiza
$map->putAll(iterable $pairs): void          // Inserta múltiples pares
$map->remove(mixed $key, mixed $default = null): mixed  // Elimina por clave

// ── Lectura ──────────────────────────────────────────────────────────────────
$map->get(mixed $key, mixed $default = null): mixed
$map->hasKey(mixed $key): bool
$map->hasValue(mixed $value): bool
$map->keys(): Ds\Set                          // Retorna Ds\Set con las claves
$map->values(): Ds\Seq                        // Retorna Ds\Seq con los valores
$map->pairs(): Ds\Seq                         // Retorna Ds\Seq de Ds\Pair
$map->first(): Ds\Pair                        // Primer par
$map->last(): Ds\Pair                         // Último par
$map->get(mixed $key): mixed
$map[$key]                                    // Sintaxis de array

// ── Transformación ───────────────────────────────────────────────────────────
$map->filter(callable $fn): Ds\Map            // Filtra pares (clave, valor)
$map->map(callable $fn): Ds\Map               // Transforma valores
$map->reduce(callable $fn, mixed $init): mixed
$map->merge(iterable $values): Ds\Map         // Une mapas (nuevo Map)

// ── Operaciones de conjuntos ─────────────────────────────────────────────────
$map->intersect(Ds\Map $map): Ds\Map          // Intersección por claves
$map->diff(Ds\Map $map): Ds\Map               // Diferencia por claves
$map->union(Ds\Map $map): Ds\Map              // Unión (las del otro Map ganan)
$map->xor(Ds\Map $map): Ds\Map                // Claves en uno u otro, no en ambos

// ── Ordenamiento ─────────────────────────────────────────────────────────────
$map->sort(?callable $comparator): void       // Ordena por valor in-place
$map->sorted(?callable $comparator): Ds\Map
$map->ksort(?callable $comparator): void      // Ordena por clave in-place
$map->ksorted(?callable $comparator): Ds\Map
$map->reverse(): void
$map->reversed(): Ds\Map

// ── Utilidades ───────────────────────────────────────────────────────────────
$map->count(): int
$map->isEmpty(): bool
$map->clear(): void
$map->slice(int $index, ?int $length): Ds\Map
$map->capacity(): int
$map->allocate(int $capacity): void
$map->toArray(): array
$map->copy(): Ds\Map

Ejemplos de uso

$config = \Ds\map(['debug' => true, 'version' => '2.0']);
$config->put('env', 'production');
echo $config->get('version');          // 2.0
echo $config->get('timeout', 30);     // 30 (valor por defecto)
var_dump($config->hasKey('debug'));    // true

// Clave de tipo objeto
$user = new User(1, 'Ana');
$mapa = new Ds\Map();
$mapa->put($user, ['rol' => 'admin']);

// Iterar
foreach ($config as $clave => $valor) {
    echo "$clave: $valor\n";
}

// Operaciones de conjuntos
$m1 = \Ds\map(['a' => 1, 'b' => 2]);
$m2 = \Ds\map(['b' => 99, 'c' => 3]);
$interseccion = $m1->intersect($m2);  // Map{'b' => 2}
$union        = $m1->union($m2);      // Map{'a' => 1, 'b' => 99, 'c' => 3}
$diferencia   = $m1->diff($m2);       // Map{'a' => 1}

`Ds\Set` — Conjunto ordenado de valores únicos

Colección de valores sin duplicados. Los valores duplicados son ignorados silenciosamente.

keys() de Ds\Map retorna un Ds\Set.
Soporta operaciones matemáticas de conjuntos.

$set = new Ds\Set([1, 2, 3, 2, 1]);  // Set{1, 2, 3}
// o bien:
$set = \Ds\set([1, 2, 3]);

Métodos de `Ds\Set`

// ── Escritura ────────────────────────────────────────────────────────────────
$set->add(mixed ...$values): void             // Agrega valores (ignora duplicados)
$set->remove(mixed ...$values): void          // Elimina valores

// ── Lectura ──────────────────────────────────────────────────────────────────
$set->contains(mixed ...$values): bool        // Verifica existencia
$set->get(int $index): mixed                  // Obtiene por posición
$set->first(): mixed
$set->last(): mixed

// ── Operaciones de conjuntos ─────────────────────────────────────────────────
$set->union(Ds\Set $set): Ds\Set              // A ∪ B
$set->intersect(Ds\Set $set): Ds\Set          // A ∩ B
$set->diff(Ds\Set $set): Ds\Set               // A - B (diferencia)
$set->xor(Ds\Set $set): Ds\Set                // A △ B (diferencia simétrica)
$set->merge(iterable $values): Ds\Set

// ── Transformación ───────────────────────────────────────────────────────────
$set->filter(?callable $fn): Ds\Set
$set->map(callable $fn): Ds\Set               // Puede producir duplicados → nuevo Set
$set->reduce(callable $fn, mixed $init): mixed

// ── Ordenamiento ─────────────────────────────────────────────────────────────
$set->sort(?callable $comparator): void
$set->sorted(?callable $comparator): Ds\Set
$set->reverse(): void
$set->reversed(): Ds\Set

// ── Utilidades ───────────────────────────────────────────────────────────────
$set->count(): int
$set->isEmpty(): bool
$set->clear(): void
$set->slice(int $index, ?int $length): Ds\Set
$set->sum(): int|float
$set->join(string $glue = ''): string
$set->capacity(): int
$set->allocate(int $capacity): void
$set->toArray(): array
$set->copy(): Ds\Set

Ejemplos de uso

$tags = \Ds\set(['php', 'backend', 'php', 'api']);
// Set{'php', 'backend', 'api'}  — duplicado ignorado

$tags->add('docker');
$tags->remove('api');

var_dump($tags->contains('php'));     // true
var_dump($tags->contains('java'));    // false

// Operaciones de conjuntos
$a = \Ds\set([1, 2, 3, 4]);
$b = \Ds\set([3, 4, 5, 6]);

$a->union($b);      // {1, 2, 3, 4, 5, 6}
$a->intersect($b);  // {3, 4}
$a->diff($b);       // {1, 2}
$a->xor($b);        // {1, 2, 5, 6}

// Eliminar duplicados de un array
$unicos = \Ds\set($array_con_duplicados)->toArray();

`Ds\Heap` — Montículo configurable

Un montículo (heap) es una estructura de árbol donde el elemento más «prioritario» está siempre en la raíz y puede extraerse en O(log n). Por defecto es un max-heap (el mayor valor tiene mayor prioridad).

Reemplaza a Ds\PriorityQueue y añade soporte para un comparador personalizable.

// Max-heap por defecto
$heap = new Ds\Heap([3, 1, 4, 1, 5, 9, 2]);
// o bien:
$heap = \Ds\heap([3, 1, 4, 1, 5]);

// Min-heap con comparador
$minHeap = new Ds\Heap([], fn($a, $b) => $b <=> $a);

// Heap personalizado (por longitud de string)
$heap = new Ds\Heap([], fn($a, $b) => strlen($a) <=> strlen($b));

Métodos de `Ds\Heap`

$heap->push(mixed ...$values): void   // Inserta uno o más valores
$heap->pop(): mixed                   // Extrae y retorna el elemento prioritario
$heap->peek(): mixed                  // Lee el elemento prioritario sin extraerlo
$heap->count(): int
$heap->isEmpty(): bool
$heap->clear(): void
$heap->copy(): Ds\Heap
$heap->toArray(): array               // Array sin orden garantizado

Ejemplos de uso

// Cola de prioridades (max-heap)
$heap = \Ds\heap([10, 5, 20, 3]);
echo $heap->peek();   // 20
echo $heap->pop();    // 20
echo $heap->pop();    // 10

// Min-heap: el menor tiene prioridad
$minHeap = new Ds\Heap([], fn($a, $b) => $b <=> $a);
$minHeap->push(10, 5, 20, 3);
echo $minHeap->pop(); // 3
echo $minHeap->pop(); // 5

// Ordenar N elementos de forma eficiente
$datos = [42, 7, 15, 99, 1];
$heap = \Ds\heap($datos);
$ordenado = [];
while (!$heap->isEmpty()) {
    array_unshift($ordenado, $heap->pop()); // de mayor a menor → invertir
}
// $ordenado = [1, 7, 15, 42, 99]

// Priorización de tareas
$tareas = new Ds\Heap([], fn($a, $b) => $a['prioridad'] <=> $b['prioridad']);
$tareas->push(['nombre' => 'Deploy', 'prioridad' => 9]);
$tareas->push(['nombre' => 'Tests',  'prioridad' => 7]);
$tareas->push(['nombre' => 'Docs',   'prioridad' => 3]);
echo $tareas->pop()['nombre'];  // Deploy

`Ds\Pair` — Par clave-valor (readonly)

Un par inmutable clave-valor. Lo retornan métodos como $map->first(), $map->last() y la iteración sobre un Ds\Map.

En v2, Ds\Pair es una clase readonly: sus propiedades no pueden modificarse ni unsetearse tras la creación.

$par = new Ds\Pair('nombre', 'Ana');
echo $par->key;    // nombre
echo $par->value;  // Ana

// Desde un Map
$map = \Ds\map(['x' => 10, 'y' => 20]);
$primero = $map->first();  // Ds\Pair
echo $primero->key;        // x
echo $primero->value;      // 10

// Al iterar un Map
foreach ($map->pairs() as $par) {
    echo "{$par->key} => {$par->value}\n";
}

// Copiar (ya no existe ::copy(), usar clone)
$copia = clone $par;

`Ds\Key` — Interfaz para claves personalizadas

Interfaz que reemplaza a Ds\Hashable. Permite usar objetos como claves en Ds\Map y Ds\Set con igualdad personalizada.

interface Ds\Key
{
    public function hash(): mixed;
    public function equals(mixed $other): bool;
}

Ejemplo de uso

class Coordenada implements Ds\Key
{
    public function __construct(
        public readonly float $lat,
        public readonly float $lng,
    ) {}

    public function hash(): mixed
    {
        return "{$this->lat},{$this->lng}";
    }

    public function equals(mixed $other): bool
    {
        return $other instanceof self
            && $this->lat === $other->lat
            && $this->lng === $other->lng;
    }
}

$mapa = new Ds\Map();
$c1 = new Coordenada(19.4326, -99.1332);  // Ciudad de México
$c2 = new Coordenada(40.4168, -3.7038);   // Madrid

$mapa->put($c1, 'CDMX');
$mapa->put($c2, 'Madrid');

// Dos instancias distintas con los mismos valores son la misma clave:
$busqueda = new Coordenada(19.4326, -99.1332);
echo $mapa->get($busqueda);  // CDMX

Comparativa de rendimiento vs array

Operación	`array`	`Ds\Seq`	`Ds\Map`	`Ds\Set`
Insertar al final	O(1)*	O(1)	O(1)	O(1)
Insertar al inicio	O(n)	O(n)	O(n)	O(n)
Acceso por índice	O(1)	O(1)	O(n)	O(1)
Buscar por valor	O(n)	O(n)	O(1)†	O(1)
Memoria por valor	~alta	~baja	~media	~media

* amortizado
† acceso por clave, que es la operación natural de Map

¿Cuándo usar cada tipo?

Necesidad	Tipo recomendado
Lista ordenada, acceso por índice	`Ds\Seq`
Stack (pila LIFO)	`Ds\Seq` (`push`/`pop`)
Queue (cola FIFO)	`Ds\Seq` (`push`/`shift`)
Diccionario con claves de cualquier tipo	`Ds\Map`
Eliminar duplicados, operaciones de conjuntos	`Ds\Set`
Cola de prioridades / ordenamiento parcial	`Ds\Heap`
Clave de Map/Set con igualdad personalizada	Implementar `Ds\Key`

Características comunes a todos los tipos

Todos los tipos de ext-ds v2:

Implementan Countable → count($coleccion) y $coleccion->count()
Implementan IteratorAggregate → usables en foreach
Implementan JsonSerializable → json_encode($coleccion) funciona
Soportan var_dump(), print_r(), serialize()/unserialize()
Copy-on-Write: clonar es O(1), la copia real se difiere hasta la primera mutación
Iteración segura durante mutación gracias a COW

Copy-on-Write (COW)

$a = new Ds\Seq([1, 2, 3]);
$b = $a;           // O(1) — copia diferida, no duplica memoria todavía
$b->push(4);       // Aquí sí se copia internamente; $a no se modifica

Clonar y iterar durante mutación son ahora operaciones seguras.

Constructores funcionales

v2 agrega funciones globales de conveniencia:

$seq  = \Ds\seq([1, 2, 3]);
$map  = \Ds\map(['a' => 1, 'b' => 2]);
$set  = \Ds\set([1, 2, 3]);
$heap = \Ds\heap([3, 1, 2]);

Equivalen a new Ds\Seq(...), new Ds\Map(...), etc.

Recursos

Repositorio ext-ds
Polyfill (para IDE y entornos sin la extensión)
Documentación en php.net (puede no reflejar aún v2)
CHANGELOG

Guía de Estructuras de Datos Nativas para PHP

¿Qué es ext-ds?

Instalación

Tipos disponibles

Ds\Seq — Secuencia unificada

Métodos de Ds\Seq

Ejemplos de uso

Ds\Map — Mapa ordenado

Métodos de Ds\Map

Ejemplos de uso

Ds\Set — Conjunto ordenado de valores únicos

Métodos de Ds\Set

Ejemplos de uso

Ds\Heap — Montículo configurable

Métodos de Ds\Heap

Ejemplos de uso

Ds\Pair — Par clave-valor (readonly)

Ds\Key — Interfaz para claves personalizadas

Ejemplo de uso

Comparativa de rendimiento vs array

¿Cuándo usar cada tipo?

Características comunes a todos los tipos

Copy-on-Write (COW)

Constructores funcionales

Recursos

Ulises Rendón

Artículos relacionados

Programación Orientada a Objetos en PHP

Manejo de bases de datos con PHP

Operadores en PHP

¿Qué es `ext-ds`?

`Ds\Seq` — Secuencia unificada

Métodos de `Ds\Seq`

`Ds\Map` — Mapa ordenado

Métodos de `Ds\Map`

`Ds\Set` — Conjunto ordenado de valores únicos

Métodos de `Ds\Set`

`Ds\Heap` — Montículo configurable

Métodos de `Ds\Heap`

`Ds\Pair` — Par clave-valor (readonly)

`Ds\Key` — Interfaz para claves personalizadas