A classe Set

(PECL ds >= 1.0.0)

Introdução

Um Set é uma sequência de valores únicos. Esta implementação usa a mesma tabela de hash que Ds\Map, onde os valores são usados como chaves e o valor mapeado é ignorado.

Pontos Fortes

Os valores podem ser de qualquer tipo, incluindo objetos.
Suporta a sintaxe de array (colchetes).
A ordem de inserção é preservada.
Libera automaticamente a memória alocada quando seu tamanho fica baixo o suficiente.
add(), remove() e contains() são todos O(1).

Pontos Fracos

Não suporta push(), pop(), insert(), shift() ou unshift().
get() é O(n) se houver valores excluídos no buffer antes do índice acessado, O(1) caso contrário.

Resumo da classe

class Ds\Set implements Ds\Collection, ArrayAccess {

/* Constantes */

const int MIN_CAPACITY = 16;

/* Métodos */

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

public allocate(int $capacity): void

public capacity(): int

public clear(): void

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

public copy(): Ds\Set

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

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

public first(): mixed

public get(int $index): mixed

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

public isEmpty(): bool

public join(string $glue = ?): string

public last(): mixed

public map(callable $callback): Ds\Set

public merge(mixed $values): Ds\Set

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

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

public reverse(): void

public reversed(): Ds\Set

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

public sort(callable $comparator = ?): void

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

public sum(): int|float

public toArray(): array

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

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

}

Constantes predefinidas

Ds\Set::MIN_CAPACITY

Registro de Alterações

Versão	Descrição
PECL ds 1.3.0	A classe agora implementa ArrayAccess.
PECL ds 1.2.7	Adicionado o método Ds\Set::map().

Índice

Ds\Set::add — Adiciona valores ao conjunto
Ds\Set::allocate — Aloca memória suficiente para uma capacidade necessária
Ds\Set::capacity — Retorna a capacidade atual
Ds\Set::clear — Remove todos os valores
Ds\Set::__construct — Cria uma nova instância
Ds\Set::contains — Determina se o conjunto contém todos os valores
Ds\Set::copy — Retorna uma cópia rasa do conjunto
Ds\Set::count — Retorna o número de valores no conjunto
Ds\Set::diff — Cria um novo conjunto usando valores que não estão em outro conjunto
Ds\Set::filter — Cria um novo conjunto usando um callable para determinar quais valores incluir
Ds\Set::first — Retorna o primeiro valor no conjunto
Ds\Set::get — Retorna o valor em um índice específico
Ds\Set::intersect — Cria um novo conjunto interseccionando valores com outro conjunto
Ds\Set::isEmpty — Retorna se o conjunto está vazio
Ds\Set::join — Junta todos os valores em uma string
Ds\Set::jsonSerialize — Retorna uma representação que pode ser convertida para JSON
Ds\Set::last — Retorna o último valor no conjunto
Ds\Set::map — Retorna o resultado da aplicação de um retorno de chamada a cada valor
Ds\Set::merge — Retorna o resultado da adição de todos os valores dados ao conjunto
Ds\Set::reduce — Reduz o conjunto a um único valor usando uma função de callback
Ds\Set::remove — Remove todos os valores dados do conjunto
Ds\Set::reverse — Inverte o conjunto no local
Ds\Set::reversed — Retorna uma cópia invertida
Ds\Set::slice — Retorna um subconjunto de um intervalo dado
Ds\Set::sort — Ordena o conjunto no local
Ds\Set::sorted — Retorna uma cópia ordenada
Ds\Set::sum — Retorna a soma de todos os valores no conjunto
Ds\Set::toArray — Converte o conjunto para um array
Ds\Set::union — Cria um novo conjunto usando valores da instância atual e de outro conjunto
Ds\Set::xor — Cria um novo conjunto usando valores na instância atual ou em outro conjunto, mas não em ambos

Melhore Esta Página

Aprenda Como Melhorar Esta Página • Envie uma Solicitação de Modificação • Reporte um Problema

＋adicione uma nota

Notas Enviadas por Usuários (em inglês) 2 notes

down

Anonymous ¶

6 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 ¶

2 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"
}

*/

＋adicione uma nota