C++ vector implementation

I have tried to implement a basic vector type in C++, yet I am not sure if I can do anything any more efficiently.

```
template class vector
{
public:
typedef _Ty *iterator;
typedef _Ty _Value_type;
typedef vector _Myt;
vector()
: __size(0), __capacity(10), __data((_Value_type *)calloc(10, sizeof(_Value_type)))
{
}
vector(_Myt &_Rhs)
: __data((_Value_type *)calloc((__capacity = _Rhs.size() + 10), sizeof(_Value_type)))
{
memcpy(__data, _Rhs.__data, (__size = _Rhs.size()) * sizeof(_Value_type));
}
~vector()
{
memset(__data, NULL, 1);
}
_Value_type *data() const
{
return __data;
}
_Myt &push_back(const _Value_type &_Rhs)
{
if (++__size > __capacity)
{
reserve(__capacity + 10);
}
__data[__size - 1] = _Rhs;
return *this;
}
_Myt &operator+=(const _Value_type &_Rhs)
{
return push_back(_Rhs);
}
UINT size() const
{
return __size;
}
UINT capacity() const
{
return __capacity;
}
iterator begin() const
{
return &__data[0];
}
iterator rbegin()
{
return reversed_adaptor().begin();
}
iterator end() const
{
return &__data[__size];
}
iterator rend()
{
return reversed_adaptor().end();
}
iterator find(const _Value_type &_Search) const
{
for (iterator i = begin(); i != end(); ++i)
{
if (*i == _Search)
{
return i;
}
}
return NULL;
}
bool contains(const _Value_type &_Search) const
{
return find(_Search) != NULL;
}
_Myt &operator=(_Myt &_Rhs)
{
reserve((__size = _Rhs.size()) + 10);
memcpy(__data, _Rhs.__data, _Rhs.size() * sizeof(_Value_type));
return *this;
}
_Value_type pop_back()
{
_Value_type temp = __data[__size -= 1

Some other points, in completely random order as I came across them...

-
pop_back, pop_front and erase should have return type void

The reason here is that most of the time the caller does not need the erased object and if you return it, the copy has to be made and it can be pretty expensive. Filling a vector (if done properly, see 3. below) amortizes to just 2 copies per inserted element, so vector is a good choice even for quite complex objects and you don't want useless extra copies.

-
calloc is pointless, since you are obliged to construct the objects anyway.

-
reserve(__capacity + 10); in push_back is violation of the complexity contract.

push_back is required amortized O(1), which means the reallocation has to be in geometric sequence. Usual values are reserve(__capacity * 2) or reserve(__capacity + (__capacity+1)/2), and minimal capacity of 16 or so.

-
Just like the realloc already mentioned by ChrisW, calling memcpy on array containing non-POD objects (and vector is for containing non-POD objects) is an UndefinedBehaviour™.

The compiler may choose to do anything it pleases from simply crashing all the way over formatting your hard drive to making daemons fly out of your nose. And modern compilers can be real bitches when punishing UndefinedBehaviour™. Effect of some optimizations applied to incorrect code is next to impossible to understand.

You have to copy the elements one by one with std::copy or a loop to properly invoke constructors and you have to call destructors afterwards.

-
Assigning to unconstructed memory in push_back and resize is also UndefinedBehaviour™.

Non-POD object has to be constructed by constructor and destructed by destructor. Use the placement new:

new (i) _Value_type(_Rhs);

-
C++ does not have any type called UINT.

The size type should always be std::size_t

-
swap() method is another violation of the complexity contract.

Vector swap() is supposed to be O(1). It should simply swap the pointers. That's far from what std::swap would do in C++03 (in C++11 it could do the right thing if you defined the move constructors, but you didn't).

Furthermore std::swap should be overloaded for vector to call the swap() method. Yes, you are allowed and sometimes required to overload functions/specialize classes in std for types you define and this is one such case.

-
You correctly use reserve in push_back, but you fail to do the same in insert.

-
The special condition for i == end() in erase is superfluous.

It is not allowed to pass non-deferrable iterator (end or invalid) to erase.

-
Your erase returns useless element (but see 1. anyway).

You return the value of the final pop_back, which returns the last element. If you deleted any other element than the last, it's not the one that was just deleted. Completely useless. You shouldn't be returning anything anyway.

-
Const correctness failures.

A const method should only ever return pointers and references to const.

Standard collections have iterator and const_iterator and all methods that return iterators (begin(), end(), find() etc.) have non-const overload returning iterator and const overload returning const_iterator. If you use plain pointers (which is legal, the iterator concept is designed so that pointers are iterators), you should define const_iterator to _Value_type const * (const applies to the part before it, so this is the correct syntax; even in C).

-
rbegin and rend return dangling pointers (provided you fix the memory leak in destructor).

Another instance of UndefinedBehaviour™. The reversed_adaptor returns a new instance. By value, which is inefficient, but legal. However the return value is temporary and it will only have to have begin/end called on it and than it will be destroyed at the next semicolon. When you fix the memory leak and actually free the memory in destructor, the returned pointers will point to unallocated memory.

-
rbegin and rend don't return valid iterators to invocant.

The reverse iterators have to point to the container, not to a copy. Since you can't use plain pointers for reverse operators, it's rather a lot of work to define them. Boost has a generic implementation

-
You are missing most of the required typedefs.

There should be value_type, reference, pointer, const_reference, const_pointer, const_iterator, reverse_iterator, const_reverse_iterator, size_type (should be std::size_t) and difference_type (should be std::ptrdiff_t). And allocator_type, which is next point.

-
You should be using allocator instead of malloc and free.

Allocator abstracts the memory allocation, wraps the funny placement new and explicit destructor call syntaxes and makes the allocation and construction separate actions as appropriate for likes of vector.

The default allocator, std::allocator uses global operators new[] and delete[] for al

StackExchange Code Review Q#42297, answer score: 8