C++ Data Structures with Templates

The Code

#ifndef Vector_h
#define vector_h
template<typename T>
class Vector {
public:
	typedef T* iterator;
	Vector();
	Vector(size_t);
	~Vector();
	void push_back(const T);
	void assign(T*, size_t);
	void insert(size_t, T);
	void insert(iterator, T);
	T& front();
	T& back();
	void pop_back();
	void clear();
	bool empty();
	size_t capacity();
	void shrink_to_fit(bool);
	void reserve(size_t);
	size_t size();
	uint8_t lastError;
	iterator begin();
	iterator end();
	iterator rbegin();
	iterator rend();
	T &operator[](size_t n) {
		if (n < top) {
			return vStart[n];
		}
		else {
			lastError |= 2; // bounds error
			return noT;
		}
	};
	T noT;
private:
	T* vStart;
	int top;
	size_t tSize, mSize;
	void init();
	void resize(int);
	static const int defSize = 8; // tweak as required
};
// Vector Methods
// constructors and Destructor
template<typename T>
Vector<T>::Vector() {
	mSize = defSize;
	init();
}
template<typename T>
Vector<T>::Vector(size_t initSize) {
	mSize = (initSize > defSize) ? initSize : defSize;
	init();
}
template<typename T>
Vector<T>::~Vector() {
	free(vStart);
}
// public methods
template<typename T>
size_t Vector<T>::size() {
	return top;
}
template<typename T>
size_t Vector<T>::capacity() {
	return mSize;
}
template<typename T>
bool Vector<T>::empty() {
	return top == 0;
}
template<typename T>
void Vector<T>::push_back(const T t) {
	if (top == mSize) {
		int inc = mSize + (log(mSize) / log(2));
		resize(inc);
		if (mSize < inc) {
			return;
		}
	}
	memcpy((vStart + top++), &t, tSize); // increments top after memcpy()
}
template<typename T>
void Vector<T>::assign(T* tArray, size_t elemCount) {
	int newTop = top + elemCount;
	if (++newTop > mSize) {
		resize(newTop);
	}
	if (mSize >= newTop) {
		for (int i = 0; i < elemCount; i++) {
			memcpy((vStart + top++), (tArray + i), tSize);
		}
	}
}
template<typename T>
void Vector<T>::pop_back() {
	if (top > 0) {
		top--;
		if (top < (defSize) && mSize > defSize) {
			resize(defSize);
		}
	}
}
template<typename T>
T& Vector<T>::front() {
	return vStart[0];
}
template<typename T>
T& Vector<T>::back() {
	return vStart[top-1];
}
template<typename T>
void Vector<T>::clear() {
	top = 0;
	if (mSize > defSize) {
		resize(defSize);
	}
}
template<typename T>
void Vector<T>::shrink_to_fit(bool radical = false) {
	if (radical) {
		resize(top);
	}
	else {
		resize(((top + 1) > defSize) ? top + 1 : defSize);
	}
}
template<typename T>
void Vector<T>::reserve(size_t s) {
	if (s > mSize) {
		resize(s);
	}
}
// private methods follow
template<typename T>
void Vector<T>::resize(int newSize) {
	lastError ^= 4;
	void* newStart = realloc(vStart, tSize * newSize);
	if (newStart) {
		vStart = (T*)newStart;
		mSize = newSize;
	}
	else {
		lastError |= 4;
	}
}
template<typename T>
void Vector<T>::init() {
	lastError = top = 0;
	tSize = sizeof(T);
	vStart = (T*)malloc(tSize * mSize);
	if (!vStart) {
		lastError |= 1;
		mSize = 0;
	}
	memset(&noT, 0, tSize);
}
template<typename T>
typename Vector<T>::iterator Vector<T>::begin() {
	return vStart;
}
template<typename T>
typename Vector<T>::iterator Vector<T>::end() {
	return vStart + top;
}
template<typename T>
typename Vector<T>::iterator Vector<T>::rbegin() {
	return vStart + top - 1;
}
template<typename T>
typename Vector<T>::iterator Vector<T>::rend() {
	return vStart -1;
}
template<typename T>
void Vector<T>::insert(size_t pos, T t) {
	T* ins = vStart + pos; // convert the position index to a pointer
	insert(ins, t);
}
template<typename T>
void Vector<T>::insert(iterator pos, T t) {
	if (top == mSize) {
		int inc = mSize + (log(mSize) / log(2));
		resize(inc);
		if (mSize < inc) {
			return;
		}
	}
	size_t bytes = (size_t)(vStart + top) - (size_t)(pos);
	memmove(pos + 1, pos, bytes); // works for overlapping memory
	memcpy(pos, &t, tSize); // pop the new value into the insert position
	top++; // for added item
}
#endif

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "Vector.h"
#include <iostream>
int main()
{
	Vector<int> vector;
	for (int i = 0; i < 10; i++) {
		int r = rand() % 29;
		vector.push_back(r);
	}
	for (Vector<int>::iterator it = vector.begin(); it != vector.end(); it++) {
		std::cout << *it << '\n';
	}
	std::cout << "Size: " << vector.size() << '\n';
	std::cout << "Front: " << vector.front() << '\n';
	std::cout << "Back: " << vector.back() << '\n';
	int r = vector.front();
	vector.front() = vector.back();
	vector.back() = r;
	for (Vector<int>::iterator it = vector.rbegin(); it != vector.rend(); it--) {
		std::cout << *it << '\n';
	}
	vector[2] = 39;
	vector[6] = vector[7];
	int newInts[] = { 1, 2, 3, 6, 7 ,9 };
	vector.assign(newInts, 6);
	std::cout << '\n';
	for (Vector<int>::iterator it = vector.begin(); it != vector.end(); it++) {
		std::cout << *it << '\n';
	}
	vector.insert(2, 99); // zero based so insert to 3rd element
	std::cout << '\n';
	for (Vector<int>::iterator it = vector.begin(); it != vector.end(); it++) {
		std::cout << *it << '\n';
	}
	std::cin.get();
    return 0;
}

#include "vector.h"
Vector<int> vector;
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  for(int i = 0; i < 12; i++) {
    int r = random(1, 100);
    Serial << "Added: " << r << '\n';
    vector.push_back(r);
  }
  Serial << "Now added: " << vector.size() << " integers\n";
  int newInts[] = { 1, 2, 3, 6, 7 ,9};
  vector.assign(newInts, 6);
  Serial << "capacity now: " << vector.capacity() << " integers\n";
  vector[2] = 3;
  // the for loop addresses elements that are out of bounds
  for(int i = -2, j = vector.size(); i < j; i++) {
    Serial << vector[i] << '\n';
  }
  if(vector.lastError & 2) {
    Serial << "Bounds error detected\n";
    vector.lastError ^= 2; // turn off the bounds error flag
  }
  vector.reserve(2000); // should break memory
  Serial << "capacity: " << vector.capacity() << " integers\n";
  Serial << vector[6] << '\n'; // but vector still intact
}

Read the chapter in my book C++ Data Structures with immediate download from Amazon