ConFoo 2025

La classe Deque

(PECL ds >= 1.0.0)

Introduction

Un Deque (prononcé “deck”) est une séquence de valeurs dans un tampon contigu qui grandit et rétrécit automatiquement. Le nom est une abréviation courante de “double-ended queue” et est utilisé en interne par Ds\Queue.

Deux pointeurs sont utilisés pour garder une trace d'une tête et d'une queue. Les pointeurs peuvent “enrouler” la fin du tampon, ce qui évite de déplacer d'autres valeurs pour faire de la place. Cela rend shift et unshift très rapides — quelque chose qu'un Ds\Vector ne peut pas concurrencer.

Accéder à une valeur par index nécessite une traduction entre l'index et sa position correspondante dans le tampon : ((head + position) % capacity).

Forces

  • Support de la syntaxe de tableau (crochets).
  • Utilise moins de mémoire globale qu'un tableau pour le même nombre de valeurs.
  • Libère automatiquement la mémoire allouée lorsque sa taille devient suffisamment faible.
  • get(), set(), push(), pop(), shift(), et unshift() sont tous de complexité O(1).

Faiblesses

  • La capacité doit être une puissance de 2.
  • insert() et remove() sont de complexité O(n).

Synopsis de la classe

class Ds\Deque implements Ds\Sequence, ArrayAccess {
/* Constantes */
const int MIN_CAPACITY = 8;
/* Méthodes */
public allocate(int $capacity): void
public apply(callable $callback): void
public capacity(): int
public clear(): void
public contains(mixed ...$values): bool
public copy(): Ds\Deque
public filter(callable $callback = ?): Ds\Deque
public find(mixed $value): mixed
public first(): mixed
public get(int $index): mixed
public insert(int $index, mixed ...$values): void
public isEmpty(): bool
public join(string $glue = ?): string
public last(): mixed
public map(callable $callback): Ds\Deque
public merge(mixed $values): Ds\Deque
public pop(): mixed
public push(mixed ...$values): void
public reduce(callable $callback, mixed $initial = ?): mixed
public remove(int $index): mixed
public reverse(): void
public reversed(): Ds\Deque
public rotate(int $rotations): void
public set(int $index, mixed $value): void
public shift(): mixed
public slice(int $index, int $length = ?): Ds\Deque
public sort(callable $comparator = ?): void
public sorted(callable $comparator = ?): Ds\Deque
public sum(): int|float
public toArray(): array
public unshift(mixed $values = ?): void
}

Constantes pré-définies

Ds\Deque::MIN_CAPACITY

Historique

Version Description
PECL ds 1.3.0 La classe implémente maintenant ArrayAccess.

Sommaire

add a note

User Contributed Notes

There are no user contributed notes for this page.
To Top