ftlDynArray

ftlDynArray is a sequence container that encapsulates dynamic size arrays.

The storage of the dynArray is handled automatically, being expanded and contracted as needed. dynArrays usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a dynArray does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using the Capacity() function. Extra memory can be returned to the system via a call to ShrinkToFit().

Reallocations are usually costly operations in terms of performance. The Reserve() function can be used to eliminate reallocations if the number of elements is known beforehand.

The complexity of common operations on dynArrays is as follows:

Random access: constant O(1)
Insertion or removal of elements at the end: amortized constant O(1)
Insertion or removal of elements: linear in distance to the end of the dynArray O(n)

The Fortran array that is encapsulated by an ftlDynArray instance is available as the data member. Note that data always has the correct size, i.e. the number of elements currently stored, not the number of elements storable before reallocation happens (that would be the capacity). Here is an example snippet that prints the contents of a dynArray of type T.

type(ftlDynArrayT) :: dArr

! note that size(dArr) == dArr%Size() == size(dArr%data)

do i = 1, size(dArr)
   write (*,*) i, dArr%data(i)
enddo

ftlDynArray is basically a Fortran reimplementation of C++'s std::vector. The name was changed because std::vector is a really inappropriate name for something that does not satisfy the mathematical definition of a vector.

Instantiation

Macros

ftlDynArray uses the following macros for instantiation:

FTL_TEMPLATE_TYPE: The type of the objects to be stored in the container, e.g. integer(int64) or MyDerivedType. Do not add the enclosing type() for derived types.
FTL_TEMPLATE_TYPE_IS_DERIVED: This needs to be defined if FTL_TEMPLATE_TYPE is a derived type.
FTL_TEMPLATE_TYPE_MODULE: The name of the module in which FTL_TEMPLATE_TYPE is defined. Specifying this is probably only necessary if FTL_TEMPLATE_TYPE is a derived type, or uses a kind defined in another module, e.g. int64 from the iso_fortran_env module.
FTL_TEMPLATE_TYPE_NAME: A convenient user-readable name for the stored type, e.g. Int. This will be used in the type-name of the dynArray container itself and the module in which it is available, e.g. setting this to Int will result in the type ftlDynArrayInt available in module ftlDynArrayIntModule.
FTL_INSTANTIATE_TEMPLATE: If this macro is defined the template will be instantiated. If not, the template will not be instantiated, but some information about the ftlDynArray container (e.g. its name and the kind of iterator it provides) will be passed on to subsequent template instantiations (e.g. ftlAlgorithms).
FTL_TEMPLATE_TYPE_PROVIDES_FTLMOVE: This macro should be defined if the template type implements the ftlMove method. This is useful for large types containing arrays or owning pointers so that copying would be expensive. The ftlDynArray container will then use the ftlMove method of the template type to move elements around the container, e.g. when shifting everything after erasing an element in the middle.

Specialization for ftlString elements

There is a specialization of the ftlDynArray template for ftlString as the element type. It is accessed by defining FTL_TEMPLATE_TYPE_IS_FTLSTRING:

#define FTL_TEMPLATE_TYPE_IS_FTLSTRING
#define FTL_TEMPLATE_TYPE_NAME String
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

This adds alternative versions for all methods that accept an ftlString as input. The alternative version accepts a plain Fortran character variable as input instead of a ftlString. This in convenient when passing a string literal. Of course the normal versions accepting an ftlString are also available.

use ftlDynArrayStringModule
type(ftlDynArrayString) :: words

words = ['hello','world']
call words%PushBack('of')
call words%PushBack('Fortran')
! ... is much more convenient than ...
words = [ftlString('hello'),ftlString('world')]
call words%PushBack(ftlString('of'))
call words%PushBack(ftlString('Fortran'))
! ... but both versions are totally equivalent

The ftlDynArray template has already been instantiated for ftlStrings in src/instantiations/ftlDynArrayString.f90.

Example instantiations

Example instantiation of a ftlDynArray for integer(int64). The resulting type ftlDynArrayInt is available in ftlDynArrayIntModule.

#define FTL_TEMPLATE_TYPE integer(int64)
#define FTL_TEMPLATE_TYPE_NAME Int
#define FTL_TEMPLATE_TYPE_MODULE iso_fortran_env
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

Example instantiation of a ftnDynArray for a derived type (Point2D) defined in module Point2DModule. The resulting type ftlDynArrayPoint2D is available in ftlDynArrayPoint2DModule.

#define FTL_TEMPLATE_TYPE Point2D
#define FTL_TEMPLATE_TYPE_IS_DERIVED
#define FTL_TEMPLATE_TYPE_MODULE Point2DModule
#define FTL_TEMPLATE_TYPE_NAME Point2D
#define FTL_INSTANTIATE_TEMPLATE
#include "ftlDynArray.F90_template"

Methods and public data members

Construction, destruction & assignment

`ftlDynArray%New()`

Constructs a new ftlDynArray container from a variety of data sources:

Default constructor. Constructs an empty container.

subroutine New(self)
   type(ftlDynArrayT), intent(out) :: self

Example usage:

type(ftlDynArrayInt) :: dArr
call dArr%New() ! empty and size(dArr) == 0

Constructs the container with a size of n, optionally populating it with n copies of val.

subroutine New(self, n, val)
   type(ftlDynArrayT), intent(out)           :: self
   integer           , intent(in)            :: n
   T                 , intent(in) , optional :: val

Example usage:

type(ftlDynArrayInt) :: dArr
call dArr%New(5)     ! array with 5 uninitialized integers
call dArr%New(10, 0) ! with 10 integers of value 0

Copy constructor. Constructs the container with the copy of the contents of other.

subroutine New(self, other)
   type(ftlDynArrayT), intent(out) :: self
   type(ftlDynArrayT), intent(in)  :: other

Example usage:

type(ftlDynArrayInt) :: dArr1, dArr2
call dArr1%New(5, 1)  ! array with 5 integers of value 1
call dArr2%New(dArr1) ! copy of dArr2

Construction from a normal Fortran array.

subroutine New(self, array)
   type(ftlDynArrayT), intent(out) :: self
   T                 , intent(in)  :: array(:)

Example usage:

type(ftlDynArrayInt) :: dArr
call dArr%New([1,5,8,0]) ! size is now 4, values are as specified

`ftlDynArray%Delete()`

Destructs the container. The used storage is deallocated. Note that it is not necessary to call the destructor explicitly. Memory will also be deallocated automatically whenever a dynArray goes out of scope.
subroutine Delete(self)
   type(ftlDynArrayT), intent(inout) :: self
Example usage:
type(ftlDynArrayInt) :: dArr
call dArr%New([1,2,3,4,5,6,7,8]) ! allocates memory for 8 integers
call dArr%Delete()               ! deallocates the allocated memory

`ftlDynArray assignment(=)`

Replaces the contents of the container, modifying its size accordingly. Note that unlike using the corresponding constructors, assignment will only cause a reallocation if the current capacity is not sufficient.
Copy assignment. Replaces the contents with a copy of the contents of other.
subroutine assignment(=)(self, other)
   type(ftlDynArrayT), intent(inout) :: self
   type(ftlDynArrayT), intent(in)    :: other
Array assignment. Replaces the contents with a copy of a normal Fortran array.
subroutine assignment(=)(self, array)
   type(ftlDynArrayT), intent(inout) :: self
   T                 , intent(in)    :: array(:)
Example usage:
type(ftlDynArrayInt) :: dArr1, dArr2
dArr1 = [1,2,3,4] ! assignment also works on uninitialized dynArrays
dArr2 = [5,6,7,8,9,0]
dArr2 = dArr1 ! is now [1,2,3,4] but without reallocation
Note that there is currently no assignment of normal Fortran array from ftlDynArrays. However, this can easily be done by assigning the data member:
type(ftlDynArrayInt) :: dArr
integer :: a(5)
dArr = [5,6,3,2,3]
a = dArr%data

Element access

`ftlDynArray%data`

Provides direct access to the Fortran array underlying the ftlDynArray container. Note that calling the size() intrinsic on the data member yields the same size as calling the ftlDynArray%Size() method on the container itself.

Example usage:
type(ftlDynArrayInt) :: dArr
dArr = [1,2,3,4] ! assignment also works on uninitialized dynArrays
call dArr%PushBack(42)
write (*,*) dArr%data(5) ! prints 42
write (*,*) size(dArr), dArr%Size(), size(dArr%data) ! prints 5 5 5

`ftlDynArray%front`

`ftlDynArray%back`

Provides direct access to first/last element stored in the container.

Example usage:
type(ftlDynArrayInt) :: dArr
dArr = [1,2,3,4] ! assignment also works on uninitialized dynArrays
write (*,*) dArr%front, dArr%back ! prints 1 4

Iterators

`ftlDynArray%Begin()`

`Begin(ftlDynArray)`

Returns a random access iterator to the first element of the container.
ftlDynArrayTIterator function Begin(self)
   type(ftlDynArrayT), intent(in) :: self
If the container is empty, the returned iterator will be equal to End(). Note that this method exists as both type-bound and as a free function.

`ftlDynArray%End()`

`End(ftlDynArray)`

Returns a random access iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.
ftlDynArrayTIterator function End(self)
   type(ftlDynArrayT), intent(in) :: self
Note that this method exists as both type-bound and as a free function.

Capacity

`ftlDynArray%Empty()`

Checks if the container has no elements (i.e. its size is 0). This function does not modify the container in any way. See ftlDynArray%Clear() for a method that deletes the container's contents.
pure logical function Empty(self)
   type(ftlDynArrayT), intent(in) :: self

`ftlDynArray%Size()`

`size(ftlDynArray)`

Returns the number of elements in the container. This is the number of elements currently stored in the container, which is not or equal to the capacity of the container. Note that this method exists as a type-bound procedure as well as a free function which mimics the Fortran size() intrinsic for arrays. This method always returns the same number as calling the size() intrinsic on the ftlDynArray%data member.
pure integer function Size(self)
   type(ftlDynArrayT), intent(in) :: self
Example usage:
type(ftlDynArrayInt) :: dArr
call dArr%New([1,2,3,4,5,6,7])
call dArr%PushBack(42)
write (*,*) dArr%Size(), size(dArr), size(dArr%data) ! prints: 8 8 8

`ftlDynArray%Reserve()`

Increase the capacity of the container to a value that's greater or equal to n. If n is greater than the current capacity, new storage is allocated, otherwise the method does nothing. If n is greater than the current capacity, all iterators and pointers to elements are invalidated. Otherwise, no iterators or pointers are invalidated.
subroutine Reserve(self, n)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: n

`ftlDynArray%Capacity()`

Returns the number of elements that the container has currently allocated space for.
pure integer function Capacity(self)
   type(ftlDynArrayT), intent(in) :: self

`ftlDynArray%ShrinkToFit()`

Reduces the container's capacity to the currently stored number of elements. This releases any additional memory the container the container has allocated to accommodate future growth. If the current capacity is already the container's size, this method does nothing. If reallocation occurs, all iterators are invalidated. If no reallocation takes place, they remain valid.
subroutine ShrinkToFit(self)
   type(ftlDynArrayT), intent(inout) :: self

Modifiers

`ftlDynArray%Clear()`

Removes all elements from the container. Invalidates any pointers, or iterators referring to contained elements. Any past-the-end iterators are also invalidated.
subroutine Clear(self)
   type(ftlDynArrayT), intent(inout) :: self

`ftlDynArray%Resize()`

Resizes the container to contain n elements. If the current size is greater than n, the container is reduced to its first n elements. If the current size is less than n, additional elements are appended and optionally initialized with copies of val.
subroutine Resize(self, n, val)
   type(ftlDynArrayT), intent(inout)        :: self
   integer           , intent(in)           :: n
   T                 , intent(in), optional :: val

`ftlDynArray%PushBack()`

Appends an element to the end of the container. The new element is initialized as a copy of value.
subroutine PushBack(self, val)
   type(ftlDynArrayT), intent(inout) :: self
   T                 , intent(in)    :: val
If the new size is greater than capacity, reallocation happens and all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

`ftlDynArray%PopBack()`

Returns and removes the last element of the container.
T function PopBack(self)
   type(ftlDynArrayT), intent(inout) :: self
Only the past-the-end iterator and the iterator to the removed element are invalidated, all other iterators stay valid.

Calling this method on an empty container is undefined behavior.

`ftlDynArray%Insert()`

Inserts elements at the specified location in the container.

Causes reallocation if the new size is greater than the old capacity. If the new size is greater than capacity, all iterators and references are invalidated. Otherwise, only the iterators and references before the insertion point remain valid. The past-the-end iterator is also invalidated.

There are several versions of the insertion method:
Inserts a copy of val before index pos, meaning data(pos) will become val and all elements behind this one are shifted by one position.
subroutine Insert(self, pos, val)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: pos
   T                 , intent(in)    :: val
Insert a copy of val before iterator it. Basically just like the previous method but takes an iterator instead of an index as the insertion point.
subroutine Insert(self, it, val)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: it
   T                         , intent(in)    :: val
Insert n copies of val before index pos.
subroutine Insert(self, pos, val)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: pos
   integer           , intent(in)    :: n
   T                 , intent(in)    :: val
Insert n copies of val before iterator it. Like the previous method but takes an iterator instead of an index as the insertion point.
subroutine Insert(self, it, n, val)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: it
   integer                   , intent(in)    :: n
   T                         , intent(in)    :: val
Insert a copy of array before index pos.
subroutine Insert(self, pos, array)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: pos
   T                 , intent(in)    :: array(:)
Insert a copy of array before iterator it.
subroutine Insert(self, it, array)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: it
   T                         , intent(in)    :: array(:)
Insert a copy of the elements in the range [first, last) before index pos.
subroutine Insert(self, pos, first, last)
   type(ftlDynArrayT)        , intent(inout) :: self
   integer                   , intent(in)    :: pos
   type(ftlDynArrayTIterator), intent(in)    :: first, last
Insert a copy of the elements in the range [first,``last) before iterator it.
subroutine Insert(self, it, first, last)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: it
   type(ftlDynArrayTIterator), intent(in)    :: first, last

`ftlDynArray%Erase()`

Removes specified elements from the container. Invalidates iterators and references at or after the point of the erase, including the end() iterator.

Note that in contrast to the erase function of C++'s std::vector (which returns an iterator to the element following the last removed) this method is a subroutine and does not return anything. This was done because on Fortran it is not possible to ignore the return value of a function.

TODO: Implement an alternative erase method which corresponds to the erase function of C++'s std::vector.

There are several versions of the erase method:
Erase the element with index pos.
subroutine Erase(self, pos)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: pos
Erase the element referenced by iterator it.
subroutine Erase(self, pos)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: it
Erase the elements in the index range [first, last).
subroutine Erase(self, first, last)
   type(ftlDynArrayT), intent(inout) :: self
   integer           , intent(in)    :: first, last
Erase the elements in the iterator range [first, last).
subroutine Erase(self, first, last)
   type(ftlDynArrayT)        , intent(inout) :: self
   type(ftlDynArrayTIterator), intent(in)    :: first, last

FTL utility methods

`ftlSwap()`

Swaps the contents of two dynArrays.
subroutine ftlSwap(dArr1, dArr2)
   type(ftlDynArrayT), intent(inout) :: dArr1, dArr2
The same effect could also be achieved with assignment (or copy construction):
type(ftlDynArrayInt) :: dArr1, dArr2, tmp
tmp = dArr2
dArr2 = dArr1
dArr1 = tmp
! ^-- same result as ftlSwap(dArr1, dArr2)
Note however, that this way of swapping is an O(N) operation, while ftlSwap is O(1) with a really small prefactor (it only swaps some pointers). Use ftlSwap whenever you want to exchange two dynArrays.

`ftlMove()`

Transfers all the data from one dynArray to another. The source array becomes uninitialized in the process. It's essentially like the Fortran 2003 intrinsic move_alloc, but for ftlDynArrays.
subroutine ftlMove(src, dest)
   type(ftlDynArrayT), intent(inout) :: src
   type(ftlDynArrayT), intent(out)   :: dest
Note that it is not necessary for the template type to implement ftlMove in order for the ftlDynArray to be movable. The ftlDynArray is always movable, no matter if the template type is movable.

It is also possible to move an allocatable Fortran array into a dynArray:
subroutine ftlMove(src, dest)
   T, allocatable    , intent(inout) :: src(:)
   type(ftlDynArrayT), intent(out)   :: dest
The allocatable src becomes deallocated in the process.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ftlDynArray

Instantiation

Macros

Specialization for ftlString elements

Example instantiations

Methods and public data members

Construction, destruction & assignment

`ftlDynArray%New()`

`ftlDynArray%Delete()`

`ftlDynArray assignment(=)`

Element access

`ftlDynArray%data`

`ftlDynArray%front`

`ftlDynArray%back`

Iterators

`ftlDynArray%Begin()`

`Begin(ftlDynArray)`

`ftlDynArray%End()`

`End(ftlDynArray)`

Capacity

`ftlDynArray%Empty()`

`ftlDynArray%Size()`

`size(ftlDynArray)`

`ftlDynArray%Reserve()`

`ftlDynArray%Capacity()`

`ftlDynArray%ShrinkToFit()`

Modifiers

`ftlDynArray%Clear()`

`ftlDynArray%Resize()`

`ftlDynArray%PushBack()`

`ftlDynArray%PopBack()`

`ftlDynArray%Insert()`

`ftlDynArray%Erase()`

FTL utility methods

`ftlSwap()`

`ftlMove()`

Clone this wiki locally