So the C++ standard specifies a set of requirements for containers. Very few requirements are specified in terms of containers so adhering to these exactly is not required (unless you want to be considered for the standard). But they provide an insight into what can be done with them and if you support them will allow your container to be more easily used with some features of the language and standard library. I am not going to go over all of them here (that is left as an exercise for the reader), but I will go over the ones I would expect to see in a simple implementation (the kind you would see in a university project).
For details see the latest copy of the C++ standard.
- 23.2.1 General container requirements [container.requirements.general]
- 23.2.3 Sequence containers [sequence.reqmts]
Internal Types
- value_type
- reference
- const_reference
- iterator
- const_iterator
- difference_type
- size_type
It is worth specifying the internal types defined here. As this allows you to abstract the implementation details of the container. This will allow you to change the implementation details without users having to change their implementation; as long as the changes still provide the same interface but the interface to reference/pointers/iterators are relatively trivial and well defined.
Constructors
In C++11 the std::initializer_list<T>
was introduced. This allows a better list initialization syntax to be used with user defined types. Since this is usually defined in terms of the range based construction we should probably add both of these constructors.
- Vector(std::initializer_list<T> const& list)
- Vector(I begin, I end)
Iterators
- begin()
- rbegin()
- begin() const
- rbegin() const
- cbegin() const
- crbegin() const
- end()
- rend()
- end() const
- cend() const
- rend() const
- crend() const
The iterators are relatively easy to write. They also allow the container to be used with the new range based for that was added in C++14. So this becomes another easy add.
Member Access
- at(<index>)
- at(<index>) const
- operator[](<index>)
- operator[](<index>) const
- front()
- back()
- front() const
- back() const
Member access to a vector should be very efficient. As a result normally range checks are not performed on member access, i.e. the user is expected to make sure that the method preconditions have been met before calling the method. This results in very efficient access to the members of a Vector
. This is not normally a problem because index ranges are normally checked as part of a loop range as long as these are validated against the size of the array it does not need to be validated again.
For Loop Vector Access
Vector<T> d = getData();
for(int loop = 0; loop < d.size(); ++loop)
{
std::cout << d[loop];
}
There is also the at()
method which does validate the index provided before accessing the element (throwing an exception if the index is out of range).
Non-Mutating Member Functions
- size() const
- bool() const
To allow us to check the preconditions on the element access methods we need some functions that check the state of the object. These are provided here.
Mutating Member Functions
- push_back(<object-ref>)
- push_back(<object-rvalue-ref>)
- emplace_back(<args...>)
- pop_back()
The following members are standard easy to implement methods of std::vector
(O(1)) that I would expect to see in every implementation.
The other mutating member functions are less trivial as they require elements to be moved around. They are not that hard but you must put some thought into the most efficient techniques to move elements (i.e. move or copy) and make sure that capacity is not exceeded by multiple inserts. As a result I would expect to see these methods only on an as needed basis.
Comparators
- operator== const
- operator!= const
Easy comparison operators.
Optionally you can provide the other comparison operators.
Final
No idea why Jackal is adding all the blank lines to my source
Vector
#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>
template<typename T>
class Vector
{
public:
using value_type = T;
using reference = T&;
using const_reference = T const&;
using pointer = T*;
using const_pointer = T const*;
using iterator = T*;
using const_iterator = T const*;
using riterator = std::reverse_iterator<iterator>;
using const_riterator = std::reverse_iterator<const_iterator>;
using difference_type = std::ptrdiff_t;
using size_type = std::size_t;
private:
size_type capacity;
size_type length;
T* buffer;
struct Deleter
{
void operator()(T* buffer) const
{
::operator delete(buffer);
}
};
public:
Vector(int capacity = 10)
: capacity(capacity)
, length(0)
, buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
{}
template<typename I>
Vector(I begin, I end)
: capacity(std::distance(begin, end))
, length(0)
, buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
{
for(auto loop = begin;loop != end; ++loop)
{
pushBackInternal(*loop);
}
}
Vector(std::initializer_list<T> const& list)
: Vector(std::begin(list), std::end(list))
{}
~Vector()
{
std::unique_ptr<T, Deleter> deleter(buffer, Deleter());
clearElements<T>();
}
Vector(Vector const& copy)
: capacity(copy.length)
, length(0)
, buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
{
try
{
for(int loop = 0; loop < copy.length; ++loop)
{
push_back(copy.buffer[loop]);
}
}
catch(...)
{
std::unique_ptr<T, Deleter> deleter(buffer, Deleter());
clearElements<T>();
throw;
}
}
Vector& operator=(Vector const& copy)
{
copyAssign<T>(copy);
return *this;
}
Vector(Vector&& move) noexcept
: capacity(0)
, length(0)
, buffer(nullptr)
{
move.swap(*this);
}
Vector& operator=(Vector&& move) noexcept
{
move.swap(*this);
return *this;
}
void swap(Vector& other) noexcept
{
using std::swap;
swap(capacity, other.capacity);
swap(length, other.length);
swap(buffer, other.buffer);
}
size_type size() const {return length;}
bool empty() const {return length == 0;}
reference at(size_type index) {validateIndex(index);return buffer[index];}
const_reference at(size_type index) const {validateIndex(index);return buffer[index];}
reference operator[](size_type index) {return buffer[index];}
const_reference operator[](size_type index) const {return buffer[index];}
reference front() {return buffer[0];}
const_reference front() const {return buffer[0];}
reference back() {return buffer[length - 1];}
const_reference back() const {return buffer[length - 1];}
iterator begin() {return buffer;}
riterator rbegin() {return riterator(end());}
const_iterator begin() const {return buffer;}
const_riterator rbegin() const {return const_riterator(end());}
iterator end() {return buffer + length;}
riterator rend() {return riterator(begin());}
const_iterator end() const {return buffer + length;}
const_riterator rend() const {return const_riterator(begin());}
const_iterator cbegin() const {return begin();}
const_riterator crbegin() const {return rbegin();}
const_iterator cend() const {return end();}
const_riterator crend() const {return rend();}
bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
bool operator==(Vector const& rhs) const
{
return (size() == rhs.size())
&& std::equal(begin(), end(), rhs.begin());
}
void push_back(value_type const& value)
{
resizeIfRequire();
pushBackInternal(value);
}
void push_back(value_type&& value)
{
resizeIfRequire();
moveBackInternal(std::move(value));
}
template<typename... Args>
void emplace_back(Args&&... args)
{
resizeIfRequire();
emplaceBackInternal(std::move(args)...);
}
void pop_back()
{
--length;
buffer[length].~T();
}
void reserve(size_type capacityUpperBound)
{
if (capacityUpperBound > capacity)
{
reserveCapacity(capacityUpperBound);
}
}
private:
void validateIndex(size_type index) const
{
if (index >= length)
{
throw std::out_of_range("Out of Range");
}
}
void resizeIfRequire()
{
if (length == capacity)
{
size_type newCapacity = std::max(2.0, capacity * 1.5);
reserveCapacity(newCapacity);
}
}
void reserveCapacity(size_type newCapacity)
{
Vector<T> tmpBuffer(newCapacity);
simpleCopy<T>(tmpBuffer);
tmpBuffer.swap(*this);
}
void pushBackInternal(T const& value)
{
new (buffer + length) T(value);
++length;
}
void moveBackInternal(T&& value)
{
new (buffer + length) T(std::move(value));
++length;
}
template<typename... Args>
void emplaceBackInternal(Args&&... args)
{
new (buffer + length) T(std::move(args)...);
++length;
}
template<typename X>
typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
simpleCopy(Vector<T>& dst)
{
std::for_each(buffer, buffer + length,
[&dst](T const& v){dst.pushBackInternal(v);}
);
}
template<typename X>
typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
simpleCopy(Vector<T>& dst)
{
std::for_each(buffer, buffer + length,
[&dst](T& v){dst.moveBackInternal(std::move(v));}
);
}
template<typename X>
typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
clearElements()
{
for(int loop = 0; loop < length; ++loop)
{
buffer[length - 1 - loop].~T();
}
}
template<typename X>
typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
clearElements()
{
}
template<typename X>
typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
&& std::is_nothrow_destructible<X>::value) == true>::type
copyAssign(Vector<X>& copy)
{
if (this == ©)
{
return;
}
if (capacity <= copy.length)
{
clearElements<T>();
length = 0;
for(int loop = 0; loop < copy.length; ++loop)
{
pushBackInternal(copy[loop]);
}
}
else
{
Vector<T> tmp(copy);
tmp.swap(*this);
}
}
template<typename X>
typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
&& std::is_nothrow_destructible<X>::value) == false>::type
copyAssign(Vector<X>& copy)
{
Vector<T> tmp(copy);
tmp.swap(*this);
}
};