Collections and Data Structures

Iteration

Sequential iteration is implemented by the iterate function. The general for loop:

for i in iter   # or  "for i = iter"
    # body
end

is translated into:

next = iterate(iter)
while next !== nothing
    (i, state) = next
    # body
    next = iterate(iter, state)
end

The state object may be anything, and should be chosen appropriately for each iterable type. See the manual section on the iteration interface for more details about defining a custom iterable type.

Base.iterate — Function

iterate(iter [, state]) -> Union{Nothing, Tuple{Any, Any}}

Advance the iterator to obtain the next element. If no elements remain, nothing should be returned. Otherwise, a 2-tuple of the next element and the new iteration state should be returned.

source

Base.IteratorSize — Type

IteratorSize(itertype::Type) -> IteratorSize

Given the type of an iterator, return one of the following values:

SizeUnknown() if the length (number of elements) cannot be determined in advance.
HasLength() if there is a fixed, finite length.
HasShape{N}() if there is a known length plus a notion of multidimensional shape (as for an array). In this case N should give the number of dimensions, and the axes function is valid for the iterator.
IsInfinite() if the iterator yields values forever.

The default value (for iterators that do not define this function) is HasLength(). This means that most iterators are assumed to implement length.

This trait is generally used to select between algorithms that pre-allocate space for their result, and algorithms that resize their result incrementally.

julia> Base.IteratorSize(1:5)
Base.HasShape{1}()

julia> Base.IteratorSize((2,3))
Base.HasLength()

source

Base.IteratorEltype — Type

IteratorEltype(itertype::Type) -> IteratorEltype

Given the type of an iterator, return one of the following values:

EltypeUnknown() if the type of elements yielded by the iterator is not known in advance.
HasEltype() if the element type is known, and eltype would return a meaningful value.

HasEltype() is the default, since iterators are assumed to implement eltype.

This trait is generally used to select between algorithms that pre-allocate a specific type of result, and algorithms that pick a result type based on the types of yielded values.

julia> Base.IteratorEltype(1:5)
Base.HasEltype()

source

Fully implemented by:

Constructors and Types

Base.AbstractRange — Type

AbstractRange{T} <: AbstractVector{T}

Supertype for linear ranges with elements of type T. UnitRange, LinRange and other types are subtypes of this.

All subtypes must define step. Thus LogRange is not a subtype of AbstractRange.

source

Base.OrdinalRange — Type

OrdinalRange{T, S} <: AbstractRange{T}

Supertype for ordinal ranges with elements of type T with spacing(s) of type S. The steps should be always-exact multiples of oneunit, and T should be a "discrete" type, which cannot have values smaller than oneunit. For example, Integer or Date types would qualify, whereas Float64 would not (since this type can represent values smaller than oneunit(Float64). UnitRange, StepRange, and other types are subtypes of this.

source

Base.AbstractUnitRange — Type

AbstractUnitRange{T} <: OrdinalRange{T, T}

Supertype for ranges with a step size of oneunit(T) with elements of type T. UnitRange and other types are subtypes of this.

source

Base.StepRange — Type

StepRange{T, S} <: OrdinalRange{T, S}

Ranges with elements of type T with spacing of type S. The step between each element is constant, and the range is defined in terms of a start and stop of type T and a step of type S. Neither T nor S should be floating point types. The syntax a:b:c with b != 0 and a, b, and c all integers creates a StepRange.

Examples

julia> collect(StepRange(1, Int8(2), 10))
5-element Vector{Int64}:
 1
 3
 5
 7
 9

julia> typeof(StepRange(1, Int8(2), 10))
StepRange{Int64, Int8}

julia> typeof(1:3:6)
StepRange{Int64, Int64}

source

Base.UnitRange — Type

UnitRange{T<:Real}

A range parameterized by a start and stop of type T, filled with elements spaced by 1 from start until stop is exceeded. The syntax a:b with a and b both Integers creates a UnitRange.

Examples

julia> collect(UnitRange(2.3, 5.2))
3-element Vector{Float64}:
 2.3
 3.3
 4.3

julia> typeof(1:10)
UnitRange{Int64}

source

Base.LinRange — Type

LinRange{T,L}

A range with len linearly spaced elements between its start and stop. The size of the spacing is controlled by len, which must be an Integer.

Examples

julia> LinRange(1.5, 5.5, 9)
9-element LinRange{Float64, Int64}:
 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0, 5.5

Compared to using range, directly constructing a LinRange should have less overhead but won't try to correct for floating point errors:

julia> collect(range(-0.1, 0.3, length=5))
5-element Vector{Float64}:
 -0.1
  0.0
  0.1
  0.2
  0.3

julia> collect(LinRange(-0.1, 0.3, 5))
5-element Vector{Float64}:
 -0.1
 -1.3877787807814457e-17
  0.09999999999999999
  0.19999999999999998
  0.3

See also Logrange for logarithmically spaced points.

source

General Collections

Base.isempty — Function

isempty(condition)

Return true if no tasks are waiting on the condition, false otherwise.

source

isempty(collection) -> Bool

Determine whether a collection is empty (has no elements).

Warning

isempty(itr) may consume the next element of a stateful iterator itr unless an appropriate Base.isdone(itr) method is defined. Stateful iterators should implement isdone, but you may want to avoid using isempty when writing generic code which should support any iterator type.

Examples

julia> isempty([])
true

julia> isempty([1 2 3])
false

source

Base.isdone — Function

isdone(itr, [state]) -> Union{Bool, Missing}

This function provides a fast-path hint for iterator completion. This is useful for stateful iterators that want to avoid having elements consumed if they are not going to be exposed to the user (e.g. when checking for done-ness in isempty or zip).

Stateful iterators that want to opt into this feature should define an isdone method that returns true/false depending on whether the iterator is done or not. Stateless iterators need not implement this function.

If the result is missing, callers may go ahead and compute iterate(x, state) === nothing to compute a definite answer.

Iterable Collections

Base.in — Function

in(item, collection) -> Bool
∈(item, collection) -> Bool

Determine whether an item is in the given collection, in the sense that it is == to one of the values generated by iterating over the collection. Can equivalently be used with infix syntax:

item in collection
item ∈ collection

Return a Bool value, except if item is missing or collection contains missing but not item, in which case missing is returned (three-valued logic, matching the behavior of any and ==). Some collections follow a slightly different definition. For example, Sets check whether the item isequal to one of the elements; Dicts look for key=>value pairs, and the key is compared using isequal.

To test for the presence of a key in a dictionary, use haskey or k in keys(dict). For the collections mentioned above, the result is always a Bool.

When broadcasting with in.(items, collection) or items .∈ collection, both items and collection are broadcasted over, which is often not what is intended. For example, if both arguments are vectors (and the dimensions match), the result is a vector indicating whether each value in collection items is in the value at the corresponding position in collection. To get a vector indicating whether each value in items is in collection, wrap collection in a tuple or a Ref like this: in.(items, Ref(collection)) or items .∈ Ref(collection).

Examples

julia> a = 1:3:20
1:3:19

julia> 4 in a
true

julia> 5 in a
false

julia> missing in [1, 2]
missing

julia> 1 in [2, missing]
missing

julia> 1 in [1, missing]
true

julia> missing in Set([1, 2])
false

julia> (1=>missing) in Dict(1=>10, 2=>20)
missing

julia> [1, 2] .∈ [2, 3]
2-element BitVector:
 0
 0

julia> [1, 2] .∈ ([2, 3],)
2-element BitVector:
 0
 1

source

Base.:∉ — Function

∉(item, collection) -> Bool
∌(collection, item) -> Bool

Negation of ∈ and ∋, i.e. checks that item is not in collection.

When broadcasting with items .∉ collection, both items and collection are broadcasted over, which is often not what is intended. For example, if both arguments are vectors (and the dimensions match), the result is a vector indicating whether each value in collection items is not in the value at the corresponding position in collection. To get a vector indicating whether each value in items is not in collection, wrap collection in a tuple or a Ref like this: items .∉ Ref(collection).

Examples

julia> 1 ∉ 2:4
true

julia> 1 ∉ 1:3
false

julia> [1, 2] .∉ [2, 3]
2-element BitVector:
 1
 1

julia> [1, 2] .∉ ([2, 3],)
2-element BitVector:
 1
 0

source

Base.hasfastin — Function

Base.hasfastin(T)

Determine whether the computation x ∈ collection where collection::T can be considered as a "fast" operation (typically constant or logarithmic complexity). The definition hasfastin(x) = hasfastin(typeof(x)) is provided for convenience so that instances can be passed instead of types. However the form that accepts a type argument should be defined for new types.

The default for hasfastin(T) is true for subtypes of AbstractSet, AbstractDict and AbstractRange and false otherwise.

source

Base.eltype — Function

eltype(type)

Determine the type of the elements generated by iterating a collection of the given type. For dictionary types, this will be a Pair{KeyType,ValType}. The definition eltype(x) = eltype(typeof(x)) is provided for convenience so that instances can be passed instead of types. However the form that accepts a type argument should be defined for new types.

Indexable Collections

Base.getindex — Function

getindex(collection, key...)

Retrieve the value(s) stored at the given key or index within a collection. The syntax a[i,j,...] is converted by the compiler to getindex(a, i, j, ...).

Dictionaries

Dict is the standard dictionary. Its implementation uses hash as the hashing function for the key, and isequal to determine equality. Define these two functions for custom types to override how they are stored in a hash table.

IdDict is a special hash table where the keys are always object identities.

WeakKeyDict is a hash table implementation where the keys are weak references to objects, and thus may be garbage collected even when referenced in a hash table. Like Dict it uses hash for hashing and isequal for equality, unlike Dict it does not convert keys on insertion.

Dicts can be created by passing pair objects constructed with => to a Dict constructor: Dict("A"=>1, "B"=>2). This call will attempt to infer type information from the keys and values (i.e. this example creates a Dict{String, Int64}). To explicitly specify types use the syntax Dict{KeyType,ValueType}(...). For example, Dict{String,Int32}("A"=>1, "B"=>2).

Dictionaries may also be created with generators. For example, Dict(i => f(i) for i = 1:10).

Given a dictionary D, the syntax D[x] returns the value of key x (if it exists) or throws an error, and D[x] = y stores the key-value pair x => y in D (replacing any existing value for the key x). Multiple arguments to D[...] are converted to tuples; for example, the syntax D[x,y] is equivalent to D[(x,y)], i.e. it refers to the value keyed by the tuple (x,y).

Base.AbstractDict — Type

AbstractDict{K, V}

Supertype for dictionary-like types with keys of type K and values of type V. Dict, IdDict and other types are subtypes of this. An AbstractDict{K, V} should be an iterator of Pair{K, V}.

source

Base.Dict — Type

Dict([itr])

Dict{K,V}() constructs a hash table with keys of type K and values of type V. Keys are compared with isequal and hashed with hash.

Given a single iterable argument, constructs a Dict whose key-value pairs are taken from 2-tuples (key,value) generated by the argument.

Examples

julia> Dict([("A", 1), ("B", 2)])
Dict{String, Int64} with 2 entries:
  "B" => 2
  "A" => 1

Alternatively, a sequence of pair arguments may be passed.

julia> Dict("A"=>1, "B"=>2)
Dict{String, Int64} with 2 entries:
  "B" => 2
  "A" => 1

Warning

Keys are allowed to be mutable, but if you do mutate stored keys, the hash table may become internally inconsistent, in which case the Dict will not work properly. IdDict can be an alternative if you need to mutate keys.

source

Base.IdDict — Type

IdDict([itr])

IdDict{K,V}() constructs a hash table using objectid as hash and === as equality with keys of type K and values of type V. See Dict for further help and IdSet for the set version of this.

In the example below, the Dict keys are all isequal and therefore get hashed the same, so they get overwritten. The IdDict hashes by object-id, and thus preserves the 3 different keys.

Examples

julia> Dict(true => "yes", 1 => "no", 1.0 => "maybe")
Dict{Real, String} with 1 entry:
  1.0 => "maybe"

julia> IdDict(true => "yes", 1 => "no", 1.0 => "maybe")
IdDict{Any, String} with 3 entries:
  true => "yes"
  1.0  => "maybe"
  1    => "no"

source

Base.WeakKeyDict — Type

WeakKeyDict([itr])

WeakKeyDict() constructs a hash table where the keys are weak references to objects which may be garbage collected even when referenced in a hash table.

See Dict for further help. Note, unlike Dict, WeakKeyDict does not convert keys on insertion, as this would imply the key object was unreferenced anywhere before insertion.

Set-Like Collections

Base.AbstractSet — Type

AbstractSet{T}

Supertype for set-like types whose elements are of type T. Set, BitSet and other types are subtypes of this.

source

Base.Set — Type

Set{T} <: AbstractSet{T}

Sets are mutable containers that provide fast membership testing.

Sets have efficient implementations of set operations such as in, union and intersect. Elements in a Set are unique, as determined by the elements' definition of isequal. The order of elements in a Set is an implementation detail and cannot be relied on.

Examples

julia> s = Set("aaBca")
Set{Char} with 3 elements:
  'a'
  'c'
  'B'

julia> push!(s, 'b')
Set{Char} with 4 elements:
  'a'
  'b'
  'B'
  'c'

julia> s = Set([NaN, 0.0, 1.0, 2.0]);

julia> -0.0 in s # isequal(0.0, -0.0) is false
false

julia> NaN in s # isequal(NaN, NaN) is true
true

source

Base.BitSet — Type

BitSet([itr])

Construct a sorted set of Ints generated by the given iterable object, or an empty set. Implemented as a bit string, and therefore designed for dense integer sets. If the set will be sparse (for example, holding a few very large integers), use Set instead.

source

Base.IdSet — Type

IdSet{T}([itr])
IdSet()

IdSet{T}() constructs a set (see Set) using === as equality with values of type T.

In the example below, the values are all isequal so they get overwritten in the ordinary Set. The IdSet compares by === and so preserves the 3 different values.

Examples

julia> Set(Any[true, 1, 1.0])
Set{Any} with 1 element:
  1.0

julia> IdSet{Any}(Any[true, 1, 1.0])
IdSet{Any} with 3 elements:
  1.0
  1
  true

source

Base.union — Function

union(s, itrs...)
∪(s, itrs...)

Construct an object containing all distinct elements from all of the arguments.

The first argument controls what kind of container is returned. If this is an array, it maintains the order in which elements first appear.

Unicode ∪ can be typed by writing \cup then pressing tab in the Julia REPL, and in many editors. This is an infix operator, allowing s ∪ itr.

Examples

julia> union([1, 2], [3])
3-element Vector{Int64}:
 1
 2
 3

julia> union([4 2 3 4 4], 1:3, 3.0)
4-element Vector{Float64}:
 4.0
 2.0
 3.0
 1.0

julia> (0, 0.0) ∪ (-0.0, NaN)
3-element Vector{Real}:
   0
  -0.0
 NaN

julia> union(Set([1, 2]), 2:3)
Set{Int64} with 3 elements:
  2
  3
  1

source

Base.union! — Function

union!(s::IntDisjointSet{T}, x::T, y::T)

Merge the subset containing x and that containing y into one and return the root of the new set.

source

union!(s::Union{AbstractSet,AbstractVector}, itrs...)

Construct the union of passed in sets and overwrite s with the result. Maintain order with arrays.

Warning

Behavior can be unexpected when any mutated argument shares memory with any other argument.

Examples

julia> a = Set([3, 4, 5]);

julia> union!(a, 1:2:7);

julia> a
Set{Int64} with 5 elements:
  5
  4
  7
  3
  1

source

Base.intersect — Function

intersect(s, itrs...)
∩(s, itrs...)

Construct the set containing those elements which appear in all of the arguments.

The first argument controls what kind of container is returned. If this is an array, it maintains the order in which elements first appear.

Unicode ∩ can be typed by writing \cap then pressing tab in the Julia REPL, and in many editors. This is an infix operator, allowing s ∩ itr.

Julia 1.8

As of Julia 1.8 intersect returns a result with the eltype of the type-promoted eltypes of the two inputs

Examples

julia> intersect([1, 2, 3], [3, 4, 5])
1-element Vector{Int64}:
 3

julia> intersect([1, 4, 4, 5, 6], [6, 4, 6, 7, 8])
2-element Vector{Int64}:
 4
 6

julia> intersect(1:16, 7:99)
7:16

julia> (0, 0.0) ∩ (-0.0, 0)
1-element Vector{Real}:
 0

julia> intersect(Set([1, 2]), BitSet([2, 3]), 1.0:10.0)
Set{Float64} with 1 element:
  2.0

source

Base.setdiff — Function

setdiff(s, itrs...)

Construct the set of elements in s but not in any of the iterables in itrs. Maintain order with arrays.

See also setdiff!, union and intersect.

Examples

julia> setdiff([1,2,3], [3,4,5])
2-element Vector{Int64}:
 1
 2

source

Base.setdiff! — Function

setdiff!(s, itrs...)

Remove from set s (in-place) each element of each iterable from itrs. Maintain order with arrays.

Warning

Behavior can be unexpected when any mutated argument shares memory with any other argument.

Examples

julia> a = Set([1, 3, 4, 5]);

julia> setdiff!(a, 1:2:6);

julia> a
Set{Int64} with 1 element:
  4

source

Base.symdiff — Function

symdiff(s, itrs...)

Construct the symmetric difference of elements in the passed in sets. When s is not an AbstractSet, the order is maintained.

See also symdiff!, setdiff, union and intersect.

Examples

julia> symdiff([1,2,3], [3,4,5], [4,5,6])
3-element Vector{Int64}:
 1
 2
 6

julia> symdiff([1,2,1], [2, 1, 2])
Int64[]

source

Base.symdiff! — Function

symdiff!(s::Union{AbstractSet,AbstractVector}, itrs...)

Construct the symmetric difference of the passed in sets, and overwrite s with the result. When s is an array, the order is maintained. Note that in this case the multiplicity of elements matters.

Warning

Behavior can be unexpected when any mutated argument shares memory with any other argument.

source

Base.intersect! — Function

intersect!(s::Union{AbstractSet,AbstractVector}, itrs...)

Intersect all passed in sets and overwrite s with the result. Maintain order with arrays.

Warning

Behavior can be unexpected when any mutated argument shares memory with any other argument.

source

Base.issubset — Function

issubset(a, b) -> Bool
⊆(a, b) -> Bool
⊇(b, a) -> Bool

Determine whether every element of a is also in b, using in.

See also ⊊, ⊈, ∩, ∪, contains.

Examples

julia> issubset([1, 2], [1, 2, 3])
true

julia> [1, 2, 3] ⊆ [1, 2]
false

julia> [1, 2, 3] ⊇ [1, 2]
true

source

Base.in! — Function

in!(x, s::AbstractSet) -> Bool

If x is in s, return true. If not, push x into s and return false. This is equivalent to in(x, s) ? true : (push!(s, x); false), but may have a more efficient implementation.

Dequeues

Base.push! — Function

push!(collection, items...) -> collection

Insert one or more items in collection. If collection is an ordered container, the items are inserted at the end (in the given order).

Examples

julia> push!([1, 2, 3], 4, 5, 6)
6-element Vector{Int64}:
 1
 2
 3
 4
 5
 6

If collection is ordered, use append! to add all the elements of another collection to it. The result of the preceding example is equivalent to append!([1, 2, 3], [4, 5, 6]). For AbstractSet objects, union! can be used instead.

See sizehint! for notes about the performance model.

Utility Collections

Core.Pair — Type

Pair(x, y)
x => y

Construct a Pair object with type Pair{typeof(x), typeof(y)}. The elements are stored in the fields first and second. They can also be accessed via iteration (but a Pair is treated as a single "scalar" for broadcasting operations).