DJ Dharme
10/29/2008 4:58:00 PM
Hi,
I really like to use stl as much as possible in my code. But I
found it really hard to understand by looking into there source code.
I have no idea about what iterator traits, heaps and allocators are.
So I started to write my own container class to learn templates. I
thought about a sorted vector class which have a additional two
methods sort and insert sorted. The usage of this class is like this.
1. We can reserve some space and push all the items to the vector and
then do a sort.
2. We can insert a new item to a sorted vector by using a binary
search.
Here is my initial code. Can somebody help me to modify it so that I
can understand the concepts behind stl. How can I use allocators,
iterator traits in this class?
#include <algorithm>
#include <string.h>
template<typename T, typename Cmp>
class sorted_vector
{
public:
typedef T value_type;
typedef Cmp compare_type;
typedef value_type& reference_type;
typedef value_type* pointer_type;
typedef pointer_type iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
sorted_vector(const compare_type& pred = Cmp())
:_cmp(pred), _array(0), _capacity(0), _size(0)
{
}
~sorted_vector()
{
clear();
}
iterator begin()
{
return _array;
}
iterator end()
{
return (_array + _size);
}
void reserve(size_type size)
{
_allocate(size);
_capacity = size;
}
void push_back(const T& val)
{
insert(end(), val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void insert(iterator pos, const T& val)
{
difference_type index = (pos - begin());
pointer_type new_array = _allocate_on_insert();
if(index == 0)
{
if(new_array)
{
_copy(new_array + 1, _array, _array + _size);
_deallocate(_array);
_array = new_array;
}
else
{
_move(_array + 1, _array, _size);
}
}
else if(index == _size)
{
if(new_array)
{
_copy(new_array, _array, _array + index);
_deallocate(_array);
_array = new_array;
}
}
else
{
if(new_array)
{
_copy(new_array, _array, _array + index);
_copy(new_array + index + 1, _array + index, _array + _size);
_deallocate(_array);
_array = new_array;
}
else
{
_move(_array + index + 1, _array + index, _size - index);
}
}
_array[index] = val;
++_size;
}
void pop_back()
{
erase(end() - 1);
}
void pop_front()
{
erase(begin());
}
void erase(iterator pos)
{
difference_type index = (pos - begin());
if(index < _size)
{
_move(_array + index, _array + index + 1, _size - index - 1);
--_size;
}
}
void insert_sorted(const T& val)
{
insert(std::lower_bound(begin(), end(), val, _cmp), val);
}
void sort()
{
std::sort(begin(), end(), _cmp);
}
reference_type operator[](size_type index)
{
return _array[index];
}
size_type size() const
{
return _size;
}
size_type capacity() const
{
return _capacity;
}
void clear()
{
_deallocate(_array);
_array = 0;
_size = 0;
_capacity = 0;
}
protected:
pointer_type _allocate(size_type size)
{
return new value_type[size];
}
void _deallocate(pointer_type p)
{
delete[] p;
}
pointer_type _allocate_on_insert()
{
size_type new_size = _size + 1;
if(new_size >= _capacity)
{
_capacity = new_size * 2;
return _allocate(_capacity);
}
return 0;
}
void _move(pointer_type to, pointer_type from, size_type count)
{
memmove(to, from, count * sizeof(value_type));
}
void _copy(pointer_type dest_begin, pointer_type src_begin,
pointer_type src_end)
{
memcpy(dest_begin, src_begin, (src_end - src_begin) *
sizeof(value_type));
}
compare_type _cmp;
pointer_type _array;
size_type _capacity;
size_type _size;
};