Skip to content

Instantly share code, notes, and snippets.

@sonus21
Last active June 19, 2019 16:39
Show Gist options
  • Save sonus21/7334d98c4a5865dc19d9bbe48caa7d7b to your computer and use it in GitHub Desktop.
Save sonus21/7334d98c4a5865dc19d9bbe48caa7d7b to your computer and use it in GitHub Desktop.
Dynamic array in C++ which grows/shrink at the rate of 2.
#include <iostream>
#include <cstring>
#include <exception>
#include <stdexcept>
using namespace std;
class IndexError: public exception {
public: IndexError(char * msg) {
this -> msg = new char[strlen(msg)];
cout << msg;
strcpy(this -> msg, msg);
}
const char * what() const
throw () {
return this -> msg;
}
private: char * msg;
};
template < class T >
class Array {
public:
Array(int size = 16, int factor = 2): _size(size), _factor(factor), _num_elements(0) {
_array = new T[size];
memset(_array, 0, sizeof(_size * sizeof(T)));
}
~Array() {
delete _array;
}
size_t members() {
return _num_elements;
}
const size_t members() const {
return _num_elements;
}
const T & operator[](int index) const {
if (index < _num_elements) {
return _array[index];
}
throw IndexError("Array index out of range.");
}
T & operator[](int index) {
if (index < _num_elements) {
return _array[index];
}
throw IndexError("Array index out of range.");
}
void push(const T & element) {
// Add element at the end of the array
if (_size == 0) {
growOrShrinkArray(_default_size);
} else if (_num_elements == _size) {
growOrShrinkArray(_size * _factor);
}
_array[_num_elements++] = element;
}
T & pop() {
// Delete last element from the array
if (_num_elements == 0) {
throw IndexError("Array is empty.");
}
T & element = _array[--_num_elements];
mayBeShrink();
return element;
}
void remove(const T & element) {
// Remove the first occurance of the given element.
for (int i = 0; i < _num_elements; i++) {
if (_array[i] == element) {
int j = i;
while( j + 1 < _num_elements){
_array[j] = _array[j+1];
j++;
}
--_num_elements;
break;
}
}
mayBeShrink();
}
void empty() {
// Free the memory
delete _array;
_array = NULL;
_num_elements = 0;
_size = 0;
}
void removeAll(const T & element) {
// Remove all occurances of an element.
int i = 0;
int j = 0;
while( i < _num_elements){
if (_array[i] != element) {
_array[j++] = _array[i];
}
i++;
}
_num_elements -= (i-j);
mayBeShrink();
}
private:
T * _array;
size_t _size;
size_t _num_elements;
float _factor;
size_t _default_size = 16;
void growOrShrinkArray(int size) {
if (size < _default_size) {
return;
}
std::cout << __FUNCTION__ << "\t" << size << endl;
T * tmp_array = new T[size];
memset(tmp_array, 0, sizeof(size * sizeof(T)));
if(_array != NULL){
memcpy(tmp_array, _array, _num_elements * sizeof(T));
delete _array;
}
_array = tmp_array;
_size = size;
}
void mayBeShrink() {
if (_num_elements * _factor < _size) {
growOrShrinkArray(_size / _factor);
}
}
};
///////////// Testing of Array class //////////////
class Test {
public:
Test(int i = 0): num(i) {}
friend ostream & operator << (ostream & output,
const Test & test) {
output << test.num;
return output;
}
bool operator == (const Test & other) {
return this -> num == other.num;
}
bool operator != (const Test & other) {
return this -> num != other.num;
}
private:
int num;
};
void display(const Array < Test > & a) {
cout<<"Array: [";
for (int i = 0; i < a.members(); i++) {
cout << a[i] <<",";
}
cout<<"]\n";
}
int main() {
Array < Test > array;
for (int i = 0; i < 5; i++) {
array.push(Test(i));
}
display(array);
// Delete first element
array.remove(Test(0));
display(array);
// Delete an element which does not exist
array.removeAll(Test(0));
display(array);
// Delete an element from last
array.remove(Test(4));
display(array);
// Add an element at the end
array.push(Test(1));
display(array);
// Remove both occurances of 1
array.removeAll(Test(1));
display(array);
// Delete all elements
array.empty();
display(array);
// Add a new element
array.push(100);
display(array);
// Pop last element from the array
array.pop();
display(array);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment