C++ Creating custom vector

Question

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>

1. Why do I need typename = ?
2. Is there any way I can separate declaration from definition here?

Answer 1

Correctness and testing:

First off... note that compilers are not required to do anything with template code unless it's actually used ("instantiation"). Some compilers (or versions of a particular compiler) may check (some) template code for correctness, others may not.

So writing a template function, we cannot rely on the compiler to give us a compiler error if we make a mistake. This makes unit testing essential - we only know if the function compiles when we use it in some code (let alone whether it does the correct thing).

There are a couple of things my compiler picks up straight away:

    template <>
    class BDIterator<T> {
    public:
        operator BDIterator<const T>() {
            return BDIterator<const T>(m_address);
        }
    };

This doesn't behave the way you expect it to. Adding a class specialization like this is creating a whole new type of class when the type is T. So m_address doesn't exist in this class, and this is the only function. (There are some other ways of adding the necessary const functionality to an iterator, which I'll talk about below).

    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);
    }

We forgot to name the function arguments to first and last!

(There may be more things that won't compile when we try to use them.)

---

typedefs:

We're missing a few more standard (and useful) typedefs from the vector class:

value_type, difference_type, pointer, const_pointer, reference, const_reference

---

std::reverse_iterator:

After implementing the forward iterator correctly, we can use the standard library to generate the reverse one:

using iterator = BDIterator<T>;
using reverse_iterator = std::reverse_iterator<iterator>;

---

constructors:

    explicit vector(size_type = INITIAL_CAPACITY);

Note that the standard library takes the initial size as an argument, not the capacity, which may confuse users.

    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;
        }
    }

Using std::distance means that calling this function with "input" iterators (one-pass only) won't work at all, and calling it with "forward" or "bidirectional" iterators (no random access) may be slow.

A simpler implementation that just calls emplace_back would avoid these issues.

If we want to pre-allocate memory for random-access iterators, we can do that by dispatching to another function based on the iterator tag.

---

use standard algorithms where convenient:

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;
}

Could be: return std::find(begin(), end(), element) != end();

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;

}

Could be: return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());

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];
}

Could be: return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());

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);
}

Could perhaps use: std::copy(first, last, begin() + offset);

Note, however, that moveBackwards_ may reallocate memory. If it does, the position iterator is invalidated (it still points to the old memory), so we can't do position - cbegin()!

---

use uninitialized memory algorithms:

C++17 and C++20 also give us various algorithms for dealing with uninitialized memory. So if they're available, you might want to:

• use std::construct_at instead of placement new.
• use std::destroy(begin(), end()); to destroy objects, instead of repeatedly calling pop_back().
• use std::uninitialized_move in reserve
• use std::uninitialized_move in moveBackwards_ (with reverse iterators).

---

const and non-const iterators:

Nearly everything is the same between const and non-const iterators, so we're really just trying to avoid code duplication.

Personally I like the trick of adding an extra bool template parameter to the iterator class like so:

template<class T, bool IsConst>
class BDIterator { ... };

Then we can use enable_if to conditionally add the functionality we need:

    template<class C = IsConst, class = std::enable_if_t<C>>
    BDIterator(BDIterator<T, false> other): m_address(other.m_address) { }

And we can declare the iterators as:

using iterator = BDIterator<T, false>;
using const_iterator = BDIterator<T, true>;

See here for more details.

---

pointer arithmetic:

        BDIterator& operator+=(int n) {
            while (n--) {
                ++(*this);
            }
            return *this;
        }

Rather than repeatedly calling the increment operator, we could just do m_address += n. (And similarly for operator-=).

Note also that +=, -=, + and - should take the n parameter as a difference_type, and not an int.

Answer 2

Answers

template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
vector(InputIterator first, InputIterator last)

I can't understand this part:

This is using SFINE to make that constructor available or not available depending on the type of the iterator used.

If the user of your class passed two iterators that are not integral then the std::enable_if will fail to resolve. This means that compilation will fail as this constructor is not valid (not all the type resolved correctly).

This causes an error for the user of your code (i.e. they get an error that they are not using a valid constructor). This is better than getting an error that points deep inside your vector code saying some type they have never used or heard of is not compiling and then thinking you wrote a bad vector class.

Note: SFINE: > Substitution Failure Is Not an Error (another great acronym from C++ just like RAII). What this is saying that if we are trying to resolve types (using substitution) and not all the types can be resolved this is not an error. The offending method/class is simply never created.

You can think of SFINE as the predecessor to C++ concepts (coming to you in a compiler where std=20). Concepts has been bounced around a lot over the last 17 years never quite making into the standard because of issues; so SFINE is the crippled cousin that sort of gets us 90% of what we want even if it is hard to read.

Why do I need typename = ?

The std::enable_if either resolves to a type or not. Which makes it compile or not. But you need a template parameter for it. But like parameters to normal functions it is rarely used so you can leave off the name.

You could write it like <typename I, typename Enabled = std::endable_if<......> You then have the typename in Enabled but you don't use it.

Is there any way I can separate declaration from definition here?

Sure it is just like normal functions with predefined parameters. You declare it like above. But the definition you don't add the = stuff part.

Example:

 // declaration
 int function1(int val = 5);

 // definition
 int function1(int val) {return val + 1;} // note no = 5 here.

Note: here you don't need a parameter name here either.

 // declaration
 int function2(int = 8);

 // definition
 int function2(int) {return 8;} // note no = 8 here.

Same thing for the template parameters:

 // declaration
 template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
 vector(InputIterator first, InputIterator last);

 // definition
 template<typename InputIterator, typename>
 vector(InputIterator first, InputIterator last)
     : vector(std::distance(first, last))
 {
     while (first != last) {
         emplace_back(*first);
         ++first;
     }
 }

Note in later version (C++14) both std::enable_if and std::is_integral have helper things that shorten that up a lot. For meta things that return types add the suffix _t (no longer need the typename), for meta things that return values add the suffix _v. This shortens the above_to:

template<typename InputIterator, typename = std::enable_if_t<!std::is_integral_v<InputIterator>>>
vector(InputIterator first, InputIterator last);

Overview

Overall this is very good.

Couple of minor issues that I have documented below, but your memory management is relatively solid. Only a couple of minor mistakes around the lifetime of objects (where you use placement new on an object whose lifetime has already started).

Normally I don't suggest this (as people have a lot of work to do). But for this project the next step is add a bunch of unit tests.

In generally using DRY principles to make sure you don't repeat the code is good. I think you overuse this a bit especially for trivial functions that simply return an iterator. There are a lot of places were it would have been more obvious to do maths using the m_data object rather than getting the iterator and doing mathematics with that.

Code Review

A member class is part of the parent class and thus has accesses to all its members. In this case BDIterator is a member of vector so BDIterator automatically has accesses to all members of vector.

    class BDIterator {
        friend class vector;        // Thus this line is not needed.

---

The advantaage of random accesses iterator is that you do a const time increment of the iterator. You have a O(n) cost to increment the iterator here.

        BDIterator& operator+=(int n) {
            while (n--) {
                ++(*this);
            }
            return *this;
        }

---

Normally you implement + using the +=. You have done it the other way around. Not really a big deal but its interesting. For this iterator it is som simple that adding this level of indirection is not really needed.

        BDIterator operator+(int n) const {
            BDIterator tmp(*this);
            tmp += n;
            return tmp;
        }

---

This seems like a complex way of writting return m_address[ind].

        reference operator[](size_type ind) const {
            return (*(*this + ind));
        }

Here you are getting a reference to an iterator adding an offset which creates a new iterator then de-referencing the temporary iterator object. I am sure the compiler works it all out and gives you an effecient implementation. But I don't think you need to make it work that hard:

---

I would not bother writting a reverse iterator. You can use the staandard wrapper std::reverse_iterator

---

Why does the copy constructor use a const reference but the copy assignment takes a member.

    vector(const vector&);
    vector& operator=(vector);

---

This is a syntax error so this would generate an error if you had a unit test. You get away with this because it is a template and you don't use it.

    template<typename InputIterator, typename = typename std::enable_if<!std::is_integral<InputIterator>::value>::type>
    void assign(InputIterator, InputIterator) {  // Missing parameters names
        vector tmp(first, last);
        tmp.swap(*this);
    }

---

This has a different meaning to std::vector.

template<typename T>
vector<T>::vector(size_type capacity) : m_capacity(capacity) {
    allocateMemory_(m_data, m_capacity);
}

You are using the passed size to mean the capacity. While std::vector uses it means to actual size of the object (i.e. it will filled with capacity valid objects (default constructed)).

---

Don't think passing const iterators to a method that mutates the object is sending the correct message. template typename vector::iterator vector::erase(typename vector::const_iterator first, typename vector::const_iterator last) {

---

In the last three uses of insert:

typename vector<T>::iterator vector<T>::insert(vector::iterator position, const T& val)
typename vector<T>::iterator vector<T>::insert(vector::iterator position, size_type n, const T& val)
typename vector<T>::iterator
    vector<T>::insert(vector::iterator position, InputIterator first, InputIterator last) 

The method moveBackwards_() moves objects to the right but the object at location position is left in a valid state (we know this because you use operator[] to access the object then operator= to copy the inserted value over the current value.

But in this method:

typename vector<T>::iterator vector<T>::emplace(vector<T>::const_iterator position, Ts&&...args)

You use placement new to construct the obejct. This is ILLEGAL as you are calling new on an object whoses lifetime has not ended.

    new(m_data + offset - 1)T(std::forward<Ts>(args)...);

Two alternative are possible. A) End the lifetime of the object (then call new) B) create a new object and move it to that location:

// End Lifetime:
m_data[offset].~T();
new(m_data + offset)T(std::forward<Ts>(args)...);

// Create and move object.
m_data[offset] = T(std::forward<Ts>(args)...); // This will move.

---

Still in emplace():

Why do you use -1 here?

    new(m_data + offset - 1)T(std::forward<Ts>(args)...);

In all the above insert() uses cases the position of insert is at m_data + offset. What has changed here?

---

Inline comments:

template<typename T>
void vector<T>::reserve(size_type size) {
    if (size == 0) {
        size = INITIAL_CAPACITY;
    }
    // Don't think you want the "else" here.
    //
    // Otherwise by setting a reserve of zero you will also
    // force a resize to a smaller size when no other resize
    // forces a reduction of a size.
    else if (size <= m_capacity) {
        return;
    }

    // You shoudl hold this in `std::unique_ptr`
    // If the next loop throws while moving/copying elements
    // you will leak the object.
    T* newData = nullptr;
    allocateMemory_(newData, size);

    // You should only use move here if the type T
    // gurnatees that T has a nothrow move constructor.
    // otherwise you need to use copy to ensure that
    // you provide the strong exception gurantee.
    size_type i = 0;
    for (; i < m_size; ++i) {
        new(newData + i)T(std::move(m_data[i]));
    }


    // If calling the destructor of any of the T object
    // throws an exception then you will leave your object in
    // an invalid state.
    //
    // better to swap the state of the current object and the
    // temporary array first. Then you can destroy the old arry.
    clear();

    m_data = newData;
    m_capacity = size;
    m_size = i;
}

I would write it like this:

template<typename T>
void vector<T>::reserve(size_type size) {

    if (size == 0) {
        size = INITIAL_CAPACITY;
    }
    if (size <= m_capacity) {
        return;
    }
    std::vector<T>  tmp(size);   // remember you constructor sets capacity.

    // Copy if you can't move.
    for(auto& item: *this) {
        tmp.emplace_back(std::move(item));
    } 

    swap(tmp);
}

---

You should mark swap() as noexcept:

template<typename T>
void vector<T>::swap(vector& rhs) {

---

Comments inline:

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);
    }

    // You can only use `placement new` when you are copying elements beyond
    // m_size. Any elements that are being moved into the current array size
    // must use a normal assignment (move or copy).
    //
    // So the first `space` elements you can use placement new.
    // After that you must use assignment.
    //
    // Also most of the methods that use this method assume that
    // they will be copying into an array of objects whose life time
    // has been started. So for large values of `space` where you 
    // moving a small number of elements beyond the end of the array
    // you will need to default construct the object
    for (int i = 0; i < elementsToMove; ++i) {
        new(m_data + m_size + space - i) T(std::move(m_data[m_size - i]));
    }
}

---

I don't think this is correct:

template<typename T>
bool operator>=(const vector<T>& lhs, const vector<T>& rhs) {
    return !(lhs < rhs);
}

Answer 3

Iterators don't need to be friends with class vector

The iterator classes do not need access to private members of vector, so the friend declarations can be removed.

Mistakes when using *this

There are bugs in your implementation, mainly because you do things like:

BDIterator operator++(int) {
    BDIterator res(*this);
    ++(*this);
    return res;
}

The line ++(*this) should have just been ++m_address. In this case it works out, but in the case of the reverse iterator, you introduced a bug:

BDRIterator operator++(int) {
    BDRIterator res(*this);
    --(*this);
    return res;
}

Because you call --(*this), it will actually call BDRIterator::operator--() on itself, which will move the pointer in the wrong direction. I suggest you avoid using *this except when really necessary, like when a function needs to return a reference to its own object.

Use the right template parameter

class BDRIterator is a template with template parameter DataType, however several declarations inside it refer to T, which is wrong.

Unnecessary while-loops

I see you are using while-loops in operator+=() and operator-=(), but not in operator+ and operator-. I guess that is to avoid circular references because, again, you are using *this when you shouldn't. Just have all these operators operator directly on m_address instead.

Reverse iterator undefined behavior

If you have a pointer to an array, only pointers to elements inside the array, and a pointer right past the end of the array (where the next element would be if it were one element larger) are valid. In your case, rend() points to an address before the start of the array, and thus might invoke undefined behaviour. The fact that base() exists and points to one element further than what the reverse iterator should point to should have been a hint: you have to make rbegin() point to the same address as end(), and rend() the same as begin(). This means it will be one off, but you should just account for that in the dereferencing operators.

The documentation for std::reverse_iterator has a clear diagram of how you should implement it.