Reimplementation of C++ vector

Question

I previously attempted to make a C++ vector here, yet it was not very successful. Now I have made a basic reimplementation of it, so I'm checking that it is fine, and that I will not have to re make it again.

Note: I also implemented an allocator class, but it works the same as the std:: equivalent.

template < typename _Ty, typename _Alloc = allocator<_Ty> > class vector
{
public:
 typedef vector<_Ty, _Alloc> _Myt;
 typedef _Ty value_type;
 typedef _Alloc allocator_type;
 typedef value_type *pointer;
 typedef const value_type *const_pointer;
 typedef value_type *iterator;
 typedef const value_type *const_iterator;
 typedef value_type &reference;
 typedef const value_type &const_reference;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 vector()
 : __size(0), __capacity(20), __data(_Alloc().allocate(20))
 {
 }
 vector(const _Myt &_Rhs)
 : __size(_Rhs.__size), __capacity(_Rhs.__size + 20), __data(_Alloc().allocate(_Rhs.__size))
 {
 int count = 0;
 for (iterator i = &_Rhs.__data[0]; i != &_Rhs.__data[_Rhs.__size]; ++i, ++count)
 {
 _Alloc().construct(&__data[count], *i);
 }
 }
 ~vector()
 {
 if (!empty())
 {
 for (iterator i = begin(); i != end(); ++i)
 {
 _Alloc().destroy(i);
 }
 _Alloc().deallocate(__data, __capacity);
 }
 }
 _Myt &push_back(const value_type &_Value)
 {
 if (++__size >= __capacity)
 {
 reserve(__capacity * 2);
 }
 _Alloc().construct(&__data[__size - 1], _Value);
 return *this;
 }
 _Myt &push_front(const value_type &_Value)
 {
 if (++__size >= __capacity)
 {
 reserve(__capacity * 2);
 }
 if (!empty())
 {
 iterator _e = end(), _b = begin();
 std::uninitialized_copy(_e - 1, _e, _e);
 ++_e;
 std::copy_backward(_b, _e - 2, _e - 1);
 }
 _Alloc().construct(&__data[0], _Value);
 return *this;
 }
 _Myt &reserve(size_type _Capacity)
 {
 int count = 0;
 if (_Capacity < __capacity)
 {
 return *this;
 }
 pointer buf = _Alloc().allocate(_Capacity);
 for (iterator i = begin(); i != end(); ++i, ++count)
 {
 _Alloc().construct(&buf[count], *i);
 }
 std::swap(__data, buf);
 for (iterator i = &buf[0]; i != &buf[__capacity]; ++i)
 {
 _Alloc().destroy(i);
 }
 _Alloc().deallocate(buf, __capacity);
 __capacity = _Capacity;
 return *this;
 }
 iterator begin()
 {
 return &__data[0];
 }
 iterator end()
 {
 return &__data[__size];
 }
 size_type size()
 {
 return __size;
 }
 size_type capacity()
 {
 return __capacity;
 }
 bool empty()
 {
 return !__data;
 }
 const_pointer data()
 {
 return __data;
 }
private:
 pointer __data;
 size_type __size, __capacity;
};

• TemplateRex: Where are your test cases? And please, carefully check signatures of all members against 23.3.6 of the draft Standard

Answer 1

STOP USING __ its reserved for the implementation.

Basically stop using underscore until you know the rules. This code is basically all broken because of this. You code technically is all undefined.
We told you this before. STOP IT.

BUG:

vector(const _Myt &_Rhs)
 : __size(_Rhs.__size), __capacity(_Rhs.__size + 20), __data(_Alloc().allocate(_Rhs.__size))

You are only allocating size space. But your capacity is 20 bytes larger.
Why 20 bytes? Should this not be 20 objects 20 * sizeof(_Ty)

BUG:

You use the allocator construct routines when you are doing placement new. This means the space has not been constructed before. If the location has already got an element in it you must copy over it using the copy constructor.

Thus in

_Myt &push_front(const value_type &_Value)

This line:

 _Alloc().construct(&__data[0], _Value);

You are constructing into location 0 a new object without calling the old objects destructor. If your type is anything non trivial this will screw up any memory management.

BUG

bool empty()
{
 return !__data; // Both constructors allocate memory.
} // So this will never be true.

I think you mean

 return size != 0;

You have a potential leak situation in your reserve().
You provide the strong exception gurantee. BUT if the copy fails (with an exception) then you will leak the buffer. You need to hold the buffer in a smart pointer until you swap so that if there is an exception you gurantee that you deallocate the unused buffer.

Answer 2

You're still using leading underscores. Why?? They're reserved.

Methods like size should be const:

size_type size() const
{
 return __size;
}

The empty method should return size() == 0, not !__data.

The reserve method should return void.

In reserve I think that destroying everything up to buf[__capacity] is a mistake: instead, destroy everything up to buf[__size].

Because of the above, in push_front and push_back don't increment size before you call reserve.