phundrakstl/src/vector.hh
2018-11-02 13:54:44 +01:00

622 lines
17 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <type_traits>
namespace phundrak {
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
template <class T, class Allocator = std::allocator<T>> class vector {
public:
class iterator;
class const_iterator;
class reverse_iterator;
class const_reverse_iterator;
private:
void double_capacity() {
if (data_) {
T *olddata = data_;
capacity_ <<= 1;
data_ = new T[capacity_];
for (size_t i = 0; i < size_; ++i)
data_[i] = olddata[i];
delete[] olddata;
} else {
data_ = new T[1];
capacity_ = 1;
}
}
T *data_ = nullptr;
size_t size_ = 0;
size_t capacity_ = 0;
Allocator alloc_ = Allocator{};
public:
///////////////////////////////////////////////////////////////////////////
// Member functions //
///////////////////////////////////////////////////////////////////////////
// constructor ////////////////////////////////////////////////////////////
vector() noexcept(noexcept(Allocator())) {}
explicit vector(const Allocator &alloc) noexcept : alloc_{alloc} {}
vector(size_type count, const T &value, const Allocator &alloc = Allocator())
: vector{alloc} {
for (size_t i = 0; i < count; ++i)
push_back(value);
}
explicit vector(size_type count, const Allocator &alloc = Allocator())
: alloc_{alloc} {
for (size_type i = 0; i < count; ++i)
push_back(T{});
}
template <class InputIt>
vector(InputIt first, InputIt last, const Allocator &alloc = Allocator())
: alloc_{alloc} {
for (; first != last; ++first)
push_back(*first);
}
// Copy constructor ///////////////////////////////////////////////////////
vector(const vector<T> &other)
: data_{new T[other.size_]}, size_{other.size_},
capacity_{other.capacity_}, alloc_{other.alloc_} {
if (!alloc_) {
alloc_ = std::allocator_traits<Allocator>::
select_on_container_copy_construction(other.get_allocator());
}
for (size_type i = 0; i < size_; ++i)
data_[i] = other.data_[i];
}
vector(const vector &other, const Allocator &alloc)
: data_{new T[other.size_]}, size_{other.size},
capacity_{other.capacity_}, alloc_{alloc} {
try {
if (alloc_ != other.alloc_)
throw 20;
} catch (int error) {
std::cout << "Error in phundrak::vector(const vector &other, const "
"Allocator &alloc) :\nThe allocator "
<< alloc
<< " passed as argument is different from others allocator "
<< other.alloc_ << "\nAborting...\n";
std::terminate();
}
for (size_type i = 0; i < size_; ++i)
data_[i] = other.data_[i];
}
// Move constructor ///////////////////////////////////////////////////////
vector(vector<T> &&other) noexcept {
std::swap(data_, other.data_);
std::swap(size_, other.size_);
std::swap(capacity_, other.capacity_);
std::swap(alloc_, other.alloc_);
}
vector(vector &&other, const Allocator &alloc) {
if (alloc != other.alloc_) {
std::swap(capacity_, other.capacity_);
std::swap(size_, other.size_);
data_ = new T[capacity_];
alloc_ = alloc;
for (size_type i = 0; i < size_; ++i)
data_[i] = std::move(other.data_[i]);
} else {
std::swap(capacity_, other.capacity);
std::swap(size_, other.size);
std::swap(data_, other.data_);
std::swap(alloc_, other.alloc_);
}
}
// Constructor by initializer list //////////////////////////////////////////
vector(std::initializer_list<T> init, const Allocator &alloc = Allocator())
: vector{alloc} {
for (auto &elem : init)
push_back(std::move(elem));
}
// Destructor ///////////////////////////////////////////////////////////////
virtual ~vector() noexcept {
if (data_)
delete[] data_;
}
// Copy assignment operator /////////////////////////////////////////////////
vector &operator=(const vector &other) {
delete[] data_;
size_ = other.size_;
capacity_ = other.capacity_;
data_ = new T[capacity_];
for (size_type i = 0; i < size_; ++i)
data_[i] = other.data_[i];
return *this;
}
vector &operator=(vector &&other) noexcept {
std::swap(alloc_, other.alloc_);
std::swap(size_, other.size_);
std::swap(capacity_, other.capacity_);
std::swap(data_, other.data_);
return *this;
}
vector &operator=(std::initializer_list<T> ilist) {
delete[] data_;
size_ = ilist.size();
capacity_ = size_;
data_ = new T[capacity_];
size_type i = 0;
std::for_each(std::begin(ilist), std::end(ilist), [&i, this](T &elem) {
data_[i] = std::move(elem);
++i;
});
return *this;
}
// assign ///////////////////////////////////////////////////////////////////
void assign(size_t count, const T &value) {
clear();
reserve(count);
for (size_t i = 0; i < count; ++i)
push_back(value);
}
template <typename InputIt,
typename std::enable_if_t<!std::is_integral<InputIt>::value,
InputIt> * = nullptr>
void assign(InputIt first, InputIt last) {
clear();
capacity_ = std::distance(first, last);
size_ = capacity_;
data_ = new T[capacity_];
for (int i = 0; first != last, i < size_; ++first, ++i)
data_[i] = *first;
}
void assign(std::initializer_list<T> ilist) {
delete[] data_;
size_ = ilist.size();
capacity_ = ilist.size();
data_ = new T[size_];
size_type i = 0;
for (auto pos = ilist.begin(); pos != ilist.end(); ++pos, ++i)
data_[i] = std::move(*pos);
}
// get_allocator ////////////////////////////////////////////////////////////
Allocator get_allocator() const { return alloc_; }
/////////////////////////////////////////////////////////////////////////////
// Element access //
/////////////////////////////////////////////////////////////////////////////
// at ///////////////////////////////////////////////////////////////////////
T &at(size_t pos) {
try {
if (pos >= size_)
throw std::out_of_range("Out of range");
} catch (const std::out_of_range &e) {
std::cout << e.what() << " in phundrak::vector " << this << '\n';
std::terminate();
}
return data_[pos];
}
const T &at(size_t pos) const {
try {
if (pos >= size_ || pos < 0)
throw std::out_of_range("Out of range");
} catch (const std::out_of_range &e) {
std::cout << e.what() << " in phundrak::vector " << this << '\n';
std::terminate();
}
return data_[pos];
}
// operator[] ///////////////////////////////////////////////////////////////
T &operator[](size_type pos) { return data_[pos]; }
const T &operator[](size_type pos) const { return data_[pos]; }
// front ////////////////////////////////////////////////////////////////////
T &front() { return data_[0]; }
const T &front() const { return data_[0]; }
// back /////////////////////////////////////////////////////////////////////
T &back() { return data_[size_ - 1]; }
const T &back() const { return data_[size_ - 1]; }
// data /////////////////////////////////////////////////////////////////////
T *data() noexcept { return data_; }
const T *data() const noexcept { return data_; }
/////////////////////////////////////////////////////////////////////////////
// Iterators //
/////////////////////////////////////////////////////////////////////////////
// begin ////////////////////////////////////////////////////////////////////
iterator begin() noexcept { return iterator{data_}; }
const_iterator begin() const noexcept { return const_iterator{data_}; }
const_iterator cbegin() const noexcept { return const_iterator{data_}; }
// end //////////////////////////////////////////////////////////////////////
iterator end() noexcept { return iterator{&data_[size_]}; }
const_iterator end() const noexcept { return const_iterator{&data_[size_]}; }
const_iterator cend() const noexcept { return const_iterator{&data_[size_]}; }
// rbegin ///////////////////////////////////////////////////////////////////
reverse_iterator rbegin() noexcept {
return reverse_iterator{&data_[size_ - 1]};
}
const_reverse_iterator rbegin() const noexcept {
return const_reverse_iterator{data_[size_ - 1]};
}
const_reverse_iterator crbegin() const noexcept {
return const_reverse_iterator{&data_[size_ - 1]};
}
// rend /////////////////////////////////////////////////////////////////////
reverse_iterator rend() noexcept {
reverse_iterator ret{data_};
++ret;
return ret;
}
const_reverse_iterator rend() const noexcept {
const_reverse_iterator ret{data_};
++ret;
return ret;
}
const_reverse_iterator crend() const noexcept {
const_reverse_iterator ret{data_};
++ret;
return ret;
}
/////////////////////////////////////////////////////////////////////////////
// Capacity //
/////////////////////////////////////////////////////////////////////////////
bool empty() const noexcept { return (size_ == 0) ? true : false; }
size_t size() const noexcept { return size_; }
void reserve(size_t new_cap) {
while (capacity_ < new_cap)
double_capacity();
}
size_t capacity() const noexcept { return capacity_; }
void shrink_to_fit() {
T *olddata = data_;
capacity_ = size_;
data_ = new T[capacity_];
for (size_t i = 0; i < size_; ++i)
data_[i] = olddata[i];
delete[] olddata;
}
/////////////////////////////////////////////////////////////////////////////
// Modifiers //
/////////////////////////////////////////////////////////////////////////////
// clear ////////////////////////////////////////////////////////////////////
void clear() noexcept {
delete[] data_;
data_ = new T[capacity_];
size_ = 0;
}
// insert ///////////////////////////////////////////////////////////////////
iterator insert(const_iterator pos, const T &value) {
if (size_ == capacity_)
double_capacity();
++size_;
T prev = value;
auto end = cend();
for (; pos != end; ++pos) {
T temp = *pos;
*pos = prev;
prev = temp;
}
return pos;
}
iterator insert(const_iterator pos, T &&value) {
if (size_ == capacity_)
double_capacity();
++size_;
T prev = std::move(value);
iterator ret = pos;
auto end = cend();
for (; pos != end; ++pos) {
T temp = std::move(*pos);
*pos = std::move(prev);
prev = std::move(temp);
}
return ++ret;
}
iterator insert(const_iterator pos, size_type count, const T &value) {
for (size_type i = 0; i < count; ++i, ++pos) {
insert(pos, value);
}
}
template <typename InputIT,
typename std::enable_if_t<!std::is_integral<InputIT>::value,
InputIT> * = nullptr>
iterator insert(const_iterator pos, InputIT first, InputIT last) {
for (; first != last; ++first) {
insert(pos, *first);
}
}
iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
for (const T elem : ilist) {
insert(pos, elem);
++pos;
}
}
// emplace //////////////////////////////////////////////////////////////////
template <class... Args>
iterator emplace(const_iterator pos, Args &&... args) {
if (size_ == capacity_)
double_capacity();
auto ptr1 = rbegin();
++ptr1;
auto ptr2 = rbegin();
printf("ptr1 : %d\nptr2: %d\n", *ptr1, *ptr2);
for (; ptr2 != pos; ++ptr2, ++ptr1)
std::swap(*ptr2, *ptr1);
std::swap(*ptr2, *ptr1);
*ptr1 = T(std::forward<Args>(args)...);
// *pos = T(std::forward<Args>(args)...);
++size_;
return pos;
}
// erase ////////////////////////////////////////////////////////////////////
iterator erase(const_iterator pos) {}
iterator erase(const_iterator first, const_iterator last) {}
// push_back ////////////////////////////////////////////////////////////////
void push_back(const T &value) {
++size_;
reserve(size_);
data_[size_ - 1] = value;
}
void push_back(T &&value) {
++size_;
reserve(size_);
data_[size_ - 1] = std::move(value);
}
// emplace_back /////////////////////////////////////////////////////////////
// pop_back /////////////////////////////////////////////////////////////////
void pop_back() {
if (size_ > 0)
--size_;
}
// resize ///////////////////////////////////////////////////////////////////
void resize(size_t count, T value = T()) {
if (count < size_)
size_ = count;
else if (count > size_)
reserve(count);
while (size_ < count)
push_back(value);
}
// swap /////////////////////////////////////////////////////////////////////
void swap(vector<T> &other) {
std::swap(capacity_, other.capacity_);
std::swap(size_, other.size_);
std::swap(data_, other.data_);
}
/////////////////////////////////////////////////////////////////////////////
// //
// //
// ITERATOR CLASS //
// //
// //
/////////////////////////////////////////////////////////////////////////////
class iterator {
protected:
T *it;
public:
using iterator_category = std::forward_iterator_tag;
iterator() : it{nullptr} {}
explicit iterator(T *point) : it{point} {}
iterator(const iterator &other) : it{other.it} {}
explicit iterator(const_iterator &other) : it{other.it} {}
iterator(iterator &&other) { std::swap(it, other.it); }
iterator &operator=(T *point) {
*it = *point;
return *this;
}
iterator &operator=(const iterator &other) {
*it = *other.it;
return *this;
}
iterator &operator=(iterator &&other) {
std::swap(*it, *other.it);
return *this;
}
~iterator() {
// delete it;
}
iterator &operator++() { // ++i
++it;
return *this;
}
iterator operator++(int) { // i++
// iterator t;
// t.it = it;
iterator t{*this};
++it;
return t;
}
iterator &operator+(int i) {
for (; i > 0; --i)
++it;
return *this;
}
iterator &operator--() { // --i
--it;
return *this;
}
iterator operator--(int) { // i--
// iterator t;
// t.it = it;
iterator t{it};
--it;
return t;
}
iterator &operator-(int i) {
for (; i > 0; --i)
--it;
return *this;
}
bool operator==(T *point) { return point == it; }
bool operator==(const iterator &other) { return other.it == it; }
bool operator==(iterator &&other) { return other.it == it; }
bool operator!=(T *point) { return point != it; }
bool operator!=(const iterator &other) { return other.it != it; }
bool operator!=(iterator &&other) { return other.it != it; }
T &operator*() { return *it; }
friend class vector;
};
class const_iterator : public iterator {
public:
using iterator_category = std::forward_iterator_tag;
const_iterator() : iterator() {}
explicit const_iterator(T *point) : iterator{point} {}
explicit const_iterator(const iterator &other) : iterator{other} {}
const_iterator(const const_iterator &other) : iterator{other} {}
explicit const_iterator(iterator &&other) : iterator{std::move(other)} {}
const_iterator(const_iterator &&other) : iterator{std::move(other)} {}
const T &operator*() const { return *this->it; }
};
class reverse_iterator : public iterator {
public:
reverse_iterator() : iterator() {}
explicit reverse_iterator(T *point) : iterator(point) {}
reverse_iterator(const reverse_iterator &other) : iterator(other) {}
reverse_iterator(reverse_iterator &&other) : iterator(std::move(other)) {}
reverse_iterator &operator++() {
--this->it;
return *this;
}
reverse_iterator operator++(int) {
reverse_iterator t{*this};
--this->it;
return t;
}
reverse_iterator &operator--() {
++this->it;
return *this;
}
reverse_iterator operator--(int) {
reverse_iterator t{*this};
++this->it;
return t;
}
~reverse_iterator() {}
};
class const_reverse_iterator : public reverse_iterator {
public:
const_reverse_iterator() : reverse_iterator() {}
explicit const_reverse_iterator(T *point) : reverse_iterator{point} {}
explicit const_reverse_iterator(const reverse_iterator &other)
: reverse_iterator{other} {}
const_reverse_iterator(const const_reverse_iterator &other)
: reverse_iterator{other} {}
explicit const_reverse_iterator(reverse_iterator &&other)
: reverse_iterator{other} {}
const T &operator*() const { return *this->it; }
virtual ~const_reverse_iterator() { this->~reverse_iterator(); }
};
protected:
};
} // namespace phundrak