Advice or criticism of code below

[awhite1159]

I have been a C programmer for fun for a number of years and also programmed with C++ in the early '90s. I purchased the book "Accelerated C++" in an effort to come up to date and convert my 'C' like ways of writing code since when I used C++ in the past, alot of my code was still 'C' like.

Chapter 11 has an exercise which needs the erase function implemented for the class Vec. This class is similiar to the vector container in the stl but lacked the erase function. After some thought and seeing that there are two erase functions available in the stl, I wrote the code as below for the erase function with some overloading to deal with the different possibilities of how it would be called. Does anyone have any comments/suggestions on this code below?

I was thinking of speeding it up by having k sense that it is between i and j resulting in it be set to j+1 so it skips over items that are being erased.

Thanks.

#ifndef VEC_H
#define VEC_H

#include<iostream>
#include <algorithm>
#include <cstddef>
#include <memory>
#include<stdexcept>

using std::max;

template <class T> class Vec {
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;
	typedef T& reference;
	typedef const T& const_reference;

	Vec() { create(); }
	explicit Vec(size_type n, const T& t = T()) { create(n, t); }

	Vec(const Vec& v) { create(v.begin(), v.end()); }
	Vec& operator=(const Vec&);	// as defined in 11.3.2/196
	~Vec() { uncreate(); }

	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }

	void push_back(const T& t) {
		if (avail == limit)
			grow();
		unchecked_append(t);
	}

	size_type size() const { return avail - data; }  // changed

	iterator begin() { return data; }
	const_iterator begin() const { return data; }

	iterator end() { return avail; }                 // changed
	const_iterator end() const { return avail; }     // changed
	void clear() { uncreate(); }
	iterator erase(iterator i) { return erase(i, i); }
	iterator erase(iterator, iterator);
	bool empty() const { return data == avail; }

private:
	iterator data;	// first element in the `Vec'
	iterator avail;	// (one past) the last element in the `Vec'
	iterator limit;	// (one past) the allocated memory

	// facilities for memory allocation
	std::allocator<T> alloc;	// object to handle memory allocation

	// allocate and initialize the underlying array
	void create();
	void create(size_type, const T&);
	void create(const_iterator, const_iterator);

	// destroy the elements in the array and free the memory
	void uncreate();

	// support functions for `push_back'
	void grow();
	void unchecked_append(const T&);
};

template <class T> void Vec<T>::create()
{
	data = avail = limit = 0;
}

template <class T> void Vec<T>::create(size_type n, const T& val)
{
	data = alloc.allocate(n, 0);
	data = alloc.allocate(n);
	limit = avail = data + n;
	std::uninitialized_fill(data, limit, val);
}

template <class T>
void Vec<T>::create(const_iterator i, const_iterator j)
{
	data = alloc.allocate(j - i, 0);
	data = alloc.allocate(j - i);
	limit = avail = std::uninitialized_copy(i, j, data);
}

template <class T> void Vec<T>::uncreate()
{
	if (data) {
		// destroy (in reverse order) the elements that were constructed
		iterator it = avail;
		while (it != data)
			alloc.destroy(--it);

		// return all the space that was allocated
		alloc.deallocate(data, limit - data);
	}
	// reset pointers to indicate that the `Vec' is empty again
	data = limit = avail = 0;

}

template <class T> void Vec<T>::grow()
{
	// when growing, allocate twice as much space as currently in use
	size_type new_size = max(2 * (limit - data), ptrdiff_t(1));

	// allocate new space and copy existing elements to the new space
	iterator new_data = alloc.allocate(new_size);
	iterator new_avail = std::uninitialized_copy(data, avail, new_data);

	// return the old space
	uncreate();

	// reset pointers to point to the newly allocated space
	data = new_data;
	avail = new_avail;
	limit = data + new_size;
}

// assumes `avail' points at allocated, but uninitialized space
template <class T> void Vec<T>::unchecked_append(const T& val)
{
	alloc.construct(avail++, val);
}

template<class T> T* Vec<T>::erase(iterator i, iterator j) {
	iterator new_data, new_avail, k;
	size_type size = limit-data;
	if(i<data || j<i || j>avail)
		throw std::out_of_range("Iterator out of range");

	// allocate new space and copy existing elements to the new space
        new_data = new_avail = alloc.allocate(size);
	for(k=data;k<=avail;k++)
		if(k<i || k>j)
			alloc.construct(new_avail++, *k);

	// Destroy old vector
	uncreate();

	// Update private iterators
	data=new_data;
	avail=new_avail-1;
	limit=data+size; 
	return new_avail;
}
	
template <class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
        // check for self-assignment
        if (&rhs != this) {

                // free the array in the left-hand side
                uncreate();

                // copy elements from the right-hand to the left-hand side
                create(rhs.begin(), rhs.end());
        }
        return *this;
}
#endif 

[Duthomhas]

It certainly looks like you know what you are doing. In fact, I'd say you've picked-up C++ better than a lot of people...

Just a couple comments. ;-)

I'd be a little wary of simply doubling the space available (limit) every time you grow. The space potentially wasted grows exponentially the larger the vector gets.

If you want to be really careful, you can add an adaptive difference based upon usage patterns, but to be simple just pick some constant number of elements and add that amount every time...


In your erase(), you calculate 'size'. Why not just use the method you already created to do just that?
new_data = new_avail = alloc.allocate( size() );
Chances are that it is inline anyway...

If you are really concerned about forcing stupid compilers to be as absolutely efficient as possible:
register size_type size = size();

The point is that you should try to calculate specific values in only one place. Then, if you change one, you don't have to scratch your head figuring out why the code breaks.


Speed improvements based on adding extra conditions are temperamental at best. The greatest speed improvement would be just to have two loops:

for (k=data; k<i;     k++) alloc.construct(new_avail++, *k);
for (k=j+1;  k<avail; k++) alloc.construct(new_avail++, *k);

This might produce a few bytes worth more code...


The other option would be not to allocate a new array at all. Just move elements j+1, j+2, j+3, ... to i, i+1, i+2, ... using a simple bit-copy and then fill the (now unused) parts with the uninitialized value.


Finally, you could conceivably reduce the array size if enough elements are erased.


Just some thoughts for the terminally bit-minded. :-P
Good job! (It is better than I would have done...)

Hope this helps.