ORIGINAL
Loading...
Searching...
No Matches
/home/frozenlemontee/Projects/original/src/core/vector.h

Factory function to create a vector with specified size and construction arguments.

Factory function to create a vector with specified size and construction arguments.

Template Parameters
TElement type of the vector
ARGSVariadic template parameter pack for construction arguments
Parameters
sizeNumber of elements to create
argsArguments to forward to element constructors
Returns
A new vector instance

Creates a vector with:

// Creates a vector of 10 default-constructed integers auto vec = makeVector<int>(10);

// Creates a vector of 5 strings initialized with "hello" auto strVec = makeVector<std::string>(5, "hello");

#ifndef VECTOR_H
#define VECTOR_H
#include "baseList.h"
#include "iterationStream.h"
#include "array.h"
namespace original{
template <typename TYPE, typename ALLOC = allocator<TYPE>>
class vector final : public baseList<TYPE, ALLOC>, public iterationStream<TYPE, vector<TYPE, ALLOC>>{
u_integer size_;
const u_integer INNER_SIZE_INIT = 16;
u_integer max_size;
u_integer inner_begin;
TYPE* body;
void vectorInit();
void vectorArrayDestruct() noexcept;
TYPE* vectorArrayInit(u_integer size);
static void moveElements(TYPE* old_body, u_integer inner_idx,
u_integer len, TYPE* new_body, integer offset);
[[nodiscard]] u_integer toInnerIdx(integer index) const;
[[nodiscard]] bool outOfMaxSize(u_integer increment) const;
void grow(u_integer new_size);
void adjust(u_integer increment);
explicit vector(u_integer size, ALLOC alloc = ALLOC{});
public:
class Iterator final : public randomAccessIterator<TYPE, ALLOC>
{
explicit Iterator(TYPE* ptr, const vector* container, integer pos);
public:
friend vector;
Iterator(const Iterator& other);
Iterator& operator=(const Iterator& other);
Iterator* clone() const override;
bool atPrev(const iterator<TYPE> *other) const override;
bool atNext(const iterator<TYPE> *other) const override;
[[nodiscard]] std::string className() const override;
};
explicit vector(ALLOC alloc = ALLOC{});
template<typename... ARGS>
vector(u_integer size, ALLOC alloc, ARGS&&... args);
vector(const vector& other);
vector(const std::initializer_list<TYPE>& list);
explicit vector(const array<TYPE>& arr);
vector& operator=(const vector& other);
vector(vector&& other) noexcept;
vector& operator=(vector&& other) noexcept;
[[nodiscard]] u_integer size() const override;
TYPE& data() const;
TYPE get(integer index) const override;
TYPE& operator[](integer index) override;
// const version
using serial<TYPE, ALLOC>::operator[];
void set(integer index, const TYPE &e) override;
u_integer indexOf(const TYPE &e) const override;
void pushBegin(const TYPE &e) override;
void push(integer index, const TYPE &e) override;
void pushEnd(const TYPE &e) override;
TYPE popBegin() override;
TYPE pop(integer index) override;
TYPE popEnd() override;
Iterator* begins() const override;
Iterator* ends() const override;
[[nodiscard]] std::string className() const override;
~vector() override;
template<typename T, typename... ARGS>
friend vector<T> makeVector(u_integer size, ARGS&&... args);
};
template<typename T, typename... ARGS>
vector<T> makeVector(u_integer size, ARGS&&... args);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::vectorInit() -> void
{
this->size_ = 0;
this->max_size = this->INNER_SIZE_INIT;
this->inner_begin = (this->INNER_SIZE_INIT - 1)/2;
this->body = vector::vectorArrayInit(this->INNER_SIZE_INIT);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::vectorArrayDestruct() noexcept -> void
{
if (this->body) {
for (u_integer i = 0; i < this->max_size; ++i) {
this->destroy(&this->body[i]);
}
this->deallocate(this->body, this->max_size);
this->body = nullptr;
}
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::vectorArrayInit(const u_integer size) -> TYPE* {
auto arr = this->allocate(size);
for (u_integer i = 0; i < size; i++) {
this->construct(&arr[i]);
}
return arr;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::moveElements(TYPE* old_body, const u_integer inner_idx,
const u_integer len, TYPE* new_body, const integer offset) -> void{
if (offset > 0)
{
for (u_integer i = 0; i < len; i += 1)
{
new_body[inner_idx + offset + len - 1 - i] = old_body[inner_idx + len - 1 - i];
}
}else
{
for (u_integer i = 0; i < len; i += 1)
{
new_body[inner_idx + offset + i] = old_body[inner_idx + i];
}
}
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::toInnerIdx(integer index) const -> u_integer
{
return this->inner_begin + index;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::outOfMaxSize(u_integer increment) const -> bool
{
return this->inner_begin + this->size() + increment > this->max_size - 1 || static_cast<integer>(this->inner_begin) - static_cast<integer>(increment) < 0;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::grow(const u_integer new_size) -> void
{
TYPE* new_body = vector::vectorArrayInit(new_size);
u_integer new_begin = (new_size - 1) / 4;
const integer offset = static_cast<integer>(new_begin) - static_cast<integer>(this->inner_begin);
vector::moveElements(this->body, this->inner_begin,
this->size(), new_body, offset);
this->vectorArrayDestruct();
this->body = new_body;
this->max_size = new_size;
this->inner_begin = new_begin;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::adjust(u_integer increment) -> void {
if (!this->outOfMaxSize(increment)) {
return;
}
u_integer new_begin = (this->max_size - this->size() - increment) / 2;
if (this->max_size >= this->size_ + increment && new_begin > 0) {
const integer offset = static_cast<integer>(new_begin) - static_cast<integer>(this->inner_begin);
vector::moveElements(this->body, this->inner_begin, this->size(),
this->body, offset);
this->inner_begin = new_begin;
} else {
const u_integer new_max_size = (this->size() + increment) * 2;
this->grow(new_max_size);
}
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::Iterator::Iterator(TYPE* ptr, const vector* container, integer pos)
: randomAccessIterator<TYPE, ALLOC>(ptr, container, pos) {}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::Iterator::Iterator(const Iterator& other)
: randomAccessIterator<TYPE, ALLOC>(nullptr, nullptr, 0)
{
this->operator=(other);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::Iterator::operator=(const Iterator& other) -> Iterator&
{
if (this == &other) {
return *this;
}
randomAccessIterator<TYPE, ALLOC>::operator=(other);
return *this;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::Iterator::clone() const -> Iterator* {
return new Iterator(*this);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::Iterator::atPrev(const iterator<TYPE> *other) const -> bool {
auto other_it = dynamic_cast<const Iterator*>(other);
return this->_ptr + 1 == other_it->_ptr;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::Iterator::atNext(const iterator<TYPE> *other) const -> bool {
auto other_it = dynamic_cast<const Iterator*>(other);
return other_it->_ptr + 1 == this->_ptr;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::Iterator::className() const -> std::string {
return "vector::Iterator";
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(ALLOC alloc)
: baseList<TYPE, ALLOC>(std::move(alloc)), size_(), max_size(), inner_begin()
{
this->vectorInit();
}
template<typename TYPE, typename ALLOC>
template<typename... ARGS>
original::vector<TYPE, ALLOC>::vector(u_integer size, ALLOC alloc, ARGS&&... args)
: vector(size, std::move(alloc)) {
this->body = this->allocate(this->max_size);
for (u_integer i = 0; i < this->size_; ++i) {
this->construct(&this->body[this->toInnerIdx(i)], std::forward<ARGS>(args)...);
}
}
template<typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(const u_integer size, ALLOC alloc)
: baseList<TYPE, ALLOC>(std::move(alloc)), size_(size),
max_size(size * 4 / 3), inner_begin(size / 3 - 1), body(nullptr) {
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(const vector& other) : vector(){
this->operator=(other);
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(const std::initializer_list<TYPE>& list) : vector()
{
this->adjust(list.size());
for (const TYPE& e: list)
{
this->body[this->inner_begin + this->size()] = e;
this->size_ += 1;
}
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::operator=(const vector& other) -> vector&
{
if (this == &other)
return *this;
this->vectorArrayDestruct();
this->max_size = other.max_size;
this->inner_begin = other.inner_begin;
this->size_ = other.size_;
this->body = vector::vectorArrayInit(this->max_size);
for (u_integer i = 0; i < this->size(); ++i) {
const TYPE& data = other.body[this->toInnerIdx(i)];
this->body[this->toInnerIdx(i)] = data;
}
if constexpr (ALLOC::propagate_on_container_copy_assignment::value){
this->allocator = other.allocator;
}
return *this;
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(vector&& other) noexcept : vector()
{
this->operator=(std::move(other));
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::operator=(vector&& other) noexcept -> vector&
{
if (this == &other)
return *this;
this->vectorArrayDestruct();
this->body = other.body;
other.body = nullptr;
this->max_size = other.max_size;
this->inner_begin = other.inner_begin;
this->size_ = other.size_;
if constexpr (ALLOC::propagate_on_container_move_assignment::value){
this->allocator = std::move(other.allocator);
}
other.vectorInit();
return *this;
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::vector(const array<TYPE>& arr) : vector()
{
this->adjust(arr.size());
for (u_integer i = 0; i < arr.size(); i += 1)
{
this->body[this->toInnerIdx(i)] = arr.get(i);
this->size_ += 1;
}
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::size() const -> u_integer
{
return this->size_;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::data() const -> TYPE& {
return this->body[this->toInnerIdx(0)];
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::get(integer index) const -> TYPE
{
if (this->indexOutOfBound(index))
{
throw outOfBoundError();
}
index = this->toInnerIdx(this->parseNegIndex(index));
return this->body[index];
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::operator[](integer index) -> TYPE&
{
if (this->indexOutOfBound(index))
{
throw outOfBoundError();
}
index = this->toInnerIdx(this->parseNegIndex(index));
return this->body[index];
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::set(integer index, const TYPE &e) -> void
{
if (this->indexOutOfBound(index))
{
throw outOfBoundError();
}
index = this->toInnerIdx(this->parseNegIndex(index));
this->body[index] = e;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer
{
for (u_integer i = 0; i < this->size(); i += 1)
{
if (this->get(i) == e)
{
return i;
}
}
return this->size();
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::pushBegin(const TYPE &e) -> void
{
this->adjust(1);
this->inner_begin -= 1;
this->body[this->toInnerIdx(0)] = e;
this->size_ += 1;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::push(integer index, const TYPE &e) -> void
{
if (this->parseNegIndex(index) == this->size())
{
this->pushEnd(e);
}else if (this->parseNegIndex(index) == 0)
{
this->pushBegin(e);
}else
{
if (this->indexOutOfBound(index))
{
throw outOfBoundError();
}
this->adjust(1);
index = this->toInnerIdx(this->parseNegIndex(index));
u_integer rel_idx = index - this->inner_begin;
if (index - this->inner_begin <= (this->size() - 1) / 2)
{
vector::moveElements(this->body, this->inner_begin,
rel_idx + 1, this->body, -1);
this->inner_begin -= 1;
}else
{
vector::moveElements(this->body, index,
this->size() - rel_idx, this->body, 1);
}
this->body[this->toInnerIdx(rel_idx)] = e;
this->size_ += 1;
}
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::pushEnd(const TYPE &e) -> void
{
this->adjust(1);
this->body[this->toInnerIdx(this->size())] = e;
this->size_ += 1;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::popBegin() -> TYPE
{
if (this->size() == 0){
throw noElementError();
}
TYPE res = this->get(0);
this->inner_begin += 1;
this->size_ -= 1;
return res;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::pop(integer index) -> TYPE
{
if (this->parseNegIndex(index) == 0)
{
return this->popBegin();
}
if (this->parseNegIndex(index) == this->size() - 1)
{
return this->popEnd();
}
if (this->indexOutOfBound(index)){
throw outOfBoundError();
}
TYPE res = this->get(index);
index = this->toInnerIdx(this->parseNegIndex(index));
u_integer rel_idx = index - this->inner_begin;
if (index - this->inner_begin <= (this->size() - 1) / 2)
{
vector::moveElements(this->body, this->inner_begin,
rel_idx, this->body, 1);
this->inner_begin += 1;
}else
{
vector::moveElements(this->body, index + 1,
this->size() - 1 - rel_idx, this->body, -1);
}
this->size_ -= 1;
return res;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::popEnd() -> TYPE
{
if (this->size() == 0){
throw noElementError();
}
TYPE res = this->get(this->size() - 1);
this->size_ -= 1;
return res;
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::begins() const -> Iterator* {
return new Iterator(&this->body[this->toInnerIdx(0)], this, 0);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::ends() const -> Iterator* {
return new Iterator(&this->body[this->toInnerIdx(this->size() - 1)], this, this->size() - 1);
}
template <typename TYPE, typename ALLOC>
auto original::vector<TYPE, ALLOC>::className() const -> std::string
{
return "vector";
}
template <typename TYPE, typename ALLOC>
original::vector<TYPE, ALLOC>::~vector() {
this->vectorArrayDestruct();
}
template<typename T, typename... ARGS>
original::vector<T> original::makeVector(u_integer size, ARGS &&... args) {
return original::vector<T>(size, original::allocator<T>{}, std::forward<ARGS>(args)...);
}
#endif //VECTOR_H
array.h
Provides the array class for a fixed-size container with random access.
baseList.h
Provides a base class for variable-size serial containers.
original::allocator
Default memory allocator using allocators utilities.
Definition allocator.h:154
original::container::container
container(ALLOC alloc=ALLOC{})
Constructs a container with specified allocator.
Definition container.h:129
original::randomAccessIterator::_ptr
TYPE * _ptr
Pointer to the current element.
Definition randomAccessIterator.h:41
original::vector::Iterator
Random access iterator implementation for vector.
Definition vector.h:163
original::vector::Iterator::clone
Iterator * clone() const override
Clones the iterator.
Definition vector.h:521
original::vector::Iterator::operator=
Iterator & operator=(const Iterator &other)
Assignment operator for the iterator.
Definition vector.h:511
original::vector::Iterator::className
std::string className() const override
Gets the class name of the iterator.
Definition vector.h:538
original::vector::Iterator::atNext
bool atNext(const iterator< TYPE > *other) const override
Checks if the iterator is at the next element relative to another iterator.
Definition vector.h:532
original::vector::Iterator::atPrev
bool atPrev(const iterator< TYPE > *other) const override
Checks if the iterator is at the previous element relative to another iterator.
Definition vector.h:526
original::vector
Dynamic array container with amortized constant time operations.
Definition vector.h:43
original::vector::size
u_integer size() const override
Gets the size of the vector.
Definition vector.h:640
original::vector::operator=
vector & operator=(const vector &other)
Assignment operator for the vector.
Definition vector.h:582
original::vector::popBegin
TYPE popBegin() override
Removes and returns the first element in the vector.
Definition vector.h:747
original::vector::data
TYPE & data() const
Gets a reference to the first element in the vector.
Definition vector.h:646
original::vector::push
void push(integer index, const TYPE &e) override
Inserts an element at the specified index in the vector.
Definition vector.h:706
original::vector::~vector
~vector() override
Destructor for the vector.
Definition vector.h:817
original::vector::ends
Iterator * ends() const override
Gets an iterator to the end of the vector.
Definition vector.h:806
original::vector::pushEnd
void pushEnd(const TYPE &e) override
Inserts an element at the end of the vector.
Definition vector.h:739
original::vector::pushBegin
void pushBegin(const TYPE &e) override
Inserts an element at the beginning of the vector.
Definition vector.h:697
original::vector::className
std::string className() const override
Gets the class name of the vector.
Definition vector.h:811
original::vector::pop
TYPE pop(integer index) override
Removes and returns the element at the specified index.
Definition vector.h:759
original::vector::indexOf
u_integer indexOf(const TYPE &e) const override
Finds the index of the first occurrence of the specified element.
Definition vector.h:684
original::vector::get
TYPE get(integer index) const override
Gets an element at the specified index.
Definition vector.h:651
original::vector::set
void set(integer index, const TYPE &e) override
Sets the element at the specified index.
Definition vector.h:673
original::vector::begins
Iterator * begins() const override
Gets an iterator to the beginning of the vector.
Definition vector.h:801
original::vector::operator[]
TYPE & operator[](integer index) override
Gets a reference to the element at the specified index.
Definition vector.h:662
original::vector::popEnd
TYPE popEnd() override
Removes and returns the last element in the vector.
Definition vector.h:790
std::get
constexpr auto & get(original::couple< F, S > &c) noexcept
Structured binding support - get for non-const lvalue reference.
Definition couple.h:364
iterationStream.h
Provides functionality for an iteration stream.
original
Main namespace for the project Original.
Definition algorithms.h:21
original::u_integer
std::uint32_t u_integer
32-bit unsigned integer type for sizes and indexes
Definition config.h:43
original::integer
std::int64_t integer
64-bit signed integer type for arithmetic operations
Definition config.h:35
Generated by doxygen 1.13.2