The Set class

(No version information available, might only be in Git)

简介

A Set is a sequence of unique values. This implementation uses the same hash table as Ds\Map, where values are used as keys and the mapped value is ignored.

Strengths

Values can be any type, including objects.
Supports array syntax (square brackets).
Insertion order is preserved.
Automatically frees allocated memory when its size drops low enough.
add(), remove() and contains() are all O(1).

Weaknesses

Doesn't support push(), pop(), insert(), shift(), or unshift().
get() is O(n) if there are deleted values in the buffer before the accessed index, O(1) otherwise.

类摘要

Ds\Set implements Ds\Collection {

/* Constants */

const int MIN_CAPACITY = 16 ;

/* 方法 */

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

public allocate ( int $capacity ) : void

public capacity ( void ) : int

public clear ( void ) : void

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

public copy ( void ) : Ds\Set

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

public filter ([ callable $callback ] ) : Ds\Set

public first ( void ) : mixed

public get ( int $index ) : mixed

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

public isEmpty ( void ) : bool

public join ([ string $glue ] ) : string

public last ( void ) : void

public merge ( mixed $values ) : Ds\Set

public reduce ( callable $callback [, mixed $initial ] ) : mixed

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

public reverse ( void ) : void

public reversed ( void ) : Ds\Set

public slice ( int $index [, int $length ] ) : Ds\Set

public sort ([ callable $comparator ] ) : void

public sorted ([ callable $comparator ] ) : Ds\Set

public sum ( void ) : number

public toArray ( void ) : array

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

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

}

预定义常量

Ds\Set::MIN_CAPACITY

Ds\Set::add — Adds values to the set
Ds\Set::allocate — Allocates enough memory for a required capacity
Ds\Set::capacity — Returns the current capacity
Ds\Set::clear — Removes all values
Ds\Set::__construct — Creates a new instance
Ds\Set::contains — Determines if the set contains all values
Ds\Set::copy — Returns a shallow copy of the set
Ds\Set::count — Returns the number of values in the set
Ds\Set::diff — Creates a new set using values that aren't in another set
Ds\Set::filter — Creates a new set using a callable to determine which values to include
Ds\Set::first — Returns the first value in the set
Ds\Set::get — Returns the value at a given index
Ds\Set::intersect — Creates a new set by intersecting values with another set
Ds\Set::isEmpty — Returns whether the set is empty
Ds\Set::join — Joins all values together as a string
Ds\Set::jsonSerialize — Returns a representation that can be converted to JSON
Ds\Set::last — Returns the last value in the set
Ds\Set::merge — Returns the result of adding all given values to the set
Ds\Set::reduce — Reduces the set to a single value using a callback function
Ds\Set::remove — Removes all given values from the set
Ds\Set::reverse — Reverses the set in-place
Ds\Set::reversed — Returns a reversed copy
Ds\Set::slice — Returns a sub-set of a given range
Ds\Set::sort — Sorts the set in-place
Ds\Set::sorted — Returns a sorted copy
Ds\Set::sum — Returns the sum of all values in the set
Ds\Set::toArray — Converts the set to an array
Ds\Set::union — Creates a new set using values from the current instance and another set
Ds\Set::xor — Creates a new set using values in either the current instance or in another set, but not in both

User Contributed Notes

rtheunissen at php dot net 04-Jul-2018 03:08


Lookups by value are O(1), lookups by index are O(n) if there are deleted values before the index, O(1) otherwise.

Anonymous 01-Feb-2018 01:49


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.

vdavila dot sm at gmail dot com 15-Oct-2017 02:07


I have a question is contains() a O(1)? and why?

The Set class

简介

Strengths

Weaknesses

类摘要

预定义常量

Table of Contents

User Contributed Notes