orlp/devector – GitClassic

📄 README.md

Warning: `devector` is not finished yet and the implementation is currently an incomplete WIP.

devector - a resizable contiguous sequence container with fast appends on either end ======================================================================================

Unlike std::vector, devector can have free capacity both before and after the elements. This enables efficient implementation of methods that modify the devector at the front. Anything a std::vector can do, a devector can as well. devectors available methods are a superset of those of std::vector with identical behaviour, barring a couple of iterator invalidation guarantees that differ. The overhead for devector is one extra pointer per container. sizeof(devector) == 4*sizeof(T*) as opposed to the general implementation of sizeof(std::vector) == 3*sizeof(T*). Also, devector<bool> is not specialized.

Whenever devector requires more free space at an end it applies the following allocation strategy:

Halve the amount of free space that will be left on the other end after the operation and

calculate how much free space we want on this end after the operation. newfreeother = free_other / 2 newfreethis = size() >= 16 ? size() / 3 : size()

If there isn't enough total memory to fit new_free_other + size() + new_free_this, then

allocate more memory using an exponential factor of 1.5 with doubling for small sizes: newmem = oldmem >= 16 ? oldmem 1.5 : oldmem 2

Move the elements into the appropriate memory location, leaving new_free_other and

new_free_this free space at the ends. If new memory was allocated deallocate the old memory.

Note that not every request for more space results in an reallocation. If half of the free space of the other side is enough to satisfy the needs of this side the elements are simply moved.

Constantly halving the amount of free space on the side that it is not used on prevents wasted space. In the worst case where you push at one end and pop at the other (FIFO), memory is bounded to 5n/3. This is because free space on the output end is constantly halved, but only size() / 3 free space is required on the input end.

Typedefs

typedef T value_type; typedef Allocator allocator_type; typedef typename alloctraits::sizetype size_type; typedef typename alloctraits::differencetype difference_type; typedef typename alloc_traits::pointer pointer; typedef typename alloctraits::constpointer const_pointer; typedef T& reference; typedef const T& const_reference; typedef pointer iterator; typedef constpointer constiterator; typedef std::reverseiterator reverseiterator; typedef std::reverseiteratoriterator> constreverseiterator;

All these typedefs are the same as for std::vector. Construction/Assignment/Swapping/Destructor
~devector() noexcept; devector() noexcept(std::isnothrowdefault_constructible::value); explicit devector(const Allocator& alloc) noexcept; explicit devector(size_type n, const Allocator& alloc = Allocator()); devector(size_type n, const T& value, const Allocator& alloc = Allocator()); template devector(InputIterator first, InputIterator last, const Allocator& alloc = Allocator()); devector(const devector& other); devector(const devector& other, const Allocator& alloc); devector(devector&& other) noexcept; devector(devector&& other, const Allocator& alloc); devector(std::initializer_list il, const Allocator& alloc = Allocator()); devector& operator=(const devector& other); devector& operator=(devector&& other) noexcept(/ See below.. /); devector& operator=(std::initializer_list il); template void assign(InputIterator first, InputIterator last); void assign(size_type n, const T& t); void assign(std::initializer_list il);

All these operations have the exact same syntax and semantics as std::vector. The move assignment operator is marked noexcept if the allocator should propagate on move assignment.

Getters
allocatortype getallocator() const noexcept; iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; constreverseiterator rbegin() const noexcept; reverse_iterator rend() noexcept; constreverseiterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; constreverseiterator crbegin() const noexcept; constreverseiterator crend() const noexcept; reference front() noexcept; const_reference front() const noexcept; reference back() noexcept; const_reference back() const noexcept; T* data() noexcept; const T* data() const noexcept; reference operator[](size_type i) noexcept; constreference operator[](sizetype i) const noexcept; reference at(size_type i); constreference at(sizetype i) const; sizetype maxsize() const noexcept; size_type size() const noexcept; bool empty() const noexcept;

All these operations have the exact same syntax and semantics as std::vector. The only difference is that some functions have been marked noexcept, even though the standard doesn't require it.

size_type capacity() const noexcept; sizetype capacityfront() const noexcept; sizetype capacityback() const noexcept; The function capacity is an alias for capacity_back. capacity_back returns the number of elements in the container plus the amount of elements that can fit in the free space at the back. capacity_front does the exact same except for the free space at the front. This means that the total size of allocated memory is sizeof(T) * (capacity_front() + capacity_back() - size()).

Modifiers
The following functions are also required to be MoveAssignable in addition to the limitations put forth by std::vector: emplace_back, push_back, emplace_front, push_front, resize, resize_back, resize_front.

void swap(devector& other) noexcept(/ See below. /); void shrinktofit(); void clear() noexcept; template void emplace_back(Args&&... args); void push_back(const T& x); void push_back(T&& x); void pop_back();

All these operations have the exact same syntax and semantics as std::vector. The noexcept specifier for swap is only false if the allocator must be propagated on swap and it can not be swapped without exceptions.

template void emplace_front(Args&&... args); void push_front(const T& x); void push_front(T&& x);

Prepends an element to the container. If the new size() is greater than capacity_front() all references and iterators (including the past-the-end iterator) are invalidated. Otherwise all iterators and references remain valid. The behaviour on exceptions is the same as push_back/emplace_back.

void pop_front();

Removes the first element of the container. Calling pop_front on an empty container is undefined. No iterators or references except front() and begin() are invalidated.

void reserve(size_type n); void reserve(sizetype newfront, sizetype newback); void reservefront(sizetype n); void reserveback(sizetype n); The single argument reserve is an alias for reserve_back. reserve_back has the exact same semantics as std::vectors reserve. reserve_front does the same as reserve_back except it influences capacity_front() rather than the capacity at the back. The two argument reserve has the same behaviour as two calls to respectively reserve_front and reserve_back, but is more efficient by doing at most one reallocation.

void resize(size_type n); void resize(size_type n, const T& t); void resizeback(sizetype n); void resizeback(sizetype n, const T& t); void resizefront(sizetype n); void resizefront(sizetype n, const T& t);

resize is an alias for resize_back and has the exact same semantics as std::vector. resize_front is the same as resize_back except that it resizes the container with push_front/pop_front rather than push_back/pop_back.

template iterator emplace(const_iterator position, Args&&... args); iterator insert(const_iterator position, const T& t); iterator insert(const_iterator position, T&& t); iterator insert(constiterator position, sizetype n, const T& t); iterator insert(constiterator position, std::initializerlist il); template iterator insert(const_iterator position, InputIterator first, InputIterator last);

All these operations have the same semantics as std::vector, except for the iterators/references that get invalidated by these operations. If position - begin() < size() / 2 then only the iterators/references after the insertion point remain valid (including the past-the-end iterator). Otherwise only the iterators/references before the insertion point remain valid.

iterator erase(const_iterator position);

Behaves the same as as std::vector, except for which iterators/references get invalidated. If position - begin() < size() / 2 then all iterators and references at or before position are invalidated. Otherwise all iterators and references at or after (including end()) position are invalidated.

iterator erase(constiterator first, constiterator last);

Behaves the same as as std::vector, except for which iterators/references get invalidated. If first - begin() < end() - last then all iterators and references at or before last are invalidated. Otherwise all iterators and references at or after (including end()) first are invalidated.

Lastly, devector has lexical comparison operator overloads and swap defined in its namespace just like std::vector.

Warning: devector is not finished yet and the implementation is currently an incomplete WIP.

Warning: `devector` is not finished yet and the implementation is currently an incomplete WIP.