AFIO  v2.00 late alpha
afio_v2_xxx::algorithm::trivial_vector< T > Class Template Reference

Provides a constant time capacity expanding move-only STL vector. Requires T to be trivially copyable. More...

#include "trivial_vector.hpp"

Inheritance diagram for afio_v2_xxx::algorithm::trivial_vector< T >:
afio_v2_xxx::algorithm::impl::trivial_vector_impl< true, T > afio_v2_xxx::algorithm::impl::trivial_vector_impl< false, T >

Public Types

using value_type = T
 Value type.
 
using pointer = value_type *
 Pointer type.
 
using const_pointer = typename std::pointer_traits< pointer >::template rebind< const value_type >
 Const pointer type.
 
using difference_type = typename std::pointer_traits< pointer >::difference_type
 Difference type.
 
using size_type = typename std::make_unsigned< difference_type >::type
 Size type.
 
using reference = value_type &
 Reference type.
 
using const_reference = const value_type &
 Const reference type.
 
using iterator = pointer
 Iterator type.
 
using const_iterator = const_pointer
 Const iterator type.
 
using reverse_iterator = std::reverse_iterator< iterator >
 Reverse iterator type.
 
using const_reverse_iterator = std::reverse_iterator< const_iterator >
 Const reverse iterator type.
 

Public Member Functions

void resize (size_type count)
 Resizes container, filling any new items with default constructed value_type
 
void resize (size_type count, const value_type &v)
 Resizes container.
 
void assign (size_type count, const value_type &v)
 Assigns.
 
void assign (InputIt first, InputIt last)
 Assigns.
 
void assign (std::initializer_list< value_type > il)
 Assigns.
 
reference at (size_type i)
 Item index, bounds checked.
 
const_reference at (size_type i) const
 Item index, bounds checked.
 
reference operator[] (size_type i)
 Item index, unchecked.
 
const_reference operator[] (size_type i) const
 Item index, unchecked.
 
reference front ()
 First element.
 
const_reference front () const
 First element.
 
reference back ()
 Last element.
 
const_reference back () const
 Last element.
 
pointer data () noexcept
 Underlying array.
 
const_pointer data () const noexcept
 Underlying array.
 
iterator begin () noexcept
 Iterator to first item.
 
const_iterator begin () const noexcept
 Iterator to first item.
 
const_iterator cbegin () const noexcept
 Iterator to first item.
 
iterator end () noexcept
 Iterator to after last item.
 
const_iterator end () const noexcept
 Iterator to after last item.
 
const_iterator cend () const noexcept
 Iterator to after last item.
 
reverse_iterator rbegin () noexcept
 Iterator to last item.
 
const_reverse_iterator rbegin () const noexcept
 Iterator to last item.
 
const_reverse_iterator crbegin () const noexcept
 Iterator to last item.
 
reverse_iterator rend () noexcept
 Iterator to before first item.
 
const_reverse_iterator rend () const noexcept
 Iterator to before first item.
 
const_reverse_iterator crend () const noexcept
 Iterator to before first item.
 
bool empty () const noexcept
 If empty.
 
size_type size () const noexcept
 Items in container.
 
size_type max_size () const noexcept
 Maximum items in container.
 
void reserve (size_type n)
 Increase capacity.
 
size_type capacity () const noexcept
 Items can be stored until storage expanded.
 
void shrink_to_fit ()
 Removes unused capacity.
 
void clear () noexcept
 Clears container.
 
iterator insert (const_iterator pos, const value_type &v)
 Inserts item.
 
iterator insert (const_iterator pos, value_type &&v)
 Inserts item.
 
iterator insert (const_iterator pos, size_type count, const value_type &v)
 Inserts items.
 
iterator insert (const_iterator pos, InputIt first, InputIt last)
 Inserts items.
 
iterator insert (const_iterator pos, std::initializer_list< value_type > il)
 Inserts items.
 
iterator emplace (const_iterator pos, Args &&... args)
 Emplace item.
 
iterator erase (const_iterator pos)
 Erases item.
 
iterator erase (const_iterator first, const_iterator last)
 Erases items.
 
void push_back (const value_type &v)
 Appends item.
 
void push_back (value_type &&v)
 Appends item.
 
reference emplace_back (Args &&... args)
 Appends item.
 
void pop_back ()
 Removes last element.
 
void swap (trivial_vector_impl &o) noexcept
 Swaps.
 

Detailed Description

template<class T>
class afio_v2_xxx::algorithm::trivial_vector< T >

Provides a constant time capacity expanding move-only STL vector. Requires T to be trivially copyable.

As a hand waving estimate for whether this vector implementation may be useful to you, it roughly breaks even with std::vector on recent Intel CPUs at around the L2 cache level. So if your vector fits into the L2 cache, this implementation will be no better, and likely slower.

Note that no STL allocator support is provided as T must be trivially copyable (for which most STL's simply use memcpy() anyway instead of the allocator's construct), and an internal section_handle is used for the storage in order to implement the constant time capacity resizing.

We also disable the copy constructor, as copying an entire backing file is expensive. Use the iterator based copy constructor if you really want to copy one of these.

The very first item stored reserves a capacity of utils::page_size()/sizeof(T). Capacity is doubled in byte terms thereafter (i.e. 8Kb, 16Kb and so on). Also be aware that the capacity of the vector needs to become reasonably large before going to the kernel to resize the section_handle and remapping memory becomes faster than memcpy. For these reasons, this vector implementation is best suited to arrays of unknown in advance, but likely large, sizes.


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