Handmade Vector Class

amed01.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <vector>

#ifdef _MSC_VER
  #define WIN32_LEAN_AND_MEAN
  #include <windows.h>
  #include <psapi.h>
  #pragma comment(linker, "/defaultlib:psapi.lib")
  #pragma message("Automatically linking with psapi.lib")
#else
  #include <sys/time.h>
#endif

typedef long long llong;
typedef unsigned long long ullong;

llong microtimer()
{
#ifdef _MSC_VER
	// Windows time query
	static llong iBase = 0;
	static llong iStart = 0;
	static llong iFreq = 0;

	LARGE_INTEGER iLarge;
	if (!iBase)
	{
		// get start QPC value
		QueryPerformanceFrequency(&iLarge); iFreq = iLarge.QuadPart;
		QueryPerformanceCounter(&iLarge); iStart = iLarge.QuadPart;

		// get start UTC timestamp
		// assuming it's still approximately the same moment as iStart, give or take a msec or three
		FILETIME ft;
		GetSystemTimeAsFileTime(&ft);

		iBase = (llong(ft.dwHighDateTime)<<32) + llong(ft.dwLowDateTime);
		iBase = (iBase - 116444736000000000ULL) / 10; // rebase from 01 Jan 1601 to 01 Jan 1970, and rescale to 1 usec from 100 ns
	}

	// we can't easily drag iBase into parens because iBase*iFreq/1000000 overflows 64bit int!
	QueryPerformanceCounter(&iLarge);
	return iBase + (iLarge.QuadPart - iStart) * 1000000 / iFreq;

#else
	// UNIX time query
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return llong(tv.tv_sec) * llong(1000000) + llong(tv.tv_usec);
#endif
}

void onexit()
{
#ifdef _MSC_VER
	PROCESS_MEMORY_COUNTERS pmc;
	HANDLE hProcess = OpenProcess(PROCESS_QUERY_INFORMATION | PROCESS_VM_READ, FALSE, GetCurrentProcessId());
	if (hProcess && GetProcessMemoryInfo(hProcess, &pmc, sizeof(pmc)))
		printf ( "--- peak-wss=%d, peak-pagefile=%d\n", (int)pmc.PeakWorkingSetSize, (int)pmc.PeakPagefileUsage);
#endif
}

typedef int size_type;

template<typename T> class myvector {
public:
  static void deleteRange(T* begin, T* end) {
    while (begin != end) {
      begin->~T();
      begin++;
    }
  }

private:
  size_type _size;
  size_type _capacity;
  T* _data;

public:
  myvector();
  ~myvector();

  size_type capacity();
  size_type size();

  void add(const T&);
  T& add();
  void erase(size_type);

  void push_back(const T&);
  void erase(const T*);

  T& operator[](size_type);
  const T& operator[](size_type) const;

  T* begin();
  T* end();
  T& back();

  void clear();
  void resize(size_type);
  void reserve(size_type);
};

template<typename T>
myvector<T>::myvector() {
  _capacity = 8;
  _size = 0;
  _data = static_cast<T*>(malloc(sizeof(T) * _capacity));
}

template<typename T>
myvector<T>::~myvector() {
  deleteRange(_data, _data + _size);
  free(_data);
}

template<typename T>
size_type myvector<T>::capacity() {
  return _capacity;
}

template<typename T>
size_type myvector<T>::size() {
  return _size;
}

template<typename T>
void myvector<T>::add(const T& value) {
  push_back(value);
}

template<typename T>
T& myvector<T>::add() {
  T* item = new T();
  push_back(*item);
  delete item;
  return back();
}

template<typename T>
void myvector<T>::erase(size_type index) {
  assert(index >= 0 && index < _size);
  if (_size == 1) {
    clear();
  } else {
    for (size_type i = index; i < _size - 1; i++) {
      memcpy(_data + i, _data + i + 1, sizeof(T));
    }

    _size--;
  }
}

template<typename T>
void myvector<T>::push_back(const T& value) {
  T* item = new T(value);

  if (_size == _capacity) {
    // Resize policy
    size_type newCapacity = _capacity < 512 ? _capacity * 2 : _capacity * 1.2;

    _data = static_cast<T*>(realloc(_data, sizeof(T) * newCapacity));
    _capacity = newCapacity;
  }

  memcpy(_data + _size, item, sizeof(T));
  delete item;
  _size++;
}

template<typename T>
void myvector<T>::erase(const T* item) {
  size_type index = item - _data;
  assert(index >= 0 && index < _size);
  erase(index);
}

template<typename T>
T& myvector<T>::operator[](size_type index) {
  assert(index >= 0 && index < _size);
  return _data[index];
}

template<typename T>
const T& myvector<T>::operator[](size_type index) const {
  assert(index >= 0 && index < _size);
  return _data[index];
}

template<typename T>
T* myvector<T>::begin() {
  return _data;
}

template<typename T>
T* myvector<T>::end() {
  return _data + _size;
}

template<typename T>
T& myvector<T>::back() {
  return *(_data + _size - 1);
}

template<typename T>
void myvector<T>::clear() {
  deleteRange(_data, _data + _size);
  _size = 0;
  _capacity = 8;
  _data = static_cast<T*>(realloc(_data, sizeof(T) * _capacity));
}

template<typename T>
void myvector<T>::resize(size_type new_size) {
  if (new_size != 0) {
    if ((new_size > _capacity) || (new_size < _capacity/2)) {
      _capacity = new_size;
      _data = static_cast<T*>(realloc(_data, sizeof(T) * new_size));
    }
  } else {
    clear();
  }

  _size = new_size;
}

template<typename T>
void myvector<T>::reserve(size_type min_capacity) {
  if (min_capacity > _capacity) {
    _capacity = min_capacity < 512 ? min_capacity * 2 : min_capacity * 1.2;
    _data = static_cast<T*>(realloc(_data, sizeof(T) * _capacity));
  }
}

struct Record {
  const char* str;
  unsigned int size;
};

class ClassRecord {
public:
  int ifield;
  char cfield;
  double dfield;

  ClassRecord(int intf = 0, char cf = ' ', double df = 0.) {
    ifield = intf;
    cfield = cf;
    dfield = df;
  }

  ~ClassRecord() {
  }
};

int main(int argc, char** argv) {
#ifdef _STD_VEC
  printf("USE std::vector\n");
  std::vector<Record> str;
  std::vector<ClassRecord> cr;
#else
  printf("USE myvector\n");
  myvector<Record> str;
  myvector<ClassRecord> cr;
#endif

  llong start = microtimer();
  #ifdef _VERBOSE
    Record rec1 = {"abc\0", 3 };
    Record rec2 = {"abd\0", 3 };
    Record rec3 = {"abdc\0", 4 };
    str.push_back(rec1);
    str.push_back(rec2);
    str.push_back(rec3);
  #else
    for (int i = 0; i < 1000000; i++) {
      Record rec = {"abc\0", i };
      str.push_back(rec);
    }
  #endif
  printf("push_back(struct): %d\n", microtimer() - start);

  start = microtimer();
  #ifdef _VERBOSE
    cr.push_back(ClassRecord(1, 'c', 2.235));
    cr.push_back(ClassRecord(2, 'd', 0.235));
    cr.push_back(ClassRecord(3, 'e', 1.335));
    cr.push_back(ClassRecord(4, 'a', 2.255));
    cr.push_back(ClassRecord(5, 'v', 3.245));
  #else
    for (int i = 0; i < 1000000; i++) {
      cr.push_back(ClassRecord(i));
    }
  #endif
  printf("push_back(class): %d\n", microtimer() - start);

  #ifndef _STD_VEC
    cr.erase(&cr[2]);
    ClassRecord& emplace = cr.add();
    emplace.ifield = 10;
    emplace.cfield = 'i';
    emplace.dfield = 9.889;
  #else
    cr.erase(cr.begin() + 2, cr.begin() + 3);
    cr.emplace_back(10, 'i', 9.889);
  #endif

  #ifdef _VERBOSE
    for (unsigned int i = 0; i < str.size(); i++) {
      printf("%s c: %d\n", str[i].str, str[i].size);
    }
    for (unsigned int i = 0; i < cr.size(); i++) {
      printf("%d, %c, %f\n", cr[i].ifield, cr[i].cfield, cr[i].dfield);
    }
  #endif

  onexit();
  return 0;
}