Last active
June 19, 2019 16:39
-
-
Save sonus21/7334d98c4a5865dc19d9bbe48caa7d7b to your computer and use it in GitHub Desktop.
Dynamic array in C++ which grows/shrink at the rate of 2.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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