Picking Up Telemetry where we left it — Lists.

Picking up this project after months of wanting to resume, I walk through redesigning the library from scratch and taking it further.

Photo by Koushik Chowdavarapu on Unsplash

Back in November 2019, I decided I needed to brush up my beyond-rusty C++ and so I decided to finally start working on a data-structures library while documenting my progress here on Medium. The idea was to walk my self through the design and implementation of such a library while documenting theoretical concepts, helpful notes and eventually creating a ‘Data Structures for Dummies’ level tutorial for others like me! If you’re seeing this post for the first time, head here to find out more:

Telemetry — Implementing a library for Data Structures and Algorithms in C++.

And one post later, it fell through. With incomplete code languishing on GitHub, commits waiting to be pushed and blogs aching to be written. Oops!

But with the Lockdown upon us, college behind me and time on my hands, I decided there’s no better time to get cracking on this library again — and so here I am!

The What and the Why, once again.

In this discussion, let me quickly go through some salient revisions I’ve made concerning my goals for this exercise and the structure of the library itself. For starters, I’ll talk about the changes to the List class defined in List.h .

1. The goal is now to implement a drastically simplified (but still similar) variant of the Standard Template Library. Going forward, I will try to implement all algorithms, containers and data structures such that they resemble their STL cousins as closely as possible.
2. I’ve implemented the List as a doubly-linked list and re-written all functions to match. Some new functions mirror their STL equivalents (poorly, hehe) too — we’ll talk about some significant ones below! The updated goal means I’ve tried to implement Templates, Exception Handling, and the like as far as I could given my still rusty C++!

Anyhoo, back to business.

Before moving to the code, here’s a quick reminder. I will regularly push all my code here:

utkarshpant/telemetry

With that out of the way, here goes… First, let’s go over some cosmetic changes to the organization of the library. For neatness and readability, I’ve separated all class declarations and definitions into their corresponding header (.h) and implementation (.cpp) files respectively. Doing so means that in case we decide to rework some of the implementation of a class in the future, we don’t have to recompile everything over again — we can do with recompiling just the implementation file.

That brings us to the second change in our library going forward…

Templates.

What are templates? Simply put, templates allow us to define a class or a function once, independent of the data types involved, rather than relying on overloading to handle multiple data types.

While I’d love to delve into the finer details, I won’t because:

1. I haven’t gotten the hang of them completely myself, and
2. I found this fantastic walkthrough on the subject to do the heavy lifting for me (An Idiot’s Guide to C++ Templates — Part 1, Ajay Vijayvargiya):

An Idiot’s Guide to C++ Templates — Part 1

The thing with templates is, however, that when we define class templates, the definition must usually follow the declaration in the same header file.

From the C++ Super FAQ on the subject (linked in references):

1. A template is not a class or a function. A template is a “pattern” that the compiler uses to generate a family of classes or functions.

2. In order for the compiler to generate the code, it must see both the template definition (not just declaration) and the specific types/whatever used to “fill in” the template. For example, if you’re trying to use a Foo<int>, the compiler must see both the Foo template and the fact that you’re trying to make a specific Foo<int>.

3. Your compiler probably doesn’t remember the details of one .cpp file while it is compiling another .cpp file. It could, but most do not and if you are reading this FAQ, it almost definitely does not. BTW this is called the “separate compilation model.”

That’s why, for now, everything is bunched in the relevant header files, until I learn of a more elegant solution.

The next new concept I’ve applied is Exception Handling.

Exception Handling.

Everyone makes mistakes. Sometimes, these are in the form of incorrect code that won’t compile. We must correct these errors before our code will compile. Other times, code will compile perfectly but your program will come to a sputtering halt because something unexpected happened (like dividing a number by 0 in a calculator program) and the best we can do is anticipate them. These are the two types of exceptions — checked and unchecked.

In C++, we deal with unchecked exceptions and have a defined way of handling them. Cplusplus.com has this to say:

Exceptions provide a way to react to exceptional circumstances (like runtime errors) in programs by transferring control to special functions called handlers.

To catch exceptions, a portion of code is placed under exception inspection. This is done by enclosing that portion of code in a try-block. When an exceptional circumstance arises within that block, an exception is thrown that transfers the control to the exception handler. If no exception is thrown, the code continues normally and all handlers are ignored.

Once again glossing over the details, I’ll let you explore the tutorial at your own pace:

Exceptions

For our List class, I have defined two custom exceptions: EmptyListException and OutOfBoundsException. The former is thrown whenever we invoke any functions such as listObj.printList() or listObj.pop() on an empty List and the latter is thrown when we try to access/manipulate an ‘index’ that is greater than the size of the list, as in listObj.erase(position) .

Iterators.

Since I want this library to mirror the STL as far as possible, we also need to ensure that our container is inter-operable with it’s STL cousins, and a very important aspect of this is providing iterators.

Iterators are references to specific locations in your container allowing specific behaviors — bidirectional traversability, read-only/write access, etc.

Also, this is super confusing. I’ll update this as and when I can wrap my head around what’s happening here and how to present it simply. For now, you can skip over this part — it’s just an effort to be more like our cooler STL cousins and doesn’t affect the basic functioning of our Linked List and its functions!

fin.

References.

1. An Idiot’s Guide to C++ Templates — Part 1 https://www.codeproject.com/Articles/257589/An-Idiots-Guide-to-Cplusplus-Templates-Part-1
2. Standard C++ — The C++ Super FAQ https://isocpp.org/wiki/faq/templates#templates-defn-vs-decl
3. Why can templates only be implemented in the header file?https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file
4. Exceptions — C++ Tutorials http://www.cplusplus.com/doc/tutorial/exceptions/
5. list::remove_if() — C++ Reference http://www.cplusplus.com/reference/list/list/remove_if/