La classe Set

(PECL ds >= 1.0.0)

Introduction

Un Set est une séquence de valeurs uniques. Cette implémentation utilise la même table de hachage que Ds\Map, où les valeurs sont utilisées comme clés et la valeur mappée est ignorée.

Force

Les valeurs peuvent être de n'importe quel type, y compris des objets.
Support de la syntaxe de tableau (crochets).
L'ordre d'insertion est préservé.
Libère automatiquement la mémoire allouée lorsque sa taille devient suffisamment faible.
add(), remove() et contains() sont tous de complexité O(1).

Faiblesses

Ne supporte pas: push(), pop(), insert(), shift(), ou unshift().
get() est de complexité O(n) s'il y a des valeurs supprimées dans le tampon avant l'index accédé, O(1) sinon.

Synopsis de la classe

class Ds\Set implements Ds\Collection, ArrayAccess {

/* Constantes */

const int MIN_CAPACITY = 8;

/* Méthodes */

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

public function allocate(int $capacity): void

public function capacity(): int

public function clear(): void

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

public function copy(): Ds\Set

public function diff(Ds\Set $set): Ds\Set

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

public function first(): mixed

public function get(int $index): mixed

public function intersect(Ds\Set $set): Ds\Set

public function isEmpty(): bool

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

public function last(): mixed

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

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

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

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

public function reverse(): void

public function reversed(): Ds\Set

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

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

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

public function sum(): int|float

public function toArray(): array

public function union(Ds\Set $set): Ds\Set

public function xor(Ds\Set $set): Ds\Set

}

Constantes pré-définies

Ds\Set::MIN_CAPACITY

Historique

Version	Description
PECL ds 1.3.0	Cette classe implémente maintenant ArrayAccess.
PECL ds 1.2.7	Ajout de la méthode Ds\Set::map().
PECL ds 1.2.0	`Ds\Set::MIN_CAPACITY` est passé de 16 à 8.

Sommaire

Ds\Set::add — Ajoute des valeurs à la séquence
Ds\Set::allocate — Alloue suffisamment de mémoire pour une capacité requise
Ds\Set::capacity — Renvoie la capacité actuelle
Ds\Set::clear — Supprime toutes les valeurs
Ds\Set::__construct — Crée une nouvelle instance
Ds\Set::contains — Détermine si l'ensemble contient toutes les valeurs
Ds\Set::copy — Renvoie une copie superficielle de la séquence
Ds\Set::count — Renvoie le nombre de valeurs dans la séquence
Ds\Set::diff — Crée un nouvel ensemble en utilisant des valeurs qui ne sont pas dans une autre séquence
Ds\Set::filter — Créer un nouvel ensemble en utilisant un callable pour déterminer quelles valeurs inclure
Ds\Set::first — Renvoie la première valeur de la séquence
Ds\Set::get — Renvoie la valeur à un index donné
Ds\Set::intersect — Crée un nouvel ensemble en utilisant des valeurs communes avec une autre séquence
Ds\Set::isEmpty — Renvoie si l'ensemble est vide
Ds\Set::join — Rassemble toutes les valeurs en une chaîne
Ds\Set::jsonSerialize — Renvoie une représentation qui peut être convertie en JSON
Ds\Set::last — Renvoie la dernière valeur de la séquence
Ds\Set::map — Renvoie le résultat de l'application d'une fonction de rappel à chaque valeur
Ds\Set::merge — Renvoie le résultat de l'ajout de toutes les valeurs de la séquence
Ds\Set::reduce — Réduit l'ensemble à une seule valeur en utilisant une fonction de rappel
Ds\Set::remove — Supprime toutes les valeurs données de la séquence
Ds\Set::reverse — Renverse l'ensemble en place
Ds\Set::reversed — Renvoie une copie renversée
Ds\Set::slice — Renvoie un sous-ensemble d'une plage donnée
Ds\Set::sort — Trie l'ensemble en place
Ds\Set::sorted — Renvoie une copie triée
Ds\Set::sum — Renvoie la somme de toutes les valeurs de la séquence
Ds\Set::toArray — Convertit l'ensemble en un tableau
Ds\Set::union — Crée un nouvel ensemble en utilisant les valeurs de l'instance actuelle et d'un autre ensemble
Ds\Set::xor — Crée un nouvel ensemble en utilisant les valeurs de l'instance actuelle ou d'un autre ensemble, mais pas des deux

Found A Problem?

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

＋add a note

User Contributed Notes 2 notes

down

Anonymous ¶

8 years ago

Lookup for a Set should be O(1). This is true for sets and hashtables (eg maps) in any language.

The way this is possible is that sets store values differently than arrays.

In an array values are stored sequentially based on what their place is in the array and where that array is in memory, so to find your item you need to scan through the array sequentially to find your item (unless it's a sorted array, then you can use binary search at O(logn)).

Sets declare a block of memory, like an array, but instead of putting items in memory in sequence, like an array, they determine the index of the item to add by running the item through a hash function (essentially a function that takes in an object and returns an evenly distributed, very large random number), and then modulousing the result of that hash function by the size of the memory block they have.

So, when you call contains($needle, $mySetHaystack), php will take $needle, and feed it into a hashfunction, which will return a big number like 9283472378, then it takes the length of $mySetHaystack (let's say 31), and does 9283472378 % 31 = 28, so it checks the 28th index of $mySetHaystack to see if $needle is there. Everything in this list of operations is independent of the size of $mySetHaystack, hence the perf being O(1).

If a hash function returns the same value for two different items (a hash collision, which totally happens), or if the modulo of that value is the same, then an array of values is stored in the set at that index. Since sets don't allow duplicate values, this happens rarely and is negligible from a perf perspective.

You should check out the wikipedia page on hash tables (similar to sets), as there are lots of pictures that will make this concept easier to understand.

down

Sbastien ¶

3 years ago

One nice thing is the type-awarness. array_unique() lose values (whatever flag), while Ds\Set keep them.

<?php

$array = [true, false, null, '', 0, '0', 123, '123'];
var_dump(array_unique($array));
var_dump(new \Ds\Set($array));

/*

Gives :

array(4) {
  [0]=> bool(true)
  [1]=> bool(false)
  [4]=> int(0)
  [6]=> int(123)
}
object(Ds\Set)#1 (8) {
  [0]=> bool(true)
  [1]=> bool(false)
  [2]=> NULL
  [3]=> string(0) ""
  [4]=> int(0)
  [5]=> string(1) "0"
  [6]=> int(123)
  [7]=> string(3) "123"
}

*/

＋add a note