(Optional Notes)

C++ is a 'Batteries Included' Language - The Standard Library

Often times when we discuss or even think about programming languages, we 'combine' the keywords that make up the language (e.g. class, struct, int, while, for, etc.) with functionality readily available in the library (e.g. std::cout, std::copy, std::for_each, etc.). The latter set of things are actually functions and objects that are part of the standard C++ library. The Standard Library is a set of functions, classes, and any other functionality that is readily available with your C++ compiler.

Let me explain a bit by using another popular programming language as an example -- Python. I think languages like Python for example are known for doing nearly anything by just adding another 'import'. So Python is an example of a language that we think of as very vast, and capable of doing anything very quickly.

I have a secret for you though -- C++ has just as many capabilities and a standard library of built-in functions are available. Remember the 'std::' in front of the 'cout' that we saw previously? Well 'std' is short for 'standard' and means it's part of the standard library. We can include standard library functions from many of the '#include ' statements for example. The ecosystem of commands and things that we can do in the standard library of C++ makes it what I call a 'batteries included' language, meaning we can do many things without having to rely on external resources (And that said, the C++ ecosystem is huge! Most of those Python 'imports' that you may have used, are often implemented in C++ code).

The Standard Template Library (STL)

Included with your compiler is a library known as the Standard Template Library (STL). This library implements the 'batteries included' components of C++. There are many components that make up the Standard Template Library (STL), but at a high level we need to understand three separate concepts:

1. Containers
2. Algorithms
3. Iterators

When Folks are discussing the Standard Library, most of the time they are discussing the Standard Template Library (STL) which is an implementation of the Standard Library for C++ in a specification. For readers, I'll generally refer to the STL maning the implementation of the Standard Library that is available with your compiler.

Containers

Containers are data structures that you have likely learned in school. Arrays, stack, queue, list, maps (i.e. dictionary or hashmap), unordered_map, etc.

Algorithms

Algorithms can consiste of things you are familiar with like searching and sorting. More generally speaking in C++, they are functions that allow you to operator on a 'range' and perform some computation. Usually when we think of 'sorting' for example, we think of that as the entire collection of elements in an array or al ist.

Iterators

Iterators point to some element in a container. Two iterators provide a range (i.e. the start and end iterators). So generally speaking, an iterator allows us to define the range of a computation.

Let's imagine a problem where we are searching to see if a number is in some container (and again, I'm using the C++ lingo for 'container' to mean data structure). We can probably think of this in terms of something like an array or a linked list, where we move forward one element at a time looking at each element. We call this 'iterating' one element at a time, and you could perform this in a for-loop for example.

// Iteration.cpp
#include <iostream>

int main(){
    int array[] = {1,2,3,4,5};

    for(int i=0; i<5; i++)){
        if(array[i]==4){
            std::cout << "Found 4 in our collection\n";
            break;
        }
    }

    return 0;
}

Now, this example provided is relatively trivial. Our 'start' iterator is i=0, and our end iterator is the condition i<5. Now what if I asked you to do this with a linked list? Let's take a look.

TODO: Maybe linked list forward iteration example here.
TODO: Might pull this example as we have not learned about pointers yet.

In a list data struture your iterator is stll somewhat trivial, but doing something interesting in how we are moving forward. We also need a sort of end iterator, but again this is implicit as we move until there is nothing left, usually indiciated by a nodes 'next' pointer being nullptr.

Okay, so at the very least hopefully you are convinced that we have some way of iterating, and typically we do so in a 'forward' manner when we start programming. But now, what if I asked you to 'iteratoe' through a data struture like a 'tree'. Perhaps you have learned some tree traversals algorithms to search for elements (e.g. depth-first search or breadth-first search). You could implement these algorithms in your code base, or you could also provide an 'iterator' to search the next node. This could be particularly interesting if for example you only wanted to search a subset of the tree (i.e. a sub-tree) and given two iterators (a start and an end) have a consistent way to do this. The iterators start and end again define the computation that you want to perform, and this works on any container for which there is an iterator. Note, the iterator need not always move forward either, C++ allows for backwards or bidirectional iterators (amongst other types of iterators) as well!

TODO: Provide example or move topic to another section

TODOs

Talk about why to use the STL (Overall consistency of the API, and that it is well tested)