Skip to the content of the web site.

Programming for Nanotechnology students

This sequence of tutorials will help a nanotechnology engineering student make the transition from Python and Matlab to C++.

Other deeper topics

In the above tutorials, we have discussed an array class in the Standard Template Library (STL); however, there is a more primitive array implemented in C and C++. Unfortunately, to properly understand these more primitive arrays, it necessary to understand pointers and addresses.

If you are unwilling to worry about pointers and addresses, it is simply more ideal to use the std::array<typename, N> class.

To do:

  • describe how the call stack works,
  • describe dynamically allocated memory;

and others, as requested.

Data storage

You are already aware that you can store information in an array; however, there are efficient ways of storing information, and there are very inefficient ways of storing information. There may be ways that are sufficiently efficient when you are storing up to ten objects in an array, but these same approaches may be very inefficient if you are storing thousands of objects in an array. Data structures are means of storing information, and an array is the most primitive data structure.

Generally, however, when you are storing data, there may only be very specific interactions you intend to have with the data you are storing. If you can restrict the necessary interactions, you can often come up with more efficient means of storing that data.

Now, when storing information, there are four operations you may want to perform:

  1. inserting new data,
  2. accessing stored data,
  3. manipulating stored data, and
  4. erasing (or removing) data that is currently stored.

We will look at one example in particular, and then describe the more general approach.

What we did here was implement a stack to solve a very specific problem, and then simplified that implementation, only to see that there is an already existing container in the standard library that does what we need.

You will notice that the stack in the standard library is independent of type, but then again, a stack itself is actually an idea, and we will note that there are many ideas that are shared. This introduces the idea of an abstraction: instead of focusing on the implementation or the application, more import is what is wanted and what is necessary. This leads us to the concept of an abstract data type.

Abstract data types

In the last topic, we introduced using a stack, but then we also saw that we could create a single stack data structure that could be used for many different purposes, and not just the purpose we needed. We then saw that there was a stack container in the C++ Standard Library. However, these are all concrete implementations of a stack; but the idea of a stack does not need an implementation: a stack is a container where you can put objects into the container, and when you ask to take something out of the container, you get the last object that was put in. This is the idea of an abstraction. When you are solving a problem, you don't think of a stack as an array where objects are put at one specific location, and removed from that location when necessary; instead, you think of a last-in–first out container: the last thing put into the container is the next to come out. This is so ubiquitous that it is often described by the initialism LIFO.

Abstract data types (ADTs) are ideas that have been found to be useful in solving problems. Here, we will describe a number of abstract data types that you must be aware of. You will note that we don't discuss the implementation of any of these; instead, if you understand the idea, then you will find implementations of these ADTs and be able to use them.

Algorithms

We are going to look at some problems that can be solved by various algorithms, and we will begin by describing the more obvious solutions and then looking at progressively better solutions.

Algorithm design

When solving problems in data processing, there are a few tried-and-true approaches that work under very specific circumstances.

Other algorithms you can look up include dynamic programming algorithms.

The standard library

The most significant topic probably of most interest to students will be the data structures available in the standard library. You can view this topic here where I will first describe contiguous indexed data structures (arrays and linked lists) and then binary trees, followed by a description of both "containers" and "iterators", followed by a step-by-step examination of the containers and algorithms in the C++ standard library.