I am an engineer turned self-taught programmer, with no formal computer science training. (That's by way of an excuse for what follows.) For about 10 years up to about 1995 I used C but never really got fully to grips with it. Then I moved on, first to Java then later JavaScript and Python. Recently however I started some ESP8266 projects. I tried Micropython but found it lacking in “bare metal” capabilities and it takes up too much space in a 512KB device.
So it was time to return to C - or more specifically C++. It came as something of a shock to rediscover how complex it is, how easy it is to make simple programming errors that cause programs to crash, and how lacking C++ is in features we take for granted in other languages. One of these is dynamic arrays, which allow elements to be freely added without the need to consider memory management.
There are of course libraries out there that could serve my needs, but I usually find it's a better use of my time (and more enjoyable) to spend a couple of days writing code rather than hunting down potential candidate libraries, getting to understand them and often as not rejecting them as unsuitable. So if the code that follows is similar to something already available then it's a complete coincidence.
My dynamic arrays start with a linked list class. This has a no-argument constructor and 3 main methods:
void add(element) adds the supplied element to the list. It throws an exception if the request fails
int getSize() returns the number of elements in the list
void* get(index) returns the element at the specified position
void clear() clears the list
The list is doubly-linked (forwards and backwards) and needs no malloc() commands as the elements added are all pointers to the original items. All elements are stored as void* pointers so the list can handle any kind of data. An inner LinkedListElement class handles each element.
Here's the code:
#ifndef LINKED_LIST
#define LINKED_LIST
#include <stdio.h>
/*
This is a doubly linked list element able to store any kind of data.
The content is immutable within this class.
*/
class LinkedListElement {
private:
const void* content;
LinkedListElement* previous = nullptr;
LinkedListElement* next = nullptr;
public:
// Get the content of this element
void* get() {
return (void*)content;
}
// Get the previous element pointer
LinkedListElement* getPrevious() {
return previous;
}
// Set the previous element pointer
void setPrevious(LinkedListElement* data) {
previous = data;
}
// Get the next element pointer
LinkedListElement* getNext() {
return next;
}
// Set the next element pointer
void setNext(LinkedListElement* data) {
next = data;
}
// Constructor
LinkedListElement(const void* data) {
content = data;
}
// Destructor
~LinkedListElement() {}
};
class LinkedList {
private:
int size = 0; // the number of items
LinkedListElement* head = nullptr;
LinkedListElement* tail = nullptr;
public:
///////////////////////////////////////////////////////////////////////
// Get the size (the number of elements in the list)
int getSize() {
return size;
};
///////////////////////////////////////////////////////////////////////
void add(const void* data) {
LinkedListElement* element = new LinkedListElement(data);
if (size == 0) {
head = element;
tail = head;
} else {
tail->setNext(element);
element->setPrevious(tail);
tail = element;
}
++size;
}
///////////////////////////////////////////////////////////////////////
void* get(int index) {
if (index < size) {
LinkedListElement* element = head;
while (index > 0) {
element = element->getNext();
--index;
}
return element->get();
}
return nullptr;
}
///////////////////////////////////////////////////////////////////////
// Clear the list. Remove everything except the element data.
void clear() {
LinkedListElement* walker = head;
if (walker != nullptr) {
while (walker->getNext() != nullptr) {
LinkedListElement* next = walker->getNext();
delete walker;
walker = next;
}
delete walker;
}
size = 0;
}
// Default constructor
LinkedList() {}
// Destructor
~LinkedList() {
clear();
}
};
#endif
Linked lists are simple and effective, but to retrieve an element means “walking” the list, which has a performance overhead that gets significant for large lists. By contrast, an array provides instant access to its elements but requires knowledge of its size to allocate memory for its list of pointers before any elements can be added. To get around both these limitations we need to combine an array with a linked list.
The next class is StringArray, which is an array of character strings referenced by char* pointers. As well as this array it also contains a LinkedList. The significant methods of the class are
void add(element) adds the supplied element to the StringArray. It will be added to the internal linked list.
int getSize() returns the number of elements held by this class instance. This is the sum of those in the array and those in the linked list.
char* get(index) returns the element at the specified position. The element might be taken from either the array or the linked list, depending on the index and how many elements there are in each part.
void flatten() “flattens” the array. It creates a new array big enough to hold the contents of the existing array plus those in the list, copies all of their pointers to the new array then clears the list and frees the old array. Note that the data itself is untouched and unaffected. This method is “idempotent”; that is, it can be called as often as desired. If the list is empty it does nothing.
Here's the code:
#ifndef STRINGARRAY
#define STRINGARRAY
/*
StringArray is a memory-efficient class for managing arrays of strings.
A typical usage is to break a piece of text into lines and make them
available by line number.
*/
class StringArray {
private:
int size = 0; // the number of items
char** array = (char**)malloc(1); // the array of items
LinkedList* list; // a list to hold new data items
public:
///////////////////////////////////////////////////////////////////////
// Get the size (the number of elements in the array)
int getSize() {
return this->size + list->getSize();
};
///////////////////////////////////////////////////////////////////////
// Get a specified item.
// If the index is greater than the array size, return the item from the list.
char* get(int n) {
if (n < size) {
return array[n];
}
else if (n < size + list->getSize()) {
return (char*)list->get(n - size);
}
return nullptr;
};
///////////////////////////////////////////////////////////////////////
// Add an item. This goes into the linked list.
void add(const char* item) {
list->add(item);
}
///////////////////////////////////////////////////////////////////////
// Flatten this item by creating a single array to hold all the data.
void flatten() {
char** oldArray = array;
int oldSize = size;
// Create a new array big enough for the old array and the list
int total = oldSize + list->getSize();
if (total > 0) {
array = (char**)malloc(sizeof(StringArray*) * (total));
// Copy the old array to the new
size = 0;
while (size < oldSize) {
array[size] = oldArray[size];
size++;
}
free(oldArray);
// Copy the list to the new array
int n = 0;
while (n < list->getSize()) {
array[size++] = (char*)list->get(n++);
}
list->clear();
}
}
///////////////////////////////////////////////////////////////////////
// Default constructor
StringArray() {
list = new LinkedList();
}
///////////////////////////////////////////////////////////////////////
// Destructor
~StringArray() {
free(array);
delete list;
}
};
#endif
Not shown here are useful methods such as indexOf(char* item), which searches for and returns the index of an item in the array. My own implementation also has a parse(char* data) method that takes a single string containing a number of items separated by a common delimiter (such as lines of a text document or a CSV file), breaks them up into individual strings and adds them all to the array.
The final class is ObjectArray, which is an array of arbitrary objects referenced by void* pointers. This class is useful for holding data of varying types. It differs only very slightly from the previous StringArray. Here’s the code:
#ifndef OBJECTARRAY
#define OBJECTARRAY
/*
ObjectArray is a memory-efficient class for managing arrays of arbitrary objects.
*/
class ObjectArray {
private:
int size = 0; // the number of items
void** array = (void**)malloc(1); // the array of items
LinkedList* list; // a list to hold new data items
public:
///////////////////////////////////////////////////////////////////////
// Get the size (the number of elements in the array)
int getSize() {
return this->size + list->getSize();
};
///////////////////////////////////////////////////////////////////////
// Get a specified item.
// If the index is greater than the array size, return the item from the list.
void* get(int n) {
if (n < size) {
return array[n];
}
else if (n < size + list->getSize()) {
return (void*)list->get(n - size);
}
return nullptr;
};
///////////////////////////////////////////////////////////////////////
// Add an item. This goes into the linked list.
void add(const void* item) {
list->add(item);
}
///////////////////////////////////////////////////////////////////////
// Flatten this item by creating a single array to hold all the data.
void flatten() {
void** oldArray = array;
int oldSize = size;
// Create a new array big enough for the old array and the list
int total = oldSize + list->getSize();
if (total > 0) {
array = (void**)malloc(sizeof(ObjectArray*) * (total));
// Copy the old array to the new
size = 0;
while (size < oldSize) {
array[size] = oldArray[size];
size++;
}
free(oldArray);
// Copy the list to the new array
int n = 0;
while (n < list->getSize()) {
array[size++] = list->get(n++);
}
list->clear();
}
}
///////////////////////////////////////////////////////////////////////
// Default constructor
ObjectArray() {
list = new LinkedList();
}
///////////////////////////////////////////////////////////////////////
// Destructor
~ObjectArray() {
free(array);
delete list;
}
};
#endif
Here is a simple test program to illustrate its usage. (Yes, I know the classes defined here are all animals and could share a common superclass, but that’s not the point of the exercise.)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkedlist.cpp"
#include "objectarray.cpp"
class Cat {
private:
const char* name;
public:
char* getName() { return (char*)this->name; }
Cat(const char* name) { this->name = name; }
};
class Dog {
private:
const char* name;
public:
char* getName() { return (char*)this->name; }
Dog(const char* name) { this->name = name; }
};
class Rabbit {
private:
const char* name;
public:
char* getName() { return (char*)this->name; }
Rabbit(const char* name) { this->name = name; }
};
class Canary {
private:
const char* name;
public:
char* getName() { return (char*)this->name; }
Canary(const char* name) { this->name = name; }
};
// Main program
int main(void) {
ObjectArray* pets = new ObjectArray();
pets->add(new Cat("Garfield"));
pets->add(new Dog("Scooby"));
pets->add(new Rabbit("Bugs"));
pets->add(new Canary("Tweety Pie"));
pets->flatten(); // optional
printf("I have a cat called %s,\n", ((Cat*)pets->get(0))->getName());
printf("a dog called %s,\n", ((Dog*)pets->get(1))->getName());
printf("a rabbit called %s,\n", ((Rabbit*)pets->get(2))->getName());
printf("and a canary called %s.\n", ((Canary*)pets->get(3))->getName());
};
The output when run is
I have a cat called Garfield,
a dog called Scooby,
a rabbit called Bugs,
and a canary called Tweety Pie.
Having written these simple classes I am amazed by how much the rest of my code now depends on them. I hope others may find them just as useful.
Photo by Pierre Bamin on Unsplash
Top comments (0)