I am new to C++ and Data structures, so I have started writing a custom vector as a practice. Please provide critique and advice. I know it is quite long, so thank you very much in advance. I just want to get better and not to get used to bad practices.
#pragma once
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstddef>
namespace DataStructures {
template<typename T>
class vector {
public:
using size_type = std::size_t;
template <typename DataType>
class BDIterator {
friend class vector;
public:
using difference_type = ptrdiff_t;
using value_type = DataType;
using pointer = DataType*;
using reference = DataType&;
using iterator_category = std::random_access_iterator_tag;
explicit BDIterator(const pointer data = nullptr) : m_address(data) {
}
reference operator*() const {
return *m_address;
}
pointer operator->() const {
return m_address;
}
BDIterator& operator++() {
++m_address;
return *this;
}
BDIterator operator++(int) {
BDIterator res(*this);
++(*this);
return res;
}
BDIterator& operator+=(int n) {
while (n--) {
++(*this);
}
return *this;
}
BDIterator operator+(int n) const {
BDIterator tmp(*this);
tmp += n;
return tmp;
}
BDIterator& operator--() {
--m_address;
return *this;
}
BDIterator operator--(int) {
BDIterator res(*this);
--(*this);
return res;
}
BDIterator& operator-=(int n) {
while (n--) {
--(*this);
}
return *this;
}
BDIterator operator-(int n) const {
BDIterator tmp(*this);
tmp -= n;
return tmp;
}
difference_type operator-(const BDIterator& rhs) const {
return m_address - rhs.m_address;
}
reference operator[](size_type ind) const {
return (*(*this + ind));
}
bool operator==(const BDIterator& other) const noexcept {
return m_address == other.m_address;
}
bool operator!=(const BDIterator& other) const noexcept {
return !(other == *this);
}
bool operator<(const BDIterator& other) const noexcept {
return m_address < other.m_address;
}
bool operator>(const BDIterator& other) const noexcept {
return other < *this;
}
private:
pointer m_address;
};
template <>
class BDIterator<T> {
public:
operator BDIterator<const T>() {
return BDIterator<const T>(m_address);
}
};
using iterator = BDIterator<T>;
using const_iterator = BDIterator<const T>;
template <typename DataType>
class BDRIterator {
friend class vector;
public:
using difference_type = ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
explicit BDRIterator(const pointer data = nullptr) : m_address(data) {}
explicit BDRIterator(BDIterator<T> iterator) : m_address(iterator.m_address - 1) {}
reference operator*() const {
return *m_address;
}
pointer operator->() const {
return m_address;
}
BDRIterator& operator++() {
--m_address;
return *this;
}
BDRIterator operator++(int) {
BDRIterator res(*this);
--(*this);
return res;
}
BDRIterator& operator+=(int n) {
while (n--) {
++(*this);
}
return *this;
}
BDRIterator operator+(int n) const {
BDRIterator tmp(*this);
tmp -= n;
return tmp;
}
BDRIterator& operator--() {
++m_address;
return *this;
}
BDRIterator operator--(int) {
BDRIterator res(*this);
++(*this);
return res;
}
BDRIterator& operator-=(int n) {
while (n--) {
--(*this);
}
return *this;
}
BDRIterator operator-(int n) const {
BDRIterator tmp(*this);
tmp += n;
return tmp;
}
difference_type operator-(const BDRIterator& rhs) const {
return m_address - rhs.m_address;
}
reference operator[](size_type ind) const {
return (*(m_address - ind));
}
BDIterator<T> base() {
return BDIterator<T>(m_address + 1);
}
bool operator==(const BDRIterator& other) const noexcept {
return m_address == other.m_address;
}
bool operator!=(const BDRIterator& other) const noexcept {
return !(other == *this);
}
bool operator<(const BDRIterator& other) const noexcept {
return m_address > other.m_address;
}
bool operator>(const BDRIterator& other) const noexcept {
return other < *this;
}
private:
pointer m_address;
};
using reverse_iterator = BDRIterator<T>;
using const_reverse_iterator = BDRIterator<const T>;
explicit vector(size_type = INITIAL_CAPACITY);
vector(size_type, const T&);
template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
vector(InputIterator first, InputIterator last) : vector(std::distance(first, last)) {
while (first != last) {
emplace_back(*first);
++first;
}
}
vector(const vector&);
vector(vector&&) noexcept;
vector(std::initializer_list<T>);
vector& operator=(vector);
vector& operator=(vector&&) noexcept;
vector& operator=(std::initializer_list<T>);
~vector();
template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
void assign(InputIterator, InputIterator) {
vector tmp(first, last);
tmp.swap(*this);
}
void assign(size_type, const T&);
void assign(std::initializer_list<T>);
void push_back(const T&);
void push_back(T&&);
template<typename... Ts>
void emplace_back(Ts&&...);
void pop_back() noexcept;
iterator erase(const_iterator);
iterator erase(const_iterator, const_iterator);
iterator insert(iterator position, const T& val);
iterator insert(iterator position, size_type n, const T& val);
template<class InputIterator>
iterator insert(iterator position, InputIterator first, InputIterator last);
iterator insert(iterator position, T&& val);
iterator insert(iterator position, std::initializer_list<T> il);
template <typename... Ts>
iterator emplace(const_iterator position, Ts&&... args);
void reserve(size_type);
void resize(size_type);
void resize(size_type, const T&);
T& operator[](size_type);
const T& operator[](size_type) const;
T& at(size_type);
const T& at(size_type) const;
T& front();
const T& front() const;
T& back();
const T& back() const;
T* data() noexcept;
const T* data() const noexcept;
bool empty() const noexcept;
size_type size() const noexcept;
size_type capacity() const noexcept;
bool contains(const T&) const noexcept;
void shrink_to_fit();
void swap(vector&);
void clear() noexcept;
iterator begin() noexcept {
return iterator(m_data);
}
iterator end() noexcept {
return iterator(m_data + m_size);
}
const_iterator begin() const noexcept {
return const_iterator(m_data);
}
const_iterator end() const noexcept {
return const_iterator(m_data + m_size);
}
reverse_iterator rbegin() noexcept {
return reverse_iterator(end());
}
reverse_iterator rend() noexcept {
return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const noexcept {
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const noexcept {
return const_reverse_iterator(begin());
}
const_iterator cbegin() const noexcept {
return begin();
}
const_iterator cend() const noexcept {
return end();
}
const_reverse_iterator crbegin() const noexcept {
return rbegin();
}
const_reverse_iterator crend() const noexcept {
return rend();
}
private:
void allocateMemory_(T*&, size_type);
void destructObjects_() noexcept;
void moveBackwards_(const_iterator, size_type);
private:
size_type m_size = 0;
size_type m_capacity = 0;
T* m_data = nullptr;
static const short INITIAL_CAPACITY = 2;
static const short FACTOR = 2;
};
template<typename T>
bool operator==(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
bool operator!=(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
bool operator>(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
bool operator>=(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
bool operator<(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
bool operator<=(const vector<T>& lhs, const vector<T>& rhs);
template<typename T>
vector<T>::vector(size_type capacity) : m_capacity(capacity) {
allocateMemory_(m_data, m_capacity);
}
template<typename T>
vector<T>::vector(size_type n, const T& val) : vector(n) {
while (n--) {
emplace_back(val);
}
}
template<typename T>
vector<T>::vector(const vector& rhs) : vector(rhs.cbegin(), rhs.cend()) {}
template<typename T>
vector<T>::vector(vector&& rhs) noexcept : m_data(nullptr), m_size(0), m_capacity(0) {
rhs.swap(*this);
}
template<typename T>
vector<T>::vector(std::initializer_list<T> rhs) : vector(rhs.begin(), rhs.end()) {
}
template<typename T>
vector<T>& vector<T>::operator=(vector rhs) {
rhs.swap(*this);
return *this;
// return *this = vector<T>{rhs}; <- copy-assign via move-assign
}
template<typename T>
vector<T>& vector<T>::operator=(vector&& rhs) noexcept {
rhs.swap(*this);
return *this;
}
template<typename T>
vector<T>& vector<T>::operator=(std::initializer_list<T> il) {
vector tmp(il.begin(), il.end());
tmp.swap(*this);
return *this;
}
template<typename T>
vector<T>::~vector() {
clear();
}
template<typename T>
void vector<T>::assign(size_type n, const T& val) {
vector tmp(n, val);
tmp.swap(*this);
}
template<typename T>
void vector<T>::assign(std::initializer_list<T> il) {
assign(il.begin(), il.end());
}
template<typename T>
void vector<T>::push_back(const T& element) {
emplace_back(element);
}
template<typename T>
void vector<T>::push_back(T&& element) {
emplace_back(std::move(element));
}
template <typename T>
template <typename ...Ts>
void vector<T>::emplace_back(Ts&&... args) {
if (!m_data || m_size == m_capacity) {
reserve(m_capacity * FACTOR);
}
new(m_data + m_size) T(std::forward<Ts>(args)...);
++m_size;
}
template<typename T>
void vector<T>::pop_back() noexcept {
m_data[--m_size].~T();
}
template<typename T>
typename vector<T>::iterator vector<T>::erase(typename vector<T>::const_iterator position) {
//std::advance(it,std::distance(cbegin(),position));
//iterator iter = begin() + ( position - cbegin() );
//std::move( iter + 1, end(), iter );
//pop_back();
//return iter;
return erase(position, position + 1);
}
template<typename T>
typename vector<T>::iterator
vector<T>::erase(typename vector<T>::const_iterator first, typename vector<T>::const_iterator last) {
//UB on invalid range
iterator iter = begin() + (first - cbegin());
int removed_elements = last - first;
std::move(last, cend(), iter);
while (removed_elements--) {
pop_back();
}
return iter;
}
template<typename T>
typename vector<T>::iterator vector<T>::insert(vector::iterator position, const T& val) {
moveBackwards_(position-1, 1);
size_type offset = position - cbegin();
m_data[offset] = val;
++m_size;
return (begin() + offset);
}
template<typename T>
typename vector<T>::iterator vector<T>::insert(vector::iterator position, size_type n, const T& val) {
moveBackwards_(position-1, n);
size_type offset = position - cbegin();
for (int i = 0; i < n; ++i) {
m_data[offset + i] = val;
}
m_size += n;
return (begin() + offset);
}
template<typename T>
template<class InputIterator>
typename vector<T>::iterator
vector<T>::insert(vector::iterator position, InputIterator first, InputIterator last) {
size_type count = std::distance(first, last);
moveBackwards_(position-1, count);
size_type offset = position - cbegin();
int i = 0;
while (first != last) {
m_data[offset + i] = *first;
++first;
++i;
}
m_size += count;
return (begin() + offset);
}
template<typename T>
template<typename ...Ts>
typename vector<T>::iterator vector<T>::emplace(vector<T>::const_iterator position, Ts&&...args)
{
moveBackwards_(position, 1);
size_type offset = position - cbegin();
new(m_data + offset - 1)T(std::forward<Ts>(args)...);
++m_size;
return (begin() + offset);
}
template<typename T>
typename vector<T>::iterator vector<T>::insert(vector::iterator position, T&& val) {
return emplace(position, std::forward<T>(val));
}
template<typename T>
typename vector<T>::iterator vector<T>::insert(vector::iterator position, std::initializer_list<T> il) {
return insert(position, il.begin(), il.end());
}
template<typename T>
void vector<T>::reserve(size_type size) {
if (size == 0) {
size = INITIAL_CAPACITY;
}
else if (size <= m_capacity) {
return;
}
T* newData = nullptr;
allocateMemory_(newData, size);
size_type i = 0;
for (; i < m_size; ++i) {
new(newData + i)T(std::move(m_data[i]));
}
clear();
m_data = newData;
m_capacity = size;
m_size = i;
}
template<typename T>
void vector<T>::resize(size_type size) {
resize(size, T());
}
template<typename T>
void vector<T>::resize(size_type size, const T& value) {
reserve(size);
if (size <= m_size) {
while (m_size > size) {
pop_back();
}
}
else {
while (m_size < size) {
push_back(value);
}
}
}
template<typename T>
T& vector<T>::operator[](size_type idx) {
return *(m_data + idx);
}
template<typename T>
const T& vector<T>::operator[](size_type idx) const {
return *(m_data + idx);
}
template<typename T>
T& vector<T>::at(size_type idx) {
if (idx >= m_size) {
throw (std::out_of_range("Invalid index"));
}
return *(m_data + idx);
}
template<typename T>
const T& vector<T>::at(size_type idx) const {
if (idx >= m_size) {
throw (std::out_of_range("Invalid index"));
}
return *(m_data + idx);
}
template<typename T>
T& vector<T>::front() {
return *m_data;
}
template<typename T>
const T& vector<T>::front() const {
return *m_data;
}
template<typename T>
T& vector<T>::back() {
return *(m_data + m_size - 1);
}
template<typename T>
const T& vector<T>::back() const {
return *(m_data + m_size - 1);
}
template<typename T>
T* vector<T>::data() noexcept {
return m_data;
}
template<typename T>
const T* vector<T>::data() const noexcept {
return m_data;
}
template<typename T>
bool vector<T>::empty() const noexcept {
return (m_size == 0);
}
template<typename T>
typename vector<T>::size_type vector<T>::size() const noexcept {
return m_size;
}
template<typename T>
typename vector<T>::size_type vector<T>::capacity() const noexcept {
return m_capacity;
}
template<typename T>
bool vector<T>::contains(const T& element) const noexcept {
for (int i = 0; i < m_size; ++i) {
if (m_data[i] == element) {
return true;
}
}
return false;
}
template<typename T>
void vector<T>::shrink_to_fit() {
vector(*this).swap(*this);
}
template<typename T>
void vector<T>::swap(vector& rhs) {
using std::swap;
swap(m_data, rhs.m_data);
swap(m_size, rhs.m_size);
swap(m_capacity, rhs.m_capacity);
}
template<typename T>
void vector<T>::clear() noexcept {
destructObjects_();
operator delete(m_data);
m_data = nullptr;
m_capacity = 0;
}
template<typename T>
void vector<T>::allocateMemory_(T*& destination, size_type capacity) {
destination = static_cast<T*>(operator new[](capacity * sizeof(T)));
}
template<typename T>
void vector<T>::destructObjects_() noexcept {
while (!empty()) {
pop_back();
}
}
template<typename T>
void vector<T>::moveBackwards_(vector::const_iterator position, size_type space) {
size_type elementsToMove = end() - position;
if (m_size + space >= m_capacity) {
reserve(m_capacity * FACTOR);
}
for (int i = 0; i < elementsToMove; ++i) {
new(m_data + m_size + space - i) T(std::move(m_data[m_size - i]));
}
}
template<typename T>
bool operator==(const vector<T>& lhs, const vector<T>& rhs) {
if (lhs.size() != rhs.size()) {
return false;
}
for (int i = 0; i < lhs.size(); ++i) {
if (lhs[i] != rhs[i]) {
return false;
}
}
return true;
}
template<typename T>
bool operator!=(const vector<T>& lhs, const vector<T>& rhs) {
return !(lhs == rhs);
}
template<typename T>
bool operator>(const vector<T>& lhs, const vector<T>& rhs) {
return rhs < lhs;
}
template<typename T>
bool operator>=(const vector<T>& lhs, const vector<T>& rhs) {
return !(lhs < rhs);
}
template<typename T>
bool operator<(const vector<T>& lhs, const vector<T>& rhs) {
int i = 0;
while (i < lhs.size() && i < rhs.size() && lhs[i] == rhs[i]) {
++i;
}
if (i == lhs.size() || i == rhs.size()) {
return lhs.size() < rhs.size();
}
return lhs[i] < rhs[i];
}
template<typename T>
bool operator<=(const vector<T>& lhs, const vector<T>& rhs) {
return !(rhs < lhs);
}
}
Questions:
- I can't understand this part:
template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
- Why do I need
typename =
? - Is there any way I can separate declaration from definition here?
typename
, how did you actually write that part? You are expected to understand your code when you post it here, so your question 1 is off-topic. To some extent, so is question 2, but that's likely to be answered in the course of review anyway. \$\endgroup\$