Collections and Data Structures¶
Iteration¶
Sequential iteration is implemented by the methods start()
, done()
, and
next()
. The general for
loop:
for i = I # or "for i in I"
# body
end
is translated into:
state = start(I)
while !done(I, state)
(i, state) = next(I, state)
# body
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.

start
(iter) → state¶ Get initial iteration state for an iterable object.

done
(iter, state) → Bool¶ Test whether we are done iterating.

next
(iter, state) → item, state¶ For a given iterable object and iteration state, return the current item and the next iteration state.

zip
(iters...)¶ For a set of iterable objects, returns an iterable of tuples, where the
i
th tuple contains thei
th component of each input iterable.Note that
zip()
is its own inverse:collect(zip(zip(a...)...)) == collect(a)
.julia> a = 1:5 1:5 julia> b = ["e","d","b","c","a"] 5element Array{String,1}: "e" "d" "b" "c" "a" julia> c = zip(a,b) Base.Zip2{UnitRange{Int64},Array{String,1}}(1:5,String["e","d","b","c","a"]) julia> length(c) 5 julia> first(c) (1,"e")

enumerate
(iter)¶ An iterator that yields
(i, x)
wherei
is a counter starting at 1, andx
is thei
th value from the given iterator. It’s useful when you need not only the valuesx
over which you are iterating, but also the number of iterations so far. Note thati
may not be valid for indexingiter
; it’s also possible thatx != iter[i]
, ifiter
has indices that do not start at 1.julia> a = ["a", "b", "c"]; julia> for (index, value) in enumerate(a) println("$index $value") end 1 a 2 b 3 c

rest
(iter, state)¶ An iterator that yields the same elements as
iter
, but starting at the givenstate
.

countfrom
(start=1, step=1)¶ An iterator that counts forever, starting at
start
and incrementing bystep
.

take
(iter, n)¶ An iterator that generates at most the first
n
elements ofiter
.julia> a = 1:2:11 1:2:11 julia> collect(a) 6element Array{Int64,1}: 1 3 5 7 9 11 julia> collect(take(a,3)) 3element Array{Int64,1}: 1 3 5

drop
(iter, n)¶ An iterator that generates all but the first
n
elements ofiter
.julia> a = 1:2:11 1:2:11 julia> collect(a) 6element Array{Int64,1}: 1 3 5 7 9 11 julia> collect(drop(a,4)) 2element Array{Int64,1}: 9 11

cycle
(iter)¶ An iterator that cycles through
iter
forever.

repeated
(x[, n::Int])¶ An iterator that generates the value
x
forever. Ifn
is specified, generatesx
that many times (equivalent totake(repeated(x), n)
).

iteratorsize
(itertype::Type) → IteratorSize¶ Given the type of an iterator, returns 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()
if there is a known length plus a notion of multidimensional shape (as for an array). In this case thesize
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 implementlength
.This trait is generally used to select between algorithms that preallocate space for their result, and algorithms that resize their result incrementally.

iteratoreltype
(itertype::Type) → IteratorEltype¶ Given the type of an iterator, returns 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, andeltype
would return a meaningful value.
HasEltype()
is the default, since iterators are assumed to implementeltype
.This trait is generally used to select between algorithms that preallocate a specific type of result, and algorithms that pick a result type based on the types of yielded values.
Fully implemented by:
Range
UnitRange
Tuple
Number
AbstractArray
IntSet
ObjectIdDict
Dict
WeakKeyDict
EachLine
AbstractString
Set
Task
General Collections¶

isempty
(collection) → Bool¶ Determine whether a collection is empty (has no elements).
julia> isempty([]) true julia> isempty([1 2 3]) false

empty!
(collection) → collection¶ Remove all elements from a
collection
.

length
(collection) → Integer¶ For ordered, indexable collections, the maximum index
i
for whichgetindex(collection, i)
is valid. For unordered collections, the number of elements.

endof
(collection) → Integer¶ Returns the last index of the collection.
julia> endof([1,2,4]) 3
Fully implemented by:
Range
UnitRange
Tuple
Number
AbstractArray
IntSet
Dict
WeakKeyDict
AbstractString
Set
Iterable Collections¶

in
(item, collection) → Bool¶ 
∈
(item, collection) → Bool¶ 
∋
(collection, item) → Bool¶ 
∉
(item, collection) → Bool¶ 
∌
(collection, item) → 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. Some collections need a slightly different definition; for exampleSet
s check whether the itemisequal()
to one of the elements.Dict
s look for(key,value)
pairs, and the key is compared usingisequal()
. To test for the presence of a key in a dictionary, usehaskey()
ork in keys(dict)
.

eltype
(type)¶ Determine the type of the elements generated by iterating a collection of the given
type
. For associative collection types, this will be aPair{KeyType,ValType}
. The definitioneltype(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.

indexin
(a, b)¶ Returns a vector containing the highest index in
b
for each value ina
that is a member ofb
. The output vector contains 0 wherevera
is not a member ofb
.julia> a = ['a', 'b', 'c', 'b', 'd', 'a']; julia> b = ['a','b','c']; julia> indexin(a,b) 6element Array{Int64,1}: 1 2 3 2 0 1 julia> indexin(b,a) 3element Array{Int64,1}: 6 4 3

findin
(a, b)¶ Returns the indices of elements in collection
a
that appear in collectionb
.julia> a = collect(1:3:15) 5element Array{Int64,1}: 1 4 7 10 13 julia> b = collect(2:4:10) 3element Array{Int64,1}: 2 6 10 julia> findin(a,b) # 10 is the only common element 1element Array{Int64,1}: 4

unique
(itr[, dim])¶ Returns an array containing only the unique elements of the iterable
itr
, in the order that the first of each set of equivalent elements originally appears. Ifdim
is specified, returns unique regions of the arrayitr
alongdim
.

unique
(itr) Returns an array containing one value from
itr
for each unique value, as determined byisequal
.

unique
(f, itr) Returns an array containing one value from
itr
for each unique value produced byf
applied to elements ofitr
.

allunique
(itr)¶ Return
true
if all values fromitr
are distinct when compared withisequal
.

reduce
(op, v0, itr)¶ Reduce the given collection
ìtr
with the given binary operatorop
.v0
must be a neutral element forop
that will be returned for empty collections. It is unspecified whetherv0
is used for nonempty collections.Reductions for certain commonlyused operators have special implementations which should be used instead:
maximum(itr)
,minimum(itr)
,sum(itr)
,prod(itr)
,any(itr)
,all(itr)
.The associativity of the reduction is implementation dependent. This means that you can’t use nonassociative operations like

because it is undefined whetherreduce(,[1,2,3])
should be evaluated as(12)3
or1(23)
. Usefoldl
orfoldr
instead for guaranteed left or right associativity.Some operations accumulate error, and parallelism will also be easier if the reduction can be executed in groups. Future versions of Julia might change the algorithm. Note that the elements are not reordered if you use an ordered collection.

reduce
(op, itr) Like
reduce(op, v0, itr)
. This cannot be used with empty collections, except for some special cases (e.g. whenop
is one of+
,*
,max
,min
,&
,
) when Julia can determine the neutral element ofop
.

foldl
(op, v0, itr)¶ Like
reduce()
, but with guaranteed left associativity.v0
will be used exactly once.

foldl
(op, itr) Like
foldl(op, v0, itr)
, but using the first element ofitr
asv0
. In general, this cannot be used with empty collections (seereduce(op, itr)
).

foldr
(op, v0, itr)¶ Like
reduce()
, but with guaranteed right associativity.v0
will be used exactly once.

foldr
(op, itr) Like
foldr(op, v0, itr)
, but using the last element ofitr
asv0
. In general, this cannot be used with empty collections (seereduce(op, itr)
).

maximum
(itr)¶ Returns the largest element in a collection.
julia> maximum(20.5:10) 9.5 julia> maximum([1,2,3]) 3

maximum
(A, dims) Compute the maximum value of an array over the given dimensions.

maximum!
(r, A)¶ Compute the maximum value of
A
over the singleton dimensions ofr
, and write results tor
.

minimum
(itr)¶ Returns the smallest element in a collection.
julia> minimum(20.5:10) 20.5 julia> minimum([1,2,3]) 1

minimum
(A, dims) Compute the minimum value of an array over the given dimensions.

minimum!
(r, A)¶ Compute the minimum value of
A
over the singleton dimensions ofr
, and write results tor
.

extrema
(itr) → Tuple¶ Compute both the minimum and maximum element in a single pass, and return them as a 2tuple.
julia> extrema(2:10) (2,10) julia> extrema([9,pi,4.5]) (3.141592653589793,9.0)

extrema
(A, dims) → Array{Tuple} Compute the minimum and maximum elements of an array over the given dimensions.

indmax
(itr) → Integer¶ Returns the index of the maximum element in a collection. The collection must not be empty.
julia> indmax([8,0.1,9,pi]) 1

indmin
(itr) → Integer¶ Returns the index of the minimum element in a collection. The collection must not be empty.
julia> indmin([8,0.1,9,pi]) 3

findmax
(itr) → (x, index)¶ Returns the maximum element and its index. The collection must not be empty.
julia> findmax([8,0.1,9,pi]) (8.0,1)

findmax
(A, region) → (maxval, index) For an array input, returns the value and index of the maximum over the given region.

findmin
(itr) → (x, index)¶ Returns the minimum element and its index. The collection must not be empty.
julia> findmin([8,0.1,9,pi]) (9.0,3)

findmin
(A, region) → (minval, index) For an array input, returns the value and index of the minimum over the given region.

findmax!
(rval, rind, A[, init=true]) → (maxval, index)¶ Find the maximum of
A
and the corresponding linear index along singleton dimensions ofrval
andrind
, and store the results inrval
andrind
.

findmin!
(rval, rind, A[, init=true]) → (minval, index)¶ Find the minimum of
A
and the corresponding linear index along singleton dimensions ofrval
andrind
, and store the results inrval
andrind
.

maxabs
(itr)¶ Compute the maximum absolute value of a collection of values.
julia> maxabs([1, 3, 4*im]) 4.0

maxabs
(A, dims) Compute the maximum absolute values over given dimensions.

maxabs!
(r, A)¶ Compute the maximum absolute values over the singleton dimensions of
r
, and write values tor
.

minabs
(itr)¶ Compute the minimum absolute value of a collection of values.
julia> minabs([1, 3, 4*im]) 1.0

minabs
(A, dims) Compute the minimum absolute values over given dimensions.

minabs!
(r, A)¶ Compute the minimum absolute values over the singleton dimensions of
r
, and write values tor
.

sum
(itr)¶ Returns the sum of all elements in a collection.

sum
(A, dims) Sum elements of an array over the given dimensions.

sum!
(r, A)¶ Sum elements of
A
over the singleton dimensions ofr
, and write results tor
.

sum
(f, itr) Sum the results of calling function
f
on each element ofitr
.

sumabs
(itr)¶ Sum absolute values of all elements in a collection. This is equivalent to
sum(abs(itr))
but faster.

sumabs
(A, dims) Sum absolute values of elements of an array over the given dimensions.

sumabs!
(r, A)¶ Sum absolute values of elements of
A
over the singleton dimensions ofr
, and write results tor
.

sumabs2
(itr)¶ Sum squared absolute values of all elements in a collection. This is equivalent to
sum(abs2(itr))
but faster.

sumabs2
(A, dims) Sum squared absolute values of elements of an array over the given dimensions.

sumabs2!
(r, A)¶ Sum squared absolute values of elements of
A
over the singleton dimensions ofr
, and write results tor
.

prod
(itr)¶ Returns the product of all elements of a collection.

prod
(A, dims) Multiply elements of an array over the given dimensions.

prod!
(r, A)¶ Multiply elements of
A
over the singleton dimensions ofr
, and write results tor
.

any
(itr) → Bool¶ Test whether any elements of a boolean collection are
true
.

any
(A, dims) Test whether any values along the given dimensions of an array are
true
.

any!
(r, A)¶ Test whether any values in
A
along the singleton dimensions ofr
aretrue
, and write results tor
.

all
(itr) → Bool¶ Test whether all elements of a boolean collection are
true
.

all
(A, dims) Test whether all values along the given dimensions of an array are
true
.

all!
(r, A)¶ Test whether all values in
A
along the singleton dimensions ofr
aretrue
, and write results tor
.

count
(p, itr) → Integer¶ Count the number of elements in
itr
for which predicatep
returnstrue
.julia> count(i>(4<=i<=6), [2,3,4,5,6]) 3

any
(p, itr) → Bool Determine whether predicate
p
returnstrue
for any elements ofitr
.julia> any(i>(4<=i<=6), [3,5,7]) true

all
(p, itr) → Bool Determine whether predicate
p
returnstrue
for all elements ofitr
.julia> all(i>(4<=i<=6), [4,5,6]) true

foreach
(f, c...) → Void¶ Call function
f
on each element of iterablec
. For multiple iterable arguments,f
is called elementwise.foreach
should be used instead ofmap
when the results off
are not needed, for example inforeach(println, array)
.julia> a = 1:3:7; julia> foreach(x>println(x^2),a) 1 16 49

map
(f, c...) → collection¶ Transform collection
c
by applyingf
to each element. For multiple collection arguments, applyf
elementwise.julia> map((x) > x * 2, [1, 2, 3]) 3element Array{Int64,1}: 2 4 6 julia> map(+, [1, 2, 3], [10, 20, 30]) 3element Array{Int64,1}: 11 22 33

map!
(function, collection)¶ Inplace version of
map()
.

map!
(function, destination, collection...) Like
map()
, but stores the result indestination
rather than a new collection.destination
must be at least as large as the first collection.

mapreduce
(f, op, v0, itr)¶ Apply function
f
to each element initr
, and then reduce the result using the binary functionop
.v0
must be a neutral element forop
that will be returned for empty collections. It is unspecified whetherv0
is used for nonempty collections.mapreduce()
is functionally equivalent to callingreduce(op, v0, map(f, itr))
, but will in general execute faster since no intermediate collection needs to be created. See documentation forreduce()
andmap()
.julia> mapreduce(x>x^2, +, [1:3;]) # == 1 + 4 + 9 14
The associativity of the reduction is implementationdependent. Additionally, some implementations may reuse the return value of
f
for elements that appear multiple times initr
. Usemapfoldl()
ormapfoldr()
instead for guaranteed left or right associativity and invocation off
for every value.

mapreduce
(f, op, itr) Like
mapreduce(f, op, v0, itr)
. In general, this cannot be used with empty collections (seereduce(op, itr)
).

mapfoldl
(f, op, v0, itr)¶ Like
mapreduce()
, but with guaranteed left associativity.v0
will be used exactly once.

mapfoldl
(f, op, itr) Like
mapfoldl(f, op, v0, itr)
, but using the first element ofitr
asv0
. In general, this cannot be used with empty collections (seereduce(op, itr)
).

mapfoldr
(f, op, v0, itr)¶ Like
mapreduce()
, but with guaranteed right associativity.v0
will be used exactly once.

mapfoldr
(f, op, itr) Like
mapfoldr(f, op, v0, itr)
, but using the first element ofitr
asv0
. In general, this cannot be used with empty collections (seereduce(op, itr)
).

first
(coll)¶ Get the first element of an iterable collection. Returns the start point of a
Range
even if it is empty.

last
(coll)¶ Get the last element of an ordered collection, if it can be computed in O(1) time. This is accomplished by calling
endof()
to get the last index. Returns the end point of aRange
even if it is empty.

step
(r)¶ Get the step size of a
Range
object.julia> step(1:10) 1 julia> step(1:2:10) 2 julia> step(2.5:0.3:10.9) 0.3 julia> step(linspace(2.5,10.9,85)) 0.1

collect
(collection)¶ Return an
Array
of all items in a collection or iterator. For associative collections, returnsPair{KeyType, ValType}
. If the argument is arraylike or is an iterator with theHasShape()
trait, the result will have the same shape and number of dimensions as the argument.

collect
(element_type, collection) Return an
Array
with the given element type of all items in a collection or iterable. The result has the same shape and number of dimensions ascollection
.

issubset
(a, b)¶ 
⊆
(a, b) → Bool¶ 
⊈
(a, b) → Bool¶ 
⊊
(a, b) → Bool¶ Determine whether every element of
a
is also inb
, usingin()
.

filter
(function, collection)¶ Return a copy of
collection
, removing elements for whichfunction
isfalse
. For associative collections, the function is passed two arguments (key and value).julia> a = 1:10 1:10 julia> filter(isodd, a) 5element Array{Int64,1}: 1 3 5 7 9

filter!
(function, collection)¶ Update
collection
, removing elements for whichfunction
isfalse
. For associative collections, the function is passed two arguments (key and value).
Indexable Collections¶

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 togetindex(a, i, j, ...)
.

setindex!
(collection, value, key...)¶ Store the given value at the given key or index within a collection. The syntax
a[i,j,...] = x
is converted by the compiler to(setindex!(a, x, i, j, ...); x)
.
Fully implemented by:
Array
BitArray
AbstractArray
SubArray
ObjectIdDict
Dict
WeakKeyDict
AbstractString
Partially implemented by:
Range
UnitRange
Tuple
Associative Collections¶
Dict
is the standard associative collection. 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.
ObjectIdDict
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.
Dict
s 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)
.
Dict
s 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 keyvalue 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)
.

Dict
([itr])¶ Dict{K,V}()
constructs a hash table with keys of typeK
and values of typeV
.Given a single iterable argument, constructs a
Dict
whose keyvalue pairs are taken from 2tuples(key,value)
generated by the argument.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

haskey
(collection, key) → Bool¶ Determine whether a collection has a mapping for a given key.

get
(collection, key, default)¶ Return the value stored for the given key, or the given default value if no mapping for the key is present.

get
(f::Function, collection, key) Return the value stored for the given key, or if no mapping for the key is present, return
f()
. Useget!()
to also store the default value in the dictionary.This is intended to be called using
do
block syntaxget(dict, key) do # default value calculated here time() end

get!
(collection, key, default)¶ Return the value stored for the given key, or if no mapping for the key is present, store
key => default
, and returndefault
.

get!
(f::Function, collection, key) Return the value stored for the given key, or if no mapping for the key is present, store
key => f()
, and returnf()
.This is intended to be called using
do
block syntax:get!(dict, key) do # default value calculated here time() end

getkey
(collection, key, default)¶ Return the key matching argument
key
if one exists incollection
, otherwise returndefault
.

delete!
(collection, key)¶ Delete the mapping for the given key in a collection, and return the collection.

pop!
(collection, key[, default])¶ Delete and return the mapping for
key
if it exists incollection
, otherwise returndefault
, or throw an error if default is not specified.

keys
(collection)¶ Return an iterator over all keys in a collection.
collect(keys(d))
returns an array of keys.

values
(collection)¶ Return an iterator over all values in a collection.
collect(values(d))
returns an array of values.

merge
(collection, others...)¶ Construct a merged collection from the given collections. If necessary, the types of the resulting collection will be promoted to accommodate the types of the merged collections. If the same key is present in another collection, the value for that key will be the value it has in the last collection listed.
julia> a = Dict("foo" => 0.0, "bar" => 42.0) Dict{String,Float64} with 2 entries: "bar" => 42.0 "foo" => 0.0 julia> b = Dict("baz" => 17, "bar" => 4711) Dict{String,Int64} with 2 entries: "bar" => 4711 "baz" => 17 julia> merge(a, b) Dict{String,Float64} with 3 entries: "bar" => 4711.0 "baz" => 17.0 "foo" => 0.0 julia> merge(b, a) Dict{String,Float64} with 3 entries: "bar" => 42.0 "baz" => 17.0 "foo" => 0.0

merge!
(collection, others...)¶ Update collection with pairs from the other collections.

sizehint!
(s, n)¶ Suggest that collection
s
reserve capacity for at leastn
elements. This can improve performance.

keytype
(type)¶ Get the key type of an associative collection type. Behaves similarly to
eltype
.

valtype
(type)¶ Get the value type of an associative collection type. Behaves similarly to
eltype
.
Fully implemented by:
ObjectIdDict
Dict
WeakKeyDict
Partially implemented by:
IntSet
Set
EnvHash
Array
BitArray
SetLike Collections¶

Set
([itr])¶ Construct a
Set
of the values generated by the given iterable object, or an empty set. Should be used instead ofIntSet
for sparse integer sets, or for sets of arbitrary objects.

IntSet
([itr])¶ Construct a sorted set of positive
Int
s generated by the given iterable object, or an empty set. Implemented as a bit string, and therefore designed for dense integer sets. OnlyInt
s greater than 0 can be stored. If the set will be sparse (for example holding a few very large integers), useSet
instead.

union
(s1, s2...)¶ 
∪
(s1, s2...)¶ Construct the union of two or more sets. Maintains order with arrays.

union!
(s, iterable)¶ Union each element of
iterable
into sets
inplace.

intersect
(s1, s2...)¶ 
∩
(s1, s2)¶ Construct the intersection of two or more sets. Maintains order and multiplicity of the first argument for arrays and ranges.

setdiff
(a, b)¶ Construct the set of elements in
a
but notb
. Maintains order with arrays. Note that both arguments must be collections, and both will be iterated over. In particular,setdiff(set,element)
whereelement
is a potential member ofset
, will not work in general.julia> setdiff([1,2,3],[3,4,5]) 2element Array{Int64,1}: 1 2

setdiff!
(s, iterable)¶ Remove each element of
iterable
from sets
inplace.

symdiff
(a, b, rest...)¶ Construct the symmetric difference of elements in the passed in sets or arrays. Maintains order with arrays.
julia> symdiff([1,2,3],[3,4,5],[4,5,6]) 3element Array{Int64,1}: 1 2 6

symdiff!
(s, n)¶ The set
s
is destructively modified to toggle the inclusion of integern
.

symdiff!
(s, itr) For each element in
itr
, destructively toggle its inclusion in sets
.

symdiff!
(s1, s2) Construct the symmetric difference of sets
s1
ands2
, storing the result ins1
.

intersect!
(s1, s2)¶ Intersects sets
s1
ands2
and overwrites the sets1
with the result. If needed,s1
will be expanded to the size ofs2
.

issubset
(A, S) → Bool 
⊆
(A, S) → Bool Return
true
ifA
is a subset of or equal toS
.
Fully implemented by:
IntSet
Set
Partially implemented by:
Array
Dequeues¶

push!
(collection, items...) → collection¶ Insert one or more
items
at the end ofcollection
.julia> push!([1, 2, 3], 4, 5, 6) 6element Array{Int64,1}: 1 2 3 4 5 6
Use
append!()
to add all the elements of another collection tocollection
. The result of the preceding example is equivalent toappend!([1, 2, 3], [4, 5, 6])
.

pop!
(collection) → item Remove the last item in
collection
and return it.julia> A=[1, 2, 3, 4, 5, 6] 6element Array{Int64,1}: 1 2 3 4 5 6 julia> pop!(A) 6 julia> A 5element Array{Int64,1}: 1 2 3 4 5

unshift!
(collection, items...) → collection¶ Insert one or more
items
at the beginning ofcollection
.julia> unshift!([1, 2, 3, 4], 5, 6) 6element Array{Int64,1}: 5 6 1 2 3 4

shift!
(collection) → item¶ Remove the first
item
fromcollection
.julia> A = [1, 2, 3, 4, 5, 6] 6element Array{Int64,1}: 1 2 3 4 5 6 julia> shift!(A) 1 julia> A 5element Array{Int64,1}: 2 3 4 5 6

insert!
(collection, index, item)¶ Insert an
item
intocollection
at the givenindex
.index
is the index ofitem
in the resultingcollection
.julia> insert!([6, 5, 4, 2, 1], 4, 3) 6element Array{Int64,1}: 6 5 4 3 2 1

deleteat!
(a::Vector, i::Integer)¶ Remove the item at the given
i
and return the modifieda
. Subsequent items are shifted to fill the resulting gap.julia> deleteat!([6, 5, 4, 3, 2, 1], 2) 5element Array{Int64,1}: 6 4 3 2 1

deleteat!
(a::Vector, inds) Remove the items at the indices given by
inds
, and return the modifieda
. Subsequent items are shifted to fill the resulting gap.inds
must be sorted and unique.julia> deleteat!([6, 5, 4, 3, 2, 1], 1:2:5) 3element Array{Int64,1}: 5 3 1 julia> deleteat!([6, 5, 4, 3, 2, 1], (2, 2)) ERROR: ArgumentError: indices must be unique and sorted in deleteat!(::Array{Int64,1}, ::Tuple{Int64,Int64}) at ./array.jl:614 ...

splice!
(collection, index[, replacement]) → item¶ Remove the item at the given index, and return the removed item. Subsequent items are shifted down to fill the resulting gap. If specified, replacement values from an ordered collection will be spliced in place of the removed item.
julia> A = [6, 5, 4, 3, 2, 1]; splice!(A, 5) 2 julia> A 5element Array{Int64,1}: 6 5 4 3 1 julia> splice!(A, 5, 1) 1 julia> A 5element Array{Int64,1}: 6 5 4 3 1 julia> splice!(A, 1, [1, 2, 3]) 6 julia> A 7element Array{Int64,1}: 1 2 3 5 4 3 1
To insert
replacement
before an indexn
without removing any items, usesplice!(collection, n:n1, replacement)
.

splice!
(collection, range[, replacement]) → items Remove items in the specified index range, and return a collection containing the removed items. Subsequent items are shifted down to fill the resulting gap. If specified, replacement values from an ordered collection will be spliced in place of the removed items.
To insert
replacement
before an indexn
without removing any items, usesplice!(collection, n:n1, replacement)
.julia> splice!(A, 4:3, 2) 0element Array{Int64,1} julia> A 8element Array{Int64,1}: 1 2 3 2 5 4 3 1

resize!
(collection, n) → collection¶ Resize
collection
to containn
elements. Ifn
is smaller than the current collection length, the firstn
elements will be retained. Ifn
is larger, the new elements are not guaranteed to be initialized.julia> resize!([6, 5, 4, 3, 2, 1], 3) 3element Array{Int64,1}: 6 5 4
julia> resize!([6, 5, 4, 3, 2, 1], 8) 8element Array{Int64,1}: 6 5 4 3 2 1 0 0

append!
(collection, collection2) → collection.¶ Add the elements of
collection2
to the end ofcollection
.julia> append!([1],[2,3]) 3element Array{Int64,1}: 1 2 3
julia> append!([1, 2, 3], [4, 5, 6]) 6element Array{Int64,1}: 1 2 3 4 5 6
Use
push!()
to add individual items tocollection
which are not already themselves in another collection. The result is of the preceding example is equivalent topush!([1, 2, 3], 4, 5, 6)
.

prepend!
(collection, items) → collection¶ Insert the elements of
items
to the beginning ofcollection
.julia> prepend!([3],[1,2]) 3element Array{Int64,1}: 1 2 3
Fully implemented by:
Vector
(a.k.a. 1dimensionalArray
)BitVector
(a.k.a. 1dimensionalBitArray
)
PriorityQueue¶
The PriorityQueue
type is available from the Collections
module. It provides
a basic priority queue implementation allowing for arbitrary key and priority types.
Multiple identical keys are not permitted, but the priority of existing keys can be
changed efficiently.

PriorityQueue
(K, V[, ord])¶ Construct a new
PriorityQueue
, with keys of typeK
and values/priorites of typeV
. If an order is not given, the priority queue is minordered using the default comparison forV
.A
PriorityQueue
acts like aDict
, mapping values to their priorities, with the addition of adequeue!
function to remove the lowest priority element.julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward) Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries: "c" => 1 "b" => 3 "a" => 2

enqueue!
(pq, k, v)¶ Insert the a key
k
into a priority queuepq
with priorityv
.julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward) Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries: "c" => 1 "b" => 3 "a" => 2 julia> Base.Collections.enqueue!(a, "d", 4) Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 4 entries: "c" => 1 "b" => 3 "a" => 2 "d" => 4

dequeue!
(pq)¶ Remove and return the lowest priority key from a priority queue.
julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward) Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries: "c" => 1 "b" => 3 "a" => 2 julia> Base.Collections.dequeue!(a) "c" julia> a Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries: "b" => 3 "a" => 2

peek
(pq)¶ Return the lowest priority key from a priority queue without removing that key from the queue.
PriorityQueue
also behaves similarly to a Dict
in that keys can be
inserted and priorities accessed or changed using indexing notation.
julia> # Julia code
pq = Collections.PriorityQueue();
julia> # Insert keys with associated priorities
pq["a"] = 10; pq["b"] = 5; pq["c"] = 15; pq
Base.Collections.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
"c" => 15
"b" => 5
"a" => 10
julia> # Change the priority of an existing key
pq["a"] = 0; pq
Base.Collections.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
"c" => 15
"b" => 5
"a" => 0
Heap Functions¶
Along with the PriorityQueue
type, the Collections
module provides
lower level functions for performing binary heap operations on arrays. Each
function takes an optional ordering argument. If not given, default ordering
is used, so that elements popped from the heap are given in ascending order.

heapify
(v, ord::Ordering=Forward)¶ Returns a new vector in binary heap order, optionally using the given ordering.
julia> a = [1,3,4,5,2]; julia> Base.Collections.heapify(a) 5element Array{Int64,1}: 1 2 4 5 3 julia> Base.Collections.heapify(a, Base.Order.Reverse) 5element Array{Int64,1}: 5 3 4 1 2

heapify!
(v, ord::Ordering=Forward)¶ Inplace
heapify()
.

isheap
(v, ord::Ordering=Forward)¶ Return
true
if an array is heapordered according to the given order.julia> a = [1,2,3] 3element Array{Int64,1}: 1 2 3 julia> Base.Collections.isheap(a,Base.Order.Forward) true julia> Base.Collections.isheap(a,Base.Order.Reverse) false

heappush!
(v, x[, ord])¶ Given a binary heapordered array, push a new element
x
, preserving the heap property. For efficiency, this function does not check that the array is indeed heapordered.

heappop!
(v[, ord])¶ Given a binary heapordered array, remove and return the lowest ordered element. For efficiency, this function does not check that the array is indeed heapordered.