#ifndef _STL_VECTOR_HPP_
#define _STL_VECTOR_HPP_
#include <stl/algorithm.hpp>
#include <stl/allocator.hpp>
#include <stl/iterator.hpp>
#include <stl/memory.hpp>
namespace stl
{
/*
* class base_vector
* Base class for the vector container. All memory allocation and
* deallocation is performed in this class.
* */
template <
class ValueTy,
class AllocatorTy>
class base_vector : public traits<ValueTy, ValueTy*>
{
private:
typedef base_vector<ValueTy,AllocatorTy> this_type;
const size_type __mMaxSize;
public:
typedef AllocatorTy allocator_type;
protected:
allocator_type _mAllocator;
pointer_type _mBegin;
pointer_type _mEnd;
pointer_type _mCapacity;
void _do_assign(const size_type, const_reference_type);
pointer_type _do_create_copy();
void _do_destroy_values(pointer_type, pointer_type);
void _do_reallocate(const size_type);
void _do_remove(const size_type, const size_type);
void _do_resize(const size_type);
public:
base_vector();
~base_vector();
bool empty() const;
size_type capacity() const;
size_type size() const;
size_type max_size() const;
allocator_type get_allocator() const;
};
/*
* Constructor
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
base_vector<ValueTy, AllocatorTy>::base_vector()
: __mMaxSize(stl::npos / this_type::base_size),
_mBegin(NULL),
_mEnd(NULL),
_mCapacity(NULL)
{}
/*
* Destructor
* */
template <class ValueTy, class AllocatorTy>
base_vector<ValueTy, AllocatorTy>::~base_vector()
{
const size_type currentSize = this->size();
for (size_type i = 0; i < currentSize; ++i) {
_mAllocator.destroy(_mBegin+i);
}
_mAllocator.deallocate(_mBegin);
}
/*
* _do_assign() returns nothing
* Input:
* size_type The index of the element to assign to.
* const_reference_type The value to assign.
* */
template <class ValueTy, class AllocatorTy>
void
base_vector<ValueTy, AllocatorTy>::_do_assign(const size_type index, const_reference_type val)
{
if (index >= this->size()) {
this->_do_resize(index+1);
}
_mBegin[index] = val;
}
/*
* _do_create_copy() returns pointer_type
* Input:
* nothing
*
* Creates a full copy of the data allocated by the vector.
* Returns a pointer to said copy. Will return NULL if vector is empty.
* */
template <class ValueTy, class AllocatorTy>
typename base_vector<ValueTy, AllocatorTy>::pointer_type
base_vector<ValueTy, AllocatorTy>::_do_create_copy()
{
const size_type len = this->size();
pointer_type result = NULL;
if (len > 0)
{
result = _mAllocator.allocate(len);
memcpy(result, _mBegin, len * this_type::base_size);
}
return result;
}
template <class ValueTy, class AllocatorTy>
typename base_vector<ValueTy, AllocatorTy>::pointer_type
base_vector<ValueTy, AllocatorTy>::_do_destroy_values(pointer_type first, pointer_type last)
{
for (; first != last; ++first) {
first->~value_type();
}
}
template <class ValueTy, class AllocatorTy>
void
base_vector<ValueTy, AllocatorTy>::_do_reallocate(const size_type newDesiredCapacity)
{
if (newDesiredCapacity > this->capacity())
{
size_type newCapacity = 1;
while (newCapacity < newDesiredCapacity) {
newCapacity *= 2;
}
const size_type previousSize = this->size();
pointer_type backup = _do_create_copy();
_mAllocator.deallocate(_mBegin);
_mBegin = _mAllocator.allocate(newCapacity);
_mEnd = _mBegin + previousSize;
_mCapacity = _mBegin + newCapacity;
if (backup != NULL)
{
memcpy(_mBegin, backup, previousSize * this_type::base_size);
_mAllocator.deallocate(backup);
}
}
}
template <class ValueTy, class AllocatorTy>
void
base_vector<ValueTy, AllocatorTy>::_do_remove(const size_type start, const size_type len)
{
if (start != stl::npos)
{
pointer_type ptr = (_mBegin + start);
pointer_type ptrEnd = (ptr + len);
if (ptrEnd <= _mEnd)
{
while (ptr != ptrEnd) {
_mAllocator.destroy(ptr++);
}
_mEnd -= len;
if (ptrEnd != _mEnd) {
memmove((_mBegin+start), ptrEnd, len * this_type::base_size);
}
}
}
}
template <class ValueTy, class AllocatorTy>
inline void
base_vector<ValueTy, AllocatorTy>::_do_resize(const size_type newSize)
{
this->_do_reallocate(newSize);
_mEnd = (_mBegin + newSize);
}
/*
* empty() returns bool
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline bool
base_vector<ValueTy, AllocatorTy>::empty() const
{
return (_mBegin == _mEnd);
}
/*
* capacity() returns size_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename base_vector<ValueTy, AllocatorTy>::size_type
base_vector<ValueTy, AllocatorTy>::capacity() const
{
return (_mCapacity - _mBegin);
}
/*
* size() returns size_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename base_vector<ValueTy, AllocatorTy>::size_type
base_vector<ValueTy, AllocatorTy>::size() const
{
return (_mEnd - _mBegin);
}
/*
* max_size() returns size_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename base_vector<ValueTy, AllocatorTy>::size_type
base_vector<ValueTy, AllocatorTy>::max_size() const
{
return __mMaxSize;
}
/*
* class vector
*
* */
template <
class ValueTy,
class AllocatorTy=allocator<ValueTy>>
class vector : public base_vector<ValueTy, AllocatorTy>
{
private:
typedef vector<ValueTy,AllocatorTy> this_type;
typedef base_vector<ValueTy,AllocatorTy> base_type;
public:
typedef pointer_type iterator;
typedef const_pointer_type const_iterator;
typedef stl::reverse_iterator<iterator> reverse_iterator;
typedef stl::reverse_iterator<const_iterator> const_reverse_iterator;
vector();
vector(const size_type);
vector(const size_type, const_reference_type);
reference_type operator [] (const size_type);
const_reference_type operator [] (const size_type) const;
reference_type at(const size_type);
const_reference_type at(const size_type) const;
reference_type front();
reference_type back();
const_reference_type front() const;
const_reference_type back() const;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
void push_back(const_reference_type);
void pop_back();
void reserve(const size_type);
void resize(const size_type);
void resize(const size_type, const_reference_type);
void assign(iterator, iterator);
void assign(size_type, const_reference_type);
iterator erase(iterator);
iterator erase(iterator, iterator);
iterator insert(iterator, const_reference_type);
void insert(iterator, size_type, const_reference_type);
template <class InputIteratorTy>
void insert(iterator, InputIteratorTy, InputIteratorTy);
void clear();
void swap(this_type&);
};
/*
* operator [] returns reference_type
* Input:
* size_type The index position of the element to return.
* */
template <class Ty, class AllocatorTy>
inline typename vector<Ty, AllocatorTy>::reference_type
vector<Ty, AllocatorTy>::operator [] (const size_type index)
{
return _mBegin[index];
}
/*
* operator [] returns const_reference_type
* Input:
* size_type The index position of the element to return.
* */
template <class Ty, class AllocatorTy>
inline typename vector<Ty, AllocatorTy>::const_reference_type
vector<Ty, AllocatorTy>::operator [] (const size_type index) const
{
return _mBegin[index];
}
/*
* Constructor
* */
template <class ValueTy, class AllocatorTy>
vector<ValueTy, AllocatorTy>::vector()
{
/* Intentionally left blank. */
}
/*
* Constructor
* */
template <class ValueTy, class AllocatorTy>
vector<ValueTy, AllocatorTy>::vector(const size_type num)
{
this->resize(num, value_type());
}
/*
* Constructor
* */
template <class ValueTy, class AllocatorTy>
vector<ValueTy, AllocatorTy>::vector(const size_type num, const_reference_type val)
{
this->resize(num, val);
}
/*
* at() returns reference_type
* Input:
* size_type The index of the element to return.
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::reference_type
vector<ValueTy, AllocatorTy>::at(const size_type index)
{
return _mBegin[index];
}
/*
* at() const returns const_reference_type
* Input:
* size_type The index of the element to return.
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_reference_type
vector<ValueTy, AllocatorTy>::at(const size_type index) const
{
return _mBegin[index];
}
/*
* front() returns reference_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::reference_type
vector<ValueTy, AllocatorTy>::front()
{
return *_mBegin;
}
/*
* back() returns reference_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::reference_type
vector<ValueTy, AllocatorTy>::back()
{
return *_mEnd;
}
/*
* front() const returns const_reference_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_reference_type
vector<ValueTy, AllocatorTy>::front() const
{
return *_mBegin;
}
/*
* back() const returns const_reference_type
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_reference_type
vector<ValueTy, AllocatorTy>::back() const
{
return *_mEnd;
}
/*
* begin() returns iterator
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::iterator
vector<ValueTy, AllocatorTy>::begin()
{
return iterator(_mBegin);
}
/*
* end() returns iterator
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::iterator
vector<ValueTy, AllocatorTy>::end()
{
return iterator(_mEnd);
}
/*
* begin() const returns iterator
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_iterator
vector<ValueTy, AllocatorTy>::begin() const
{
return const_iterator(_mBegin);
}
/*
* end() const returns iterator
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_iterator
vector<ValueTy, AllocatorTy>::end() const
{
return const_iterator(_mEnd);
}
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
vector<ValueTy, AllocatorTy>::rbegin()
{
return reverse_iterator(_mEnd);
}
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
vector<ValueTy, AllocatorTy>::rend()
{
return reverse_iterator(_mBegin);
}
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
vector<ValueTy, AllocatorTy>::rbegin() const
{
return const_reverse_iterator(_mEnd);
}
template <class ValueTy, class AllocatorTy>
inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
vector<ValueTy, AllocatorTy>::rend() const
{
return const_reverse_iterator(_mBegin);
}
/*
* push_back() returns nothing
* Input:
* const_reference_type The value to push.
*
* Pushes the passed value onto the end of the vector.
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::push_back(const_reference_type val)
{
this->_do_assign(this->size(), val);
}
/*
* pop_back() returns nothing
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::pop_back()
{
this->_do_remove(this->size()-1, 1);
}
/*
* reserve() returns nothing
* Input:
* size_type The new capacity.
*
* This function is a public alias for basic_vector::_do_reallocate.
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::reserve(const size_type newCapacity)
{
this->_do_reallocate(newCapacity);
}
/*
* resize() returns nothing
* Input:
* size_type The new size.
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::resize(const size_type newSize)
{
if (newSize > this->size()) {
this->_do_resize(newSize);
} else {
this->erase(_mBegin + newSize, _mEnd);
}
}
/*
* resize() returns nothing
* Input:
* size_type The new size.
* const_reference_type The value to assign the each element.
* */
template <class ValueTy, class AllocatorTy>
void
vector<ValueTy, AllocatorTy>::resize(const size_type newSize, const_reference_type val)
{
this->_do_resize(newSize);
for (iterator itr = begin(); itr != end(); ++itr) {
*itr = val;
}
}
/*
* assign() returns nothing
* Input:
* size_type The number of elements to assign.
* const_reference_type The value to assign the each element.
* */
template <class ValueTy, class AllocatorTy>
void
vector<ValueTy, AllocatorTy>::assign(size_type n, const_reference_type source)
{
if (n > this->size()) {
this->resize(n, source);
} else {
while (n-- > 0) {
_mBegin[n] = source;
}
}
}
/*
* erase() returns iterator
* Input:
* iterator The position of the element to be removed.
*
* Removes the element at the position defined by the passed iterator.
* The returned iterator will be equal to the element one past the
* element defined by the passed iterator.
* For example:
* vector<int> vec(3);
* vec[0]=1; vec[1]=2; vec[2]=3;
*
* int n = *(vec.erase(vec.begin()+1)); // 3
* */
template <class ValueTy, class AllocatorTy>
typename vector<ValueTy, AllocatorTy>::iterator
vector<ValueTy, AllocatorTy>::erase(iterator itr)
{
iterator result = this->end();
if (this->empty() == false)
{
if (this->size() > 1)
{
result = &*itr;
memmove(&*itr, &*itr+1, (this->size()-(&*itr-_mBegin)) * sizeof value_type);
}
--_mEnd;
}
return result;
}
template <class ValueTy, class AllocatorTy>
typename vector<ValueTy, AllocatorTy>::iterator
vector<ValueTy, AllocatorTy>::erase(iterator first, iterator last)
{
iterator result = this->end();
if (this->empty() == false)
{
const difference_type len = (&*last - &*first);
if (len == 0)
{
result = this->erase(first);
--_mEnd;
}
else
{
result = &*last;
_mEnd -= len;
memmove(&*first, &*last+1, (this->size()-len) * sizeof value_type);
}
}
return result;
}
/*
* clear() returns nothing
* Input:
* nothing
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::clear()
{
_do_destroy_values(_mBegin, _mEnd);
_mEnd = _mBegin;
}
/*
* swap() returns nothing
* Input:
* this_type& A reference to the vector to swap with.
* */
template <class ValueTy, class AllocatorTy>
inline void
vector<ValueTy, AllocatorTy>::swap(this_type& source)
{
memswap(this, &source, sizeof this_type);
}
}
#endif