Having already attempted an implementation of the std::vector class here, I decided to take the comments on board and also do some new bits myself (mainly the algorithms for allocation and insert).

I have a commented version, but it exceeded the character limit so I had to add the non-commented version. However, I can provide specific commented functions if you would like in the comment section.

The main reason for doing this was to check that I am doing everything safely, which I am more confident about this time, as I have never had errors during the process, while in my previous implementation, I had some errors when testing it and had to fix those a few times, but also to check the efficiency of the code and if I could make some algorithms/functions better.

# ifndef __VECTOR_H__
# define __VECTOR_H__

# include <memory>
# include <algorithm>

template<typename T,
    typename A>
    class vector;

template<typename B, 
    typename R>
    class vector_iterator;

template<typename I>
    class vector_reverse_iterator;

template<typename A>
    class vector_base
    {
public:
    typedef vector_base<A> base_type;
    typedef typename A allocator_type;
    typedef typename A::pointer pointer;
    friend class vector<typename A::value_type, A>;
    friend class vector_iterator<base_type, typename A::reference>;
    friend class vector_iterator<base_type, typename A::const_reference>;
    friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >;
    friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >;

private:
    vector_base(allocator_type const &al)
    : ms_begin(pointer()),
    s_end(pointer()),
    m_end(pointer()),
    alloc(al)
        {
        }

    ~vector_base()
        {
        }

    base_type *get_base()
        {
        return (this);
        }

    pointer ms_begin, s_end, m_end;
    allocator_type alloc;
    };

# ifndef VECTOR_ITERATOR_CHECK_LEVEL
# define VECTOR_ITERATOR_CHECK_LEVEL 1
# endif

template<typename B,
    typename R = typename B::allocator_type::reference>
    class vector_iterator
    {
public:
    typedef vector_iterator<B, R> this_t;
    typedef B base_type;
    typedef typename B::allocator_type::pointer pointer;
    typedef typename R reference;
    typedef typename B::allocator_type::const_reference const_reference;
    typedef typename B::allocator_type::value_type value_type;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    friend class vector<value_type, typename B::allocator_type>;
    friend class vector_reverse_iterator<this_t>;
    friend class vector_reverse_iterator<vector_iterator<B, const_reference> >;
    friend class vector_iterator<B, const_reference>;

    vector_iterator(base_type *b, pointer p)
        : base(b),
        ptr(p)
        {
        }

    template<typename R = reference>
    vector_iterator(vector_iterator<B, R> const &rhs)
        : base(rhs.base),
        ptr(rhs.ptr)
        {
        }

    ~vector_iterator()
        {
        }

    this_t &operator=(this_t const &rhs)
        {
        base = rhs.base;
        ptr = rhs.ptr;
        return (*this);
        }

    this_t &operator++()
        {
        ++ptr;
        return (*this);
        }

    this_t operator++(int)
        {
        this_t temp(*this);
        ++ptr;
        return (temp);
        }

    this_t &operator--()
        {
        --ptr;
        return (*this);
        }

    this_t operator--(int)
        {
        this_t temp(*this);
        --ptr;
        return (temp);
        }

    this_t operator+(size_type offset) const
        {
        return (this_t(base, ptr + offset));
        }

    this_t operator-(size_type offset) const
        {
        return (this_t(base, ptr - offset));
        }

    difference_type operator-(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (ptr - rhs.ptr);
        }

    this_t &operator+=(size_type offset)
        {
        ptr += offset;
        return (*this);
        }

    this_t &operator-=(size_type offset)
        {
        ptr -= offset;
        return (*this);
        }

    reference operator*() const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(*this, ptr_in_seq);
# endif
        return (*ptr);
        }

    reference operator[](size_type offset) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(this_t(base, ptr + offset), ptr_in_seq);
# endif
        return (*(ptr + offset));
        }

    pointer operator->() const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(*this, ptr_in_seq);
# endif
        return (ptr);
        }

    bool operator==(this_t const &rhs) const
        {
        return (ptr == rhs.ptr);
        }

    bool operator!=(this_t const &rhs) const
        {
        return (!((*this) == rhs));
        }

    bool operator<(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (ptr < rhs.ptr);
        }

    bool operator>(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (ptr > rhs.ptr);
        }

    bool operator<=(this_t const &rhs) const
        {
        return (!(ptr > rhs.ptr));
        }

    bool operator>=(this_t const &rhs) const
        {
        return (!(ptr < rhs.ptr));
        }

private:
    pointer ptr;
    base_type *base;

    static void check_validity(this_t const &it, bool (*test)(this_t const &))
        {
        if (!test(it))
            {
            throw std::exception("iterator out of range");
            }
        }

    void check_compatible(this_t const &it) const
        {
        if (it.base != base)
            {
            throw std::exception("iterators incompatible (not in same container)");
            }
        }

    static bool ptr_in_seq(this_t const &it)
        {
        return (it.ptr >= it.base->ms_begin && 
            it.ptr < it.base->s_end);
        }

    static bool ptr_in_seq_or_end(this_t const &it)
        {
        return (it.ptr >= it.base->ms_begin && 
            it.ptr <= it.base->s_end);
        }
    };

template<typename I>
    class vector_reverse_iterator
    {
public:
    typedef vector_reverse_iterator<I> this_t;
    typedef typename I::base_type base_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
    typedef typename I::const_reference const_reference;
    typedef typename I::size_type size_type;
    typedef typename I::difference_type difference_type;

    friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >;

    vector_reverse_iterator(I const &it)
        : base(it.base)
        {
        size_type from_begin = (it.ptr - it.base->ms_begin) + 1;
        ptr = (it.base->s_end - from_begin);
        }

    template<typename R = reference>
    vector_reverse_iterator(vector_reverse_iterator<
            vector_iterator<base_type, R> > const &rhs)
        : base(rhs.base),
        ptr(rhs.ptr)
        {
        }


    ~vector_reverse_iterator()
        {
        }

    this_t &operator=(this_t const &rhs)
        {
        base = rhs.base;
        ptr = rhs.ptr;
        return (*this);
        }

    this_t &operator++()
        {
        --ptr;
        return (*this);
        }

    this_t operator++(int)
        {
        this_t temp(*this);
        --ptr;
        return (temp);
        }

    this_t &operator--()
        {
        ++ptr;
        return (*this);
        }

    this_t operator--(int)
        {
        this_t temp(*this);
        ++ptr;
        return (temp);
        }

    this_t operator+(size_type offset) const
        {
        return (this_t(base, ptr - offset));
        }

    this_t operator-(size_type offset) const
        {
        return (this_t(base, ptr + offset));
        }

    difference_type operator-(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (rhs.ptr - ptr);
        }

    this_t &operator+=(size_type offset)
        {
        ptr -= offset;
        return (*this);
        }

    this_t &operator-=(size_type offset)
        {
        ptr += offset;
        return (*this);
        }

    reference operator*() const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(*this, ptr_in_seq);
# endif
        return (*ptr);
        }

    reference operator[](size_type offset) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(this_t(base, ptr - offset), ptr_in_seq);
# endif
        return (*(ptr + offset));
        }

    pointer operator->() const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_validity(*this, ptr_in_seq);
# endif
        return (ptr);
        }

    bool operator==(this_t const &rhs) const
        {
        return (ptr == rhs.ptr);
        }

    bool operator!=(this_t const &rhs) const
        {
        return (!((*this) == rhs));
        }

    bool operator<(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (ptr > rhs.ptr);
        }

    bool operator>(this_t const &rhs) const
        {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
        check_compatible(rhs);
# endif
        return (ptr < rhs.ptr);
        }

    bool operator<=(this_t const &rhs) const
        {
        return (!(ptr < rhs.ptr));
        }

    bool operator>=(this_t const &rhs) const
        {
        return (!(ptr > rhs.ptr));
        }

private:
    pointer ptr;
    base_type *base;

    static void check_validity(this_t const &it, bool (*test)(this_t const &))
        {
        if (!test(it))
            {
            throw std::exception("iterator out of range");
            }
        }

    void check_compatible(this_t const &it) const
        {
        if (it.base != base)
            {
            throw std::exception("iterators incompatible (not in same container)");
            }
        }

    static bool ptr_in_seq(this_t const &it)
        {
        return (it.ptr > (it.base->ms_begin - 1) && 
            it.ptr <= (it.base->s_end - 1));
        }

    static bool ptr_in_seq_or_end(this_t const &it)
        {
        return (it.ptr >= (it.base->ms_begin - 1) && 
            it.ptr <= (it.base->s_end - 1));
        }
    };

template<typename T,
    typename A = std::allocator<T> >
    class vector
        : public vector_base<A>
    {
public:
    typedef typename A::value_type value_type;
    typedef typename A::const_pointer const_pointer;
    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef vector_iterator<base_type> iterator;
    typedef vector_iterator<base_type, const_reference> const_iterator;
    typedef vector_reverse_iterator<iterator> reverse_iterator;
    typedef vector_reverse_iterator<const_iterator> const_reverse_iterator;
    typedef vector<T, A> this_t;

    explicit vector(allocator_type const &al = allocator_type())
        : base_type(al)
        {
        }

    explicit vector(size_type count, const_reference value = value_type(),
        allocator_type const &al = allocator_type())
        : base_type(al)
        {
        assign(count, value);
        }

    template<typename InIt>
    vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first,
        typename std::enable_if<!std::is_integral<InIt>::value, InIt> last,
        allocator_type const &al = allocator_type())
        : base_type(al)
        {
        assign(first, last);
        }

    vector(this_t const &rhs)
        : base_type(rhs.alloc)
        {
        if (&rhs != this)
            {
            assign(rhs.ms_begin, rhs.s_end);
            }
        }

    void assign(size_type count, value_type const &value = value_type())
        {
        if (is_unconstructed())
            {
            allocate(count * 1.5);
            }
        else
            {
            if (count > capacity())
                {
                reallocate(count * 1.5);
                }
            wipe_values();
            }
        this->s_end = std::uninitialized_fill_n(
            this->ms_begin, count, value);
        }

    template<typename InIt>
    typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
        {
        difference_type count = (last - first);
        if (is_unconstructed())
            {
            allocate(count * 1.5);
            }
        else
            {
            if (count > capacity())
                {
                reallocate(count * 1.5);
                }
            wipe_values();
            }
        this->s_end = std::uninitialized_copy(
            first, last, this->ms_begin);
        }

    this_t &operator=(this_t const &rhs)
        {
        if (&rhs != this)
            {
            assign(rhs.ms_begin, rhs.s_end);
            }
        return (*this);
        }

    iterator erase(iterator where)
        {
        return (erase(where, where + 1));
        }

    iterator erase(iterator first, iterator last)
        {
        iterator::check_validity(first, iterator::ptr_in_seq);
        iterator::check_validity(last, iterator::ptr_in_seq_or_end);
        difference_type diff = (last - first);
        size_type fpos = (first.ptr - this->ms_begin), 
            lpos = (last.ptr - this->ms_begin);
        std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end);
        while (diff--)
            {
            this->alloc.destroy(--this->s_end);
            }
        return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first))));
        }

    void insert(iterator where, const value_type &value = value_type())
        {
        insert(where, 1, value);
        }

    void insert(iterator where, unsigned count, const value_type &value = value_type())
        {
        iterator::check_validity(where, iterator::ptr_in_seq_or_end);
        size_type wpos = (where.ptr - this->ms_begin);
        if (is_unconstructed())
            {
            allocate(count * 1.5);
            }
        else
            {
            if (size() + count > capacity())
                {
                reallocate((size() + count) * 1.5);
                }
            }
        size_type c2 = count;
        while (c2--)
            {
            this->alloc.construct(this->s_end++, value);
            }
        std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end);
        }

    template<typename InIt>
    typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last)
        {
        iterator::check_validity(where, iterator::ptr_in_seq_or_end);
        size_type wpos = (where.ptr - this->ms_begin);
        difference_type diff = (last - first);
        if (is_unconstructed())
            {
            allocate(diff * 1.5);
            }
        else
            {
            if (size() + diff > capacity())
                {
                reallocate((size() + diff) * 1.5);
                }
            }
        while (first != last)
            {
            this->alloc.construct(this->s_end++, first++);
            }
        std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end);
        }

    void push_back(value_type const &value)
        {
        insert(end(), value);
        }

    void pop_back()
        {
        erase(end() - 1);
        }

    void clear()
        {
        erase(begin(), end());
        }

    iterator begin()
        {
        return (iterator(this->get_base(), this->ms_begin));
        }

    iterator end()
        {
        return (iterator(this->get_base(), this->s_end));
        }

    const_iterator begin() const
        {
        return (const_iterator(this->get_base(), this->ms_begin));
        }

    const_iterator end() const
        {
        return (const_iterator(this->get_base(), this->s_end));
        }

    reverse_iterator rbegin()
        {
        return (reverse_iterator(begin()));
        }

    reverse_iterator rend()
        {
        return (reverse_iterator(end()));
        }

    const_reverse_iterator rbegin() const
        {
        return (const_reverse_iterator(begin()));
        }

    const_reverse_iterator rend() const
        {
        return (const_reverse_iterator(end()));
        }

    reference operator[](size_type offset)
        {
        return (*(this->ms_begin + offset));
        }

    const_reference operator[](size_type offset) const
        {
        return (*(this->ms_begin + offset));
        }

    reference front()
        {
        return (*this->ms_begin);
        }

    const_reference front() const
        {
        return (*this->ms_begin);
        }

    reference back()
        {
        return (*(this->s_end - 1));
        }

    const_reference back() const
        {
        return (*(this->s_end - 1));
        }

    reference at(size_type offset)
        {
        if (offset >= size())
            {
            throw std::exception("offset out of bounds");
            }
        return (*(this->ms_begin + offset));
        }

    const_reference at(size_type offset) const
        {
        if (offset >= size())
            {
            throw std::exception("offset out of bounds");
            }
        return (*(this->ms_begin + offset));
        }

    void reserve(size_type count)
        {
        if (count > capacity())
            {
            reallocate(count);
            }
        }

    void resize(size_type count, value_type value = value_type())
        {
        if (count < size())
            {
            erase(begin() + count, end());
            }
        else
            {
            reserve(count);
            insert(end(), count - size(), value);
            }
        }

    void swap(this_t &rhs)
        {
        base_type b = *(this->get_base());
        *(this->get_base()) = *(rhs.get_base());
        *(rhs.get_base()) = b;
        }

    size_type size() const
        {
        return (this->s_end - this->ms_begin);
        }

    size_type capacity() const
        {
        return (this->m_end - this->ms_begin);
        }

    allocator_type get_allocator() const
        {
        return (this->alloc);
        }

    bool empty() const
        {
        return (this->ms_begin == this->s_end);
        }

private:
    void allocate(size_type count)
        {
        if (count > this->alloc.max_size())
            {
            throw std::exception("unable to allocate memory");
            }
        this->ms_begin = this->alloc.allocate(count);
        this->s_end = this->ms_begin;
        this->m_end = this->ms_begin + count;
        }

    void reallocate(size_type count)
        {
        if (count > this->alloc.max_size())
            {
            throw std::exception("unable to allocate memory");
            }
        pointer nbegin = this->alloc.allocate(count);
        std::uninitialized_copy(this->ms_begin, this->s_end, nbegin);
        size_type sz = size();
        wipe_all();
        this->ms_begin = nbegin;
        this->s_end = nbegin + sz;
        this->m_end = nbegin + count;
        }

    void wipe_values()
        {
        if (!is_unconstructed())
            {
            size_type sz = size();
            while (this->ms_begin != this->s_end)
                {
                this->alloc.destroy(this->ms_begin++);
                }
            this->ms_begin -= sz;
            }
        }

    void wipe_all()
        {
        if (!is_unconstructed())
            {
            wipe_values();
            this->alloc.deallocate(this->ms_begin, capacity());
            this->ms_begin = pointer();
            this->s_end = pointer();
            this->m_end = pointer();
            }
        }

    bool is_unconstructed() const
        {
        return (this->ms_begin == pointer());
        }
    };

# endif
  • My goodness gracious. Thats a lot. – Martin York Jul 9 '15 at 19:18

Double underscore is reserved.

# ifndef __VECTOR_H__
# define __VECTOR_H__

These are technically illegal identifers as they are reserved for the implementation. refrain from using "double underscore" anywhere or and a single underscore as a prefix. Even if you know the rules like me others (like you) don't so best to avoid them.

I don't think this is technically legal.

# include <memory>
# include <algorithm>

The directive is "#include". Not all pre-processors are going to support this. So get out of that habit. Remember that the pre-processor phase happens before the compiler is invoked (though modern compilers roll it all it to one).

Even if it was legal I would advice against it as it is non standard and makes people second guess that it is going to work.

Style:

Having a hard time reading your code

Your indentation style is making it hard to read the code.

template<typename T,
    typename A>
    class vector;

Hard to see the class part. Align the types if you think it is two long. But put the class back under the template.

template<typename T, typename A>
class vector;

// or

template< typename T, // I would use this style only if the number/size
          typename A> // of templates was going to overwhelm the line.
class vector;

Another example:

vector_base(allocator_type const &al)
: ms_begin(pointer()),
s_end(pointer()),
m_end(pointer()),
alloc(al)
    {
    }

Nothing really lines up so I find it hard to parse.

vector_base(allocator_type const &al)
    : ms_begin(pointer())
    , s_end(pointer())
    , m_end(pointer())
    , alloc(al) 
    {
    }

OK. Putting the braces {} indented is something I personally don't like. But that is an accepted standard style so; though I don't personally like it you should be OK with that as long as you are following the coding conventions of your office.

Be consistent with your indenting.

    if (is_unconstructed())
        {
        allocate(count * 1.5);
        }
    else
        {
        if (count > capacity())
            {
            reallocate(count * 1.5);
            }
        wipe_values(); 
        }

Argg. Poop. I just realized you were consistent. But just emphasis why I hate this style.

Members:

Having a hard time spotting your class members. You need to make those more abvious (and put them at the top). so I can validate that your constructor actually correctly initializes all members.

DRY your code

The code in these two function looks nearly identical.
You should try and put common code into a single location. So when you fix a bug you only have to fix a bug in one place (not in multiple places).

void assign(size_type count, value_type const &value = value_type())
    {
    if (is_unconstructed())
        {
        allocate(count * 1.5);
        }
    else
        {
        if (count > capacity())
            {
            reallocate(count * 1.5);
            }
        wipe_values();
        }
    this->s_end = std::uninitialized_fill_n(
        this->ms_begin, count, value);
    }

template<typename InIt>
typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
    {
    difference_type count = (last - first);
    if (is_unconstructed())
        {
        allocate(count * 1.5);
        }
    else
        {
        if (count > capacity())
            {
            reallocate(count * 1.5);
            }
        wipe_values();
        }
    this->s_end = std::uninitialized_copy(
        first, last, this->ms_begin);
    }

Not sure I like the fact you have different behavior for a newly constructed verses an old vector if (is_unconstructed()). Seems like the stuff for a new vector only belongs in the constructor.

Did not realize how much I disliked that brace style until now.

Sorry I can't keep going.

  • Sorry about my indentations but I personally love it that way (I think it's the Whitesmith style even if I have slightly adapted it). – Joe Jul 9 '15 at 21:18
  • @joe I too, vehemently dislike this brace style. Also while this is a good answer, you should wait a while before accepting to give other users a chance to see your question and answer. – Emily L. Jul 9 '15 at 22:10
  • @Joe: What Emily. Said that is way to quick to accept an answer. Give others a chance to chime in. As I said I really dislike your brace style, but it is one that I have seen others use. BUT coding is a cooperative venture you need to adhere to the standards the team agrees on otherwise things break down. So as long as the others in your team are using the same style that's fine. – Martin York Jul 9 '15 at 22:30
  • I came to furiously type that I really hate that way of indenting code. – Dietr1ch Jul 10 '15 at 1:37

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.