Array list is a growable, dynamic array with elements inside Elements are stored in an array, and are copied when resizing needs to happen Accessing elements is \(O(1)\) Adding elements is worst case \(O(N)\) Removing elements while preserving order is \(O(N)\) Removing elements while not preserving order is \(O(1)\). More...

#include <array_list.hpp>

Inheritance diagram for mtcore::ArrayList< T >:

[legend]

Public Types
using	Elem = T

Public Member Functions
decltype(auto)	ptr_iter () noexcept
	Gets iterator over pointers to elements.

decltype(auto)	ptr_iter () const noexcept
	Gets iterator over const pointers to elements.

decltype(auto)	iter () const noexcept
	Gets iterator over values.

Result< void, AllocationError >	init (Allocator &alloc, size_t initCapacity=10) noexcept
	Initializes an empty ArrayList with an initial capacity.

Result< void, AllocationError >	init (Allocator &alloc, std::initializer_list< T > init, size_t capacity=0) noexcept
	Initializes an array list with specified elements.

void	deinit (Allocator &alloc) noexcept
	Cleans up any memory held by array list.

Result< void, AllocationError >	push (Allocator &alloc, const Slice< std::add_const_t< T > > &elems) noexcept
	Pushes a list of items onto an array list.

Result< void, AllocationError >	push (Allocator &alloc, const Slice< std::remove_const_t< T > > &elems) noexcept
	Pushes a list of items onto an array list.

Result< void, AllocationError >	push (Allocator &alloc, const T &elem) noexcept
	Pushes an item onto an array list.

size_t	size () const noexcept
	Gets the size of an array list.

size_t	capacity () const noexcept
	Array list capacity.

Result< void, AllocationError >	reserve (Allocator &alloc, const size_t newSize) noexcept
	Will grow the capacity to be at least newSize large.

Result< void, AllocationError >	shrink_to_fit (Allocator &alloc) noexcept
	Will shrink the capacity to match the current size.

Result< void, CollectionAddNoAllocationError >	push (const Slice< std::remove_const_t< T > > &elems) noexcept
	Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Result< void, CollectionAddNoAllocationError >	push (const Slice< std::add_const_t< T > > &elems) noexcept
	Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Result< void, CollectionAddNoAllocationError >	push (const T &elem) noexcept
	Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Result< void, AllocationError >	unshift (const T &elem) noexcept
	Adds an element to the front, and shifts all other elements down by 1 If there is not enough room, will Result in a failure.

Result< void, AllocationError >	unshift (Allocator &alloc, const T &elem) noexcept
	Adds an element to the front, and shifts all other elements down by 1 If there is not enough room, will try to allocate more room.

Optional< T >	shift () noexcept
	Removes the first element and shifts all remaining elements down.

Optional< T >	pop () noexcept
	Pops the last element and returns it Will return an error if there is no element.

T &	at (size_t index) noexcept
	Get element at an index.

const T &	at (size_t index) const noexcept
	Get element at an index.

T &	operator[] (size_t index) noexcept
	Get element at an index.

const T &	operator[] (size_t index) const noexcept
	Get element at an index.

T	swap_remove (size_t index) noexcept
	Removes the element at an index (must be present) Does NOT preserve ordering Will swap the removed element with the last element and then pop Completes in \(O(1)\).

T	shift_remove (size_t index) noexcept
	Removes the element at an index (must be present) Does preserve ordering Will shift all remaining elements over by one Completes in \(O(N)\).

Slice< T >	slice ()
	Gets a slice over the underlying elements.

Slice< std::add_const_t< T > >	slice () const
	Gets a slice over the underlying elements.

Detailed Description

template<typename T>
struct mtcore::ArrayList< T >

Array list is a growable, dynamic array with elements inside Elements are stored in an array, and are copied when resizing needs to happen Accessing elements is \(O(1)\) Adding elements is worst case \(O(N)\) Removing elements while preserving order is \(O(N)\) Removing elements while not preserving order is \(O(1)\).

Template Parameters

T	Elements to store

Definition at line 46 of file array_list.hpp.

Member Typedef Documentation

◆ Elem

template<typename T>

using mtcore::ArrayList< T >::Elem = T

Definition at line 52 of file array_list.hpp.

Member Function Documentation

◆ at() [1/2]

template<typename T>

const T & mtcore::ArrayList< T >::at ( size_t index ) const

inlinenodiscardnoexcept

Get element at an index.

Parameters

index Element index to get

Returns: Element reference

Definition at line 391 of file array_list.hpp.

                                                           {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

◆ at() [2/2]

template<typename T>

T & mtcore::ArrayList< T >::at ( size_t index )

inlinenodiscardnoexcept

Get element at an index.

Parameters

index Element index to get

Returns: Element reference

Definition at line 381 of file array_list.hpp.

                                               {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

◆ capacity()

template<typename T>

size_t mtcore::ArrayList< T >::capacity ( ) const

inlinenodiscardnoexcept

Array list capacity.

Returns: capacity of array list

Definition at line 199 of file array_list.hpp.

                                                   {
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      return elements.len;
    }

Here is the caller graph for this function:

◆ deinit()

template<typename T>

void mtcore::ArrayList< T >::deinit ( Allocator & alloc )

inlinenoexcept

Cleans up any memory held by array list.

Parameters

alloc Allocator to use for cleanup

Definition at line 122 of file array_list.hpp.

                                           {
      if (elements.head != nullptr) {
        alloc.destroy_many(elements);
        elements.head = nullptr;
      }
      elements.len = 0;
    }

◆ init() [1/2]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::init	(	Allocator &	alloc,
		size_t	initCapacity = 10 )

inlinenodiscardnoexcept

Initializes an empty ArrayList with an initial capacity.

Parameters

alloc	Allocator to use for initial allocation
initCapacity	(Optional) Initial capacity to have (defaults to 10)

Returns: success or failure

Definition at line 76 of file array_list.hpp.

                                                                                                          {
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      initCapacity  = initCapacity ? initCapacity : 10;
      auto allocRes = alloc.create_many<T>(initCapacity);
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements = *allocRes;
      return success();
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init() [2/2]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::init	(	Allocator &	alloc,
		std::initializer_list< T >	init,
		size_t	capacity = 0 )

inlinenodiscardnoexcept

Initializes an array list with specified elements.

Parameters

alloc	Allocator to use for initial allocation
init	Initial value list
capacity	(Optional) initial capacity (if bigger than the initial value list)

Returns: success or failure

Definition at line 96 of file array_list.hpp.

                                                                                   {
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      if (capacity < init.size()) {
        capacity = init.size();
      }
      capacity      = capacity ? capacity : 10;
      auto allocRes = alloc.create_many<T>(init.size());
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements     = *allocRes;
      size_t index = 0;
      for (const auto &elem: init) {
        elements[index++] = elem;
      }
      count = index;
 
      return success();
    }

Here is the call graph for this function:

◆ iter()

template<typename T>

decltype(auto) mtcore::ArrayList< T >::iter ( ) const

inlinenodiscardnoexcept

Gets iterator over values.

Returns: Iterator

Definition at line 68 of file array_list.hpp.

68{ return iter::val(*this); }

mtcore::iter::val

ValIter< T > val(const T &r)

Generic value iterator that uses the operator[] and incrementing indexes to iterate over a collection...

Definition iter.hpp:114

Here is the call graph for this function:

◆ operator[]() [1/2]

template<typename T>

const T & mtcore::ArrayList< T >::operator[] ( size_t index ) const

inlinenoexcept

Get element at an index.

Parameters

index Element index to get

Returns: Element reference

Definition at line 411 of file array_list.hpp.

                                                     {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

◆ operator[]() [2/2]

template<typename T>

T & mtcore::ArrayList< T >::operator[] ( size_t index )

inlinenoexcept

Get element at an index.

Parameters

index Element index to get

Returns: Element reference

Definition at line 401 of file array_list.hpp.

                                         {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

◆ pop()

template<typename T>

Optional< T > mtcore::ArrayList< T >::pop ( )

inlinenoexcept

Pops the last element and returns it Will return an error if there is no element.

Returns: The element that was removed, or the error EMPTY

Definition at line 367 of file array_list.hpp.

                               {
      ensure(elements.head, "NOT INITIALIZED");
      if (count == 0) {
        return nullopt;
      }
      --count;
      return elements[count];
    }

Here is the caller graph for this function:

◆ ptr_iter() [1/2]

template<typename T>

decltype(auto) mtcore::ArrayList< T >::ptr_iter ( ) const

inlinenodiscardnoexcept

Gets iterator over const pointers to elements.

Returns: Iterator

Definition at line 63 of file array_list.hpp.

63{ return iter::const_ptr(*this); }

mtcore::iter::const_ptr

ConstPtrIter< T > const_ptr(const T &r)

Generic constant pointer iterator that uses the operator[] and incrementing indexes to iterate over a...

Definition iter.hpp:128

Here is the call graph for this function:

◆ ptr_iter() [2/2]

template<typename T>

decltype(auto) mtcore::ArrayList< T >::ptr_iter ( )

inlinenodiscardnoexcept

Gets iterator over pointers to elements.

Returns: Iterator

Definition at line 58 of file array_list.hpp.

58{ return iter::ptr(*this); }

mtcore::iter::ptr

PtrIter< T > ptr(T &r)

Generic pointer iterator that uses the operator[] and incrementing indexes to iterate over a collecti...

Definition iter.hpp:101

Here is the call graph for this function:

◆ push() [1/6]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::push	(	Allocator &	alloc,
		const Slice< std::add_const_t< T > > &	elems )

inlinenodiscardnoexcept

Pushes a list of items onto an array list.

If there is no more room, will allocate a new list and do a copy If allocation fails, will return a failure

Parameters

alloc	Allocator to use for potential allocations
elems	Elements to add

Returns: Success or failure (failure happens if ArrayList cannot get more memory)

Definition at line 138 of file array_list.hpp.

                                                                                                     {
      ensure(elements.head, "NOT INITIALIZED");
      if (count + elems.size() >= elements.len) {
        size_t newSize = elements.len + std::max(((elements.len + 1) / 2), elems.size());
        if (auto res = reserve(alloc, newSize); res.is_error()) {
          return res;
        }
      }
 
      ensure(push(elems).is_success(), "SOMEHOW GIVING MORE SPACE DIDN'T WORK");
      return success();
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push() [2/6]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::push	(	Allocator &	alloc,
		const Slice< std::remove_const_t< T > > &	elems )

inlinenodiscardnoexcept

Pushes a list of items onto an array list.

If there is no more room, will allocate a new list and do a copy If allocation fails, will return a failure

Parameters

alloc	Allocator to use for potential allocations
elems	Elements to add

Returns: Success or failure (failure happens if ArrayList cannot get more memory)

Definition at line 160 of file array_list.hpp.

                                                                                                        {
      return push(alloc, elems.to_const());
    }

Here is the call graph for this function:

◆ push() [3/6]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::push	(	Allocator &	alloc,
		const T &	elem )

inlinenodiscardnoexcept

Pushes an item onto an array list.

If there is no more room, will allocate a new list and do a copy If allocation fails, will return a failure

Parameters

alloc	Allocator to use for potential allocations
elem	Element to add

Returns: Success or failure (failure happens if ArrayList cannot get more memory)

Definition at line 173 of file array_list.hpp.

                                                                                               {
      ensure(elements.head, "NOT INITIALIZED");
      if (count >= elements.len) {
        size_t newSize = elements.len + ((elements.len + 1) / 2);
        if (auto res = reserve(alloc, newSize); res.is_error()) {
          return res;
        }
      }
 
      ensure(push(elem).is_success(), "SOMEHOW GIVING MORE SPACE DIDN'T WORK");
      return success();
    }

Here is the call graph for this function:

◆ push() [4/6]

template<typename T>

Result< void, CollectionAddNoAllocationError > mtcore::ArrayList< T >::push ( const Slice< std::add_const_t< T > > & elems )

inlinenodiscardnoexcept

Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Parameters

elems Element to add

Returns: success (had room) or failure (no room)

Definition at line 276 of file array_list.hpp.

                                                                                                                    {
      ensure(elements.head, "NOT INITIALIZED");
      if (count + elems.size() > elements.len) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      for (size_t i = 0; i < elems.size(); ++i) {
        elements[count++] = elems[i];
      }
 
      return success();
    }

Here is the call graph for this function:

◆ push() [5/6]

template<typename T>

Result< void, CollectionAddNoAllocationError > mtcore::ArrayList< T >::push ( const Slice< std::remove_const_t< T > > & elems )

inlinenodiscardnoexcept

Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Parameters

elems Element to add

Returns: success (had room) or failure (no room)

Definition at line 266 of file array_list.hpp.

                                                            {
      return push(elems.to_const());
    }

Here is the call graph for this function:

◆ push() [6/6]

template<typename T>

Result< void, CollectionAddNoAllocationError > mtcore::ArrayList< T >::push ( const T & elem )

inlinenodiscardnoexcept

Pushes an item onto the end of the ArrayList Will fail if there is not enough room.

Parameters

elem	Element to add

Returns: success (had room) or failure (no room)

Definition at line 295 of file array_list.hpp.

                                                                                            {
      ensure(elements.head, "NOT INITIALIZED");
      if (count >= elements.len) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      elements[count++] = elem;
      return success();
    }

Here is the call graph for this function:

◆ reserve()

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::reserve	(	Allocator &	alloc,
		const size_t	newSize )

inlinenodiscardnoexcept

Will grow the capacity to be at least newSize large.

Parameters

alloc	Allocator to use to resize
newSize	New minimum capacity size

Returns: Result

Definition at line 210 of file array_list.hpp.

                                                                                                         {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      if (newSize <= capacity()) {
        return success();
      }
      ensure(newSize > size(), "FAILED TO GROW");
      auto newElemAllocRes = alloc.create_many<T>(newSize);
      if (newElemAllocRes.is_error()) {
        return newElemAllocRes.error();
      }
 
      auto newElems = *newElemAllocRes;
      for (size_t i = 0; i < elements.size(); ++i) {
        std::swap(newElems[i], elements[i]);
      }
      alloc.destroy_many(elements);
      elements = newElems;
      return success();
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ shift()

template<typename T>

Optional< T > mtcore::ArrayList< T >::shift ( )

inlinenoexcept

Removes the first element and shifts all remaining elements down.

Returns: The element that was removed

Definition at line 354 of file array_list.hpp.

                                 {
      ensure(elements.head, "NOT INITIALIZED");
      if (count == 0) {
        return nullopt;
      }
      return shift_remove(0);
    }

Here is the call graph for this function:

◆ shift_remove()

template<typename T>

T mtcore::ArrayList< T >::shift_remove ( size_t index )

inlinenoexcept

Removes the element at an index (must be present) Does preserve ordering Will shift all remaining elements over by one Completes in \(O(N)\).

Parameters

index Index of element to remove. Must be a valid index

Returns: The removed element

Definition at line 445 of file array_list.hpp.

                                          {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(index < count, "ARRAY OUT OF BOUNDS DETECTED!");
 
      for (size_t i = index; i + 1 < count; ++i) {
        std::swap(elements[index], elements[index + 1]);
      }
      auto popRes = pop();
      ensure(popRes, "COULDN'T REMOVE ELMENT FROM NON-EMPTY LIST");
      return *popRes;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ shrink_to_fit()

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::shrink_to_fit ( Allocator & alloc )

inlinenodiscardnoexcept

Will shrink the capacity to match the current size.

Parameters

alloc Allocator to use to resize

Returns: Result

Definition at line 236 of file array_list.hpp.

                                                                                         {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      auto newSize = size();
      if (newSize == capacity()) {
        return success();
      }
 
      ensure(newSize < size(), "FAILED TO SHRINK");
      auto newElemAllocRes = alloc.create_many<T>(newSize);
      if (!newElemAllocRes) {
        return newElemAllocRes;
      }
 
      auto newElems = *newElemAllocRes;
      for (size_t i = 0; i < elements.size(); ++i) {
        std::swap(newElems[i], elements[i]);
      }
      alloc.destroy_many(elements);
      elements = newElems;
      return success();
    }

Here is the call graph for this function:

◆ size()

template<typename T>

size_t mtcore::ArrayList< T >::size ( ) const

inlinenodiscardnoexcept

Gets the size of an array list.

Returns: Size of the list

Definition at line 190 of file array_list.hpp.

                                               {
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      return count;
    }

Here is the caller graph for this function:

◆ slice() [1/2]

template<typename T>

Slice< T > mtcore::ArrayList< T >::slice ( )

inlinenodiscard

Gets a slice over the underlying elements.

Definition at line 460 of file array_list.hpp.

460{ return elements.sub(0, count); }

◆ slice() [2/2]

template<typename T>

Slice< std::add_const_t< T > > mtcore::ArrayList< T >::slice ( ) const

inlinenodiscard

Gets a slice over the underlying elements.

Definition at line 465 of file array_list.hpp.

465{ return elements.sub(0, count).to_const(); }

Here is the call graph for this function:

◆ swap_remove()

template<typename T>

T mtcore::ArrayList< T >::swap_remove ( size_t index )

inlinenoexcept

Removes the element at an index (must be present) Does NOT preserve ordering Will swap the removed element with the last element and then pop Completes in \(O(1)\).

Parameters

index Index of element to remove. Must be a valid index

Returns: The removed element

Definition at line 424 of file array_list.hpp.

                                         {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(index < count, "ARRAY OUT OF BOUNDS DETECTED!");
      auto end = count - 1;
      if (index != end) {
        std::swap(elements[end], elements[index]);
      }
 
      auto popRes = pop();
      ensure(popRes.has_value(), "COULDN'T REMOVE ELMENT FROM NON-EMPTY LIST");
      return *popRes;
    }

Here is the call graph for this function:

◆ unshift() [1/2]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::unshift	(	Allocator &	alloc,
		const T &	elem )

inlinenodiscardnoexcept

Adds an element to the front, and shifts all other elements down by 1 If there is not enough room, will try to allocate more room.

Parameters

alloc	Allocator to use to grow (if needed)
elem	Element to add

Returns: success or failure

Definition at line 334 of file array_list.hpp.

                                                                                                  {
      ensure(elements.head, "NOT INITIALIZED");
      // add the new element to the end
      if (auto err = push(alloc, elem)) {
        return err;
      }
 
      // then bubble the last element down
      for (size_t i = 0; i + 1 < count; ++i) {
        const auto upper = count - 1 - i;
        const auto lower = count - 2 - i;
        std::swap(elements[upper], elements[lower]);
      }
      return success();
    }

Here is the call graph for this function:

◆ unshift() [2/2]

template<typename T>

Result< void, AllocationError > mtcore::ArrayList< T >::unshift ( const T & elem )

inlinenodiscardnoexcept

Adds an element to the front, and shifts all other elements down by 1 If there is not enough room, will Result in a failure.

Parameters

elem	Element to add

Returns: success or failure

Definition at line 311 of file array_list.hpp.

                                                                                {
      ensure(elements.head, "NOT INITIALIZED");
      // add the new element to the end
      if (auto err = push(elem)) {
        return err;
      }
 
      // then bubble the last element down
      for (size_t i = 0; i + 1 < count; ++i) {
        const auto upper = count - 1 - i;
        const auto lower = count - 2 - i;
        std::swap(elements[upper], elements[lower]);
      }
      return success();
    }

Here is the call graph for this function:

The documentation for this struct was generated from the following file:

array_list.hpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Elem

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ capacity()

◆ deinit()

◆ init() [1/2]

◆ init() [2/2]

◆ iter()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop()

◆ ptr_iter() [1/2]

◆ ptr_iter() [2/2]

◆ push() [1/6]

◆ push() [2/6]

◆ push() [3/6]

◆ push() [4/6]

◆ push() [5/6]

◆ push() [6/6]

◆ reserve()

◆ shift()

◆ shift_remove()

◆ shrink_to_fit()

◆ size()

◆ slice() [1/2]

◆ slice() [2/2]

◆ swap_remove()

◆ unshift() [1/2]

◆ unshift() [2/2]