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 function allocate(int $capacity): void

public function apply(callable $callback): void

public function capacity(): int

public function clear(): void

public function contains(mixed ...$values): bool

public function copy(): Ds\Deque

public function filter(callable $callback = ?): Ds\Deque

public function find(mixed $value): mixed

public function first(): mixed

public function get(int $index): mixed

public function insert(int $index, mixed ...$values): void

public function isEmpty(): bool

public function join(string $glue = ?): string

public function last(): mixed

public function map(callable $callback): Ds\Deque

public function merge(mixed $values): Ds\Deque

public function pop(): mixed

public function push(mixed ...$values): void

public function reduce(callable $callback, mixed $initial = ?): mixed

public function remove(int $index): mixed

public function reverse(): void

public function reversed(): Ds\Deque

public function rotate(int $rotations): void

public function set(int $index, mixed $value): void

public function shift(): mixed

public function slice(int $index, int $length = ?): Ds\Deque

public function sort(callable $comparator = ?): void

public function sorted(callable $comparator = ?): Ds\Deque

public function sum(): int|float

public function toArray(): array

public function 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

Ds\Deque::allocate — Alloue suffisamment de mémoire pour une capacité requise
Ds\Deque::apply — Met à jour toutes les valeurs en appliquant une fonction de rappel à chaque valeur
Ds\Deque::capacity — Renvoie la capacité actuelle
Ds\Deque::clear — Supprime toutes les valeurs du deque
Ds\Deque::__construct — Crée une nouvelle instance
Ds\Deque::contains — Détermine si le deque contient des valeurs données
Ds\Deque::copy — Renvoie une copie superficielle de la deque
Ds\Deque::count — Renvoie le nombre de valeurs dans la collection
Ds\Deque::filter — Créer un nouveau deque en utilisant un callable pour déterminer quelles valeurs inclure
Ds\Deque::find — Essaye de trouver l'index d'une valeur
Ds\Deque::first — Renvoie la première valeur de la deque
Ds\Deque::get — Renvoie la valeur à un index donné
Ds\Deque::insert — Insère des valeurs à un index donné
Ds\Deque::isEmpty — Renvoie si la deque est vide
Ds\Deque::join — Rassemble toutes les valeurs en une chaîne
Ds\Deque::jsonSerialize — Renvoie une représentation qui peut être convertie en JSON
Ds\Deque::last — Renvoie la dernière valeur
Ds\Deque::map — Renvoie le résultat de l'application d'une fonction de rappel à chaque valeur
Ds\Deque::merge — Renvoie le résultat de l'ajout de toutes les valeurs données au deque
Ds\Deque::pop — Enlève et renvoie la dernière valeur
Ds\Deque::push — Ajoute des valeurs à la fin du deque
Ds\Deque::reduce — Réduit le deque à une seule valeur en utilisant une fonction de rappel
Ds\Deque::remove — Enlève et renvoie une valeur par index
Ds\Deque::reverse — Renverse le deque en place
Ds\Deque::reversed — Renvoie une copie renversée
Ds\Deque::rotate — Tourne le deque d'un certain nombre de rotations
Ds\Deque::set — Met à jour une valeur à un index donné
Ds\Deque::shift — Enlève et renvoie la première valeur
Ds\Deque::slice — Renvoie un sous-deque d'une plage donnée
Ds\Deque::sort — Trie le deque en place
Ds\Deque::sorted — Renvoie une copie triée
Ds\Deque::sum — Renvoie la somme de toutes les valeurs du deque
Ds\Deque::toArray — Convertit le deque en un tableau
Ds\Deque::unshift — Ajoute des valeurs au début du deque

Found A Problem?

Learn How To Improve This Page • Submit a Pull Request • Report a Bug

＋add a note

User Contributed Notes

There are no user contributed notes for this page.