How to build data structures on Arrays without specifying the array implementation?

General Usage
1

I’ve built some data structures on Vectors, and now realize I should be using views instead. The problem is that I need indexing operations to return another container. How do I modify my struct definitions to achieve this? Example:

struct Container{T} 
   box::Vector{T} 
   ...
end 
# other code requires that container[idx] returns another container: 
Base.getindex(c::Container{T}, idx) where {T}= Container{T}(c.box[idx])

My first thought (after google searching failed) was to attempt to abstract over the vector type:

struct Container{A,T} 
    box::A{T} 
end

thinking I could recover the original struct with c=Container{Vector,T}, but this gives an error I don’t understand:

ERROR: TypeError: in Type{...} expression, expected UnionAll, got a value of type TypeVar

I suppose the larger question is: How does one write datatypes with generic arrays? Thanks!

2

If it supports getindex, possibly struct Container{T} should be a subtype of AbstractVector? Then the caller can use @views to do slicing with views and it will create a SubArray{Container}.

Alternatively, you can declare it as:

struct Container{T<:AbstractVector} 
   box::T
   ...
end

and then you can just store a view (SubArray) if you want:

Base.getindex(c::Container, idx) = Container(@view c.box[idx])
1 Like
3

But this seems to hide the element type. Is there a way to do as you suggest, but still have access to the element type of the Vector?

4

It seems that you just want to use AbstractVector instead of vector:

struct Foo{T}
  v:: AbstractVector{T}
end

v = [1,2,3]
x = Foo(v)
y = Foo(@view v[2:3])

Edit: just for the records, this is not a good idea because fields with abstract types lead to performance losses, as pointed below (and above, implicitly). Honestly I made a confusion at that moment in which I imagined (wrongly) that the instance of the struct would assume the specific type of the value used in the generator (as functions specialize for them). Of course it does not.

5

Having an abstract field type like that will significantly harm performance. Instead, you can do:

struct Foo{T, V <: AbstractVector{T}}
  v::V 
end

if you want the element type T to be an explicit type parameter.

Also note that this isn’t strictly necessary. You can use @stevengj’s suggestion and implement Base.eltype for your Container with no loss of performance or expressiveness.

4 Likes
6

Base.eltype(c::Container) = eltype(c.box) works and is fast (it will evaluate to a compile-time constant).

1 Like
7

Thanks; exactly what I was looking for! And placing the new type parameter at the tail of the Foo{…} signature, as you showed, obviated any changes to the calling code. This made it trivial to use views instead of Vectors, my ultimate goal.

2 Likes