|
LLFIO v2.00
|
Provides a constant time capacity expanding move-only STL vector. Requires T to be trivially copyable. More...
#include "trivial_vector.hpp"
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. | |
| reference | at (size_type i) |
| Item index, bounds checked. | |
| reference | operator[] (size_type i) |
| Item index, unchecked. | |
| reference | front () |
| First element. | |
| reference | back () |
| Last element. | |
| pointer | data () noexcept |
| Underlying array. | |
| iterator | begin () noexcept |
| Iterator to first item. | |
| const_iterator | cbegin () const noexcept |
| Iterator to first item. | |
| iterator | end () 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 | crbegin () const noexcept |
| Iterator to last item. | |
| reverse_iterator | rend () 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 | emplace (const_iterator pos, Args &&... args) |
| Emplace item. | |
| iterator | erase (const_iterator pos) |
| Erases item. | |
| void | push_back (const 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. | |
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 usually roughly breaks even with std::vector on recent Intel CPUs at around the L2 cache boundary. So if your vector fits into the L2 cache, this implementation will be no better, but no worse. If your vector fits into the L1 cache, this implementation will be worse, often considerably so.
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) on POSIX and 65536/sizeof(T) on Windows. Capacity is doubled in byte terms thereafter (i.e. 8Kb, 16Kb and so on). As mentioned earlier, 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.
Benchmarking notes for Skylake 3.1Ghz Intel Core i5 with 2133Mhz DDR3 RAM, L2 256Kb, L3 4Mb:
|
inlineconstexpr |
|
inlineinherited |
Assigns.
|
inlineinherited |
Item index, bounds checked.
|
inlineinherited |
Last element.
|
inlinenoexceptinherited |
Iterator to first item.
|
inlinenoexceptinherited |
Items can be stored until storage expanded.
|
inlinenoexceptinherited |
Iterator to first item.
|
inlinenoexceptinherited |
Iterator to after last item.
|
inlinenoexceptinherited |
Clears container.
|
inlinenoexceptinherited |
Iterator to last item.
|
inlinenoexceptinherited |
Iterator to before first item.
|
inlinenoexceptinherited |
Underlying array.
|
inlineinherited |
Emplace item.
|
inlineinherited |
Appends item.
|
inlinenoexceptinherited |
If empty.
|
inlinenoexceptinherited |
Iterator to after last item.
|
inlineinherited |
Erases item.
|
inlineinherited |
First element.
|
inlineinherited |
Inserts item.
|
inlinenoexceptinherited |
Maximum items in container.
|
inlineinherited |
Item index, unchecked.
|
inlineinherited |
Removes last element.
|
inlineinherited |
Appends item.
|
inlinenoexceptinherited |
Iterator to last item.
|
inlinenoexceptinherited |
Iterator to before first item.
|
inlineinherited |
Increase capacity.
|
inlineinherited |
Resizes container.
|
inlineinherited |
Resizes container, filling any new items with default constructed value_type.
|
inlineinherited |
Removes unused capacity.
|
inlinenoexceptinherited |
Items in container.
|
inlinenoexceptinherited |
Swaps.