© Will Briggs 2021

W. BriggsC++20 for Lazy Programmershttps://doi.org/10.1007/978-1-4842-6306-8_23

23. The Standard Template Library

Will Briggs¹  

(1)

Lynchburg, VA, USA

 

Should every programmer make his/her own vector, list, and so on? Oh, of course not. So some time back, the Standard Template Library (STL) was put into the standard. In STL you’ll find containers like list and vector; strings, as we already use them; and commonly needed functions like swap, find, and copy.

You’ll also find an annoying emphasis on efficiency. I say “annoying” because STL promotes efficiency by disabling inefficient things. If you want to use operator[] with a list, you can forget it; it’s too slow (O(N) time, if you do O notation). If you want [], the makers of STL reasoned you can use a vector. They’re right. But I still get to be annoyed.

We’ve got to get at the elements of a list somehow. How? Let’s deal with that now.

Iterators

operator[] for list doesn’t exist. Entrys are private. What can we do?

STL’s list class provides iterators – things that say where we are in the list and can traverse it. Here’s what you can do with them:

// doSomethingTo each element of myList, from beginning to end

for (list<T>::iterator i = myList.begin (); i != myList.end (); ++i)

   doSomethingTo (*i);

The iterator type is a member of list<T> like our Entry struct, but publicly available. As shown, it often starts at begin(), that is, the start of the list, and keeps going till it reaches the end() (Figure 23-1).

Figure 23-1

A list, with its begin() and end() access functions, and an iterator i denoting the second element. end() is one step past the last element

end() refers not to the last element, but to one past the last element. Think of the list as a train of cars, and this is its caboose. We check it to see if we’re going too far, using != not <. (Whether one iterator is less than another is not defined – but whether they’re equal is.)

++i and i++ work as expected; they take you to the next element.

To get not the iterator but the thing it’s referring to, put the * in front, as in the loop shown earlier.

That’s all there is to it!

Is your reaction something like “But what is an iterator?”?

Formally, it’s just as described: it’s a thing that refers to an element in the list, and when you say ++, it goes to the next element.

Informally…it’s not exactly a pointer, but it does point to something. You can use * with it, and ->, just as you would with a pointer. But ++ means go to the next element in the list, not the next memory address, as it would with a pointer. Think of it as a finger you can put on an entry and can move to the next when you like – but what it really is is a class, as in Example 23-1.

template <typename T>

class List

{

    ...

private:

    ...

    Entry* start_;                         // points to first element

    Entry* end_;                           //  ...and the caboose

public:

    class iterator                         // an iterator for List

    {

    public:

        iterator (const iterator& other)  : where_ (other.where_) {}

        iterator (Entry* where = nullptr) : where_ (where)        {}

        const iterator& operator= (const iterator& other)

        {

            where_ = other.where_;

        }

        bool operator== (const iterator& other) const

        {

            return where_ == other.where_;

        }

        const iterator& operator++()    // pre-increment, as in ++i

        {

            if (where_->next_ == nullptr) throw BadPointer();

            else where_ = where_->next_;

            return *this;

        }

        iterator operator++ (int)       // post-increment, as in i++

        {

            iterator result = *this; ++(*this); return result;

        }

        T& operator* ()

        {

            if (where_->next_ == nullptr) throw BadPointer();

            return where_->data_;

        }

        T* operator->() // This really is how you do it.  It works!

        {

            if (where_->next_ == nullptr) throw BadPointer();

            return &(where_->data_);

        }

    private:

        Entry* where_;

    };

    iterator       begin() { return iterator(start_); }

    iterator       end  () { return iterator(end_  ); }

};

Example 23-1

An iterator class for List

And now we can get to the List’s data outside the List class.

…with vector too

lists need iterators. But STL provides them for vector and other containers, and STL mavens recommend using them. Why?

• Easy rewriting of code. Consider these two versions of code with a vector:

  for (int i = 0; i < v.size(); ++i)

      doSomething(v[i]);

  and

  for (vector<T>::iterator i = v.begin(); i != v.end(); ++i)

      doSomething(*i);

I write this and later think, No, I see now vector isn’t the way to go; list is better.

If I used the first version, I’ve got major changes on both lines. If I used the second, all I have to do is change vector to list.

• Some member functions of vector already require iterators. insert, for instance.

• Generic programming. Suppose there’s something you want to do with different types of container:

myIterator = find(digits.begin(), digits.end(), 7);                                          // Where's that 7?

• Since find for list must use iterators, find for vector uses iterators too. That way you can learn one way to call the function, and it’ll work regardless of your choice of container. The section “<algorithm> (optional)” at the end of the chapter introduces a few of many such functions STL provides.

But if you do use int index for vectors as before, the sky won’t fall.

const and reverse iterators

In this code, using an iterator gives a type conflict:

class EmptyList {};                  // Exception

template <typename T>

double findAverageLength (const List<T>& myList)

{

   if (myList.empty()) throw EmptyList();

   double sum = 0;

   for (List<string>::iterator i = myList.begin();

           i != myList.end();

           ++i)

        sum += i->size();

    return sum / myList.size();

}

The compiler gives an error message that boils down to: myList is const, but you’re using an iterator with it, and that’s a type conflict.

This is how STL prevents you from using an iterator with a const container and doing something that alters the contents. The solution is to use a version of iterator that promises not to allow changes:

template <typename T>

double findAverageLength(const List<T>& myList)

{

    if (myList.empty()) throw EmptyList();

    double sum = 0;

    for (List<string>::const_iterator i = myList.begin();

           i != myList.end();

           ++i)

       sum += i->size();

    return sum / myList.size();

}

That’s all it takes.

If you like you can go through the container backward (note the rbegin and rend – the same as begin and end, only in reverse):

for (list<T>::reverse_iterator i=myList.rbegin();

     i !=myList.rend();

     ++i)

        doSomethingTo (*i); // myList must be non-const

...or do backwards and const:

for (List<string>::const_reverse_iterator i = myList.begin();

     i != myList.end();

     ++i)

        sum += i->size();

To know which to use:

• If you don’t plan to change the container, use const_iterator.

• If you do, use iterator.

• If you’re going backward, stick reverse_ in there somewhere.

Antibugging

• You get an error message too long to read:

  conversion from 'std::__cxx11::list<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >::const_iterator' {aka 'std::_List_const_iterator<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >'} to non-scalar type 'std::__cxx11::list<std::pair<std::__cxx11::basic_string<char>, int> >::const_iterator' {aka 'std::_List_const_iterator<std::pair<std::__cxx11::basic_string<char>, int> >'} requested
  Rip out things that don’t look important. This gets us

  conversion from list<pair<string, string > >::const_iterator to list<pair<string, int> >::const_iterator requested.

  My mistake is now clearer: I forgot what I wanted a pair of.

• You get pages of error messages, reporting errors in system libraries. Look for your own filename(s) in the messages and focus on those.

Exercises

1. 1.

   Using iterators in a for loop, write a function reverse which returns a reversed copy of a List you give it.

    
2. 2.

   Now write it so that instead of passing a List you pass in two iterators, maybe its begin() and its end().

    
3. 3.

   Add a const_iterator class to List.

   You’ll need new const versions of begin and end, to return const_iterator instead of iterator.

    
4. 4.

   Exercise 8 in Chapter 22’s last set of exercises dealt with equipping a List to be traversed backward. Using that, incorporate reverse_iterator and const_reverse_iterator into the List class.

    
5. 5.

   Using iterators in for loops, write functions to convert back and forth between STL lists and vectors.

    

Getting really lazy: range-based for and auto

Sure, this works for traversing a container:

for (vector<string>::const_iterator i = myVector.begin();

     i != myVector.end();

     ++i)                        // A lot of typing...

        cout << *i << ' ';

But this shorter version works too:

for (const string& i : myVector)

    cout << i << ' ';            // <-- no *: i is an element, not an //   iterator

It’s a “range-based” for loop: it uses iterators – expects begin() and end() and so works for vector, list, or whatever – but we don’t have to write all that out (yay). (Code in this section is collected and compilable in source code project/folder ch23/range-based-for-and-auto.)

It also works for arrays:

int myArray[] = { 0, 1, 2, 3 };

for (int  i : myArray)  cout << i << ' ';

Great, but I’m even lazier now. Let the compiler figure out the element type:

for (auto i : myArray)  cout << i << ' ';

                          // Overkill? I *did* know it was an int...

for (auto i : myVector) cout << i << ' ';

You can use auto for any variable declaration where the compiler can figure out the type – that is, where the variable is initialized. We do have to give it some help; it won’t apply &’s unless we tell it:

for (auto& i : myArray) i *= 2; // Without & it won't change the array

You can also do our familiar const &:

for (const auto& i : myVector) cout << i << ' ';

I use auto when type names are so long I think my fingers will fall off (list<vector<int>>::const_reverse_iterator – aigh!) and in these range-based loops. I think it is overkill for simple, basic-type declarations.¹

Spans

The language Pascal (started in 1970) lets you pass in arrays as function parameters, with the size as part of the type. Problem: You need a different function for every array size.

C and C++, as you know, don’t keep that size around, so you have the extra work of passing it in as another parameter.

Until C++20. Now you can pass in an array and have it convert to a span . The span remembers the array’s contents and size, so we can do this:

void print (const span<Heffalump> &s)

{

    for (int i = 0; i < s.size(); ++i) cout << s[i];

}

or, since we now have ranges and auto, this:

void print (const span<Heffalump> &s)

{

    for (const auto &element : s) cout << element;

}

Could we do this – pass in a sequence without having to specify length – without spans? Sure, we could use vectors. But it takes time to copy an array into a vector, especially if there are lots of elements. A span doesn’t really own its memory; doesn’t copy it, but just bundles it with its size; and makes both available, as we just saw. Example 23-2 shows how to use it.

// Program to read in & dissect a phone number

//       -- from _C++20 for Lazy Programmers_

#include <iostream>

#include <span>     // for std::span

using namespace std;

// Converts a char to a single-digit number

int char2digit (char c) { return c - '0'; }

// Read/print arrays, I mean, spans

void read  (const span<      int>& s);

void print (const span<const int>& s);

int main(void)

{

    int phoneNumber[10];

    cout << "Enter your phone # (10 digits, no punctuation, ";

    cout << "e.g 2025550145):  ";   read  (phoneNumber);

    cout << "You entered:       ";  print (phoneNumber);

    cout << '\n';

    cout << "Area code was:     ";

    print (span (phoneNumber).subspan (0, 3));     cout << '\n';

    // subspan is better, but this shows how to use

    //    a span with a pointer

    int* remainder = phoneNumber + 3;

    cout << "Rest of number is: ";  print (span (remainder, 7));²

    cout << '\n';

    return 0;

}

void print (const span<const int>& s)

{

    for (const auto& element : s) cout << element;

}

void read (const span<      int>& s)

{

    for (auto& element : s)

        element = char2digit (cin.get());

            // read in a digit, convert to int

            //   keeping it simple: no check for bad input

}

Example 23-2

A program that uses spans to read, print, and dissect a phone number

The const in front of the spans in print and read means the spans’ structure won’t be altered by the function. (So you can send in an r-value, a thing that can’t be assigned to, like span (remainder, 7).) But its elements can be changed.

The const int in print’s span means the ints in it are const too. Use this if you don’t want the function to change the array.

Exercises

1. 1.

   Rewrite any program you had in Chapter 10 in which arrays were passed into functions, to use ranges, auto, and spans.

    
2. 2.

   Suppose you’ve got data, new cases per day, from when the coronavirus first became big news (Figure 23-2). To smooth the data and help us see if it’s generally increasing or decreasing – if we’re flattening that curve – calculate for each day the average for the three before it, the three after it, and itself. (You can skip the first 3 and last 3 days of your data set.) Then print those averages. Use ranges, auto, spans, and subspan .

    

Figure 23-2

Sample data for coronavirus cases, using a 7-day average for smoothing

1. 3.

   (Uses file I/O) Do the preceding exercise, getting data from a file. You don’t know how much data is in the file, so use dynamic arrays. At least one function (the one that prints) should be passed a dynamic array.

    

initializer_lists (optional)

One thing I was sorry to give up, going from arrays to more sophisticated containers, was the bracketed initializer list, as in int array [] = {0, 1, 2, 3};. Initializing element by element is more trouble.

But we can do this with our own classes too, and it’s built in for STL. Example 23-3 illustrates doing this with Vector.

#include <initializer_list > // for std::initializer_list

template <typename T>

class Vector

{

public:

    Vector (const std::initializer_list<T>& other);

    // ...

};

template <typename T>

Vector<T>::Vector (const std::initializer_list<T>& other) : Vector ()

{

    for (auto i = other.begin(); i != other.end(); ++i)

        push_back (*i);

}

Example 23-3

Adapting Vector to use an initializer_list

std::initializer_list has iterators built in, so this’ll work. Then again, since it has iterators built in, so will this simpler version:

template <typename T>

Vector<T>::Vector (const std::initializer_list<T>& other) : Vector ()

{

    for (auto i : other) push_back (i);

}

Then we can initialize as we were used to with arrays

Vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

or since the new constructor will be implicitly called as needed:

Vector<int> U;

// ...

U = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

Exercises

1. 1.

   Write and test a constructor that takes an initializer_list, in class Point2D.

    
2. 2.

   …in class Fraction.

    
3. 3.

   If you go in order through an initializer_list, using List::push_front to add its elements to a List, the order will be reversed. (Work it out on paper if necessary, to confirm.) So go back and do Exercise 8 in the last chapter if you haven’t – it provides List::push_back – and give List a constructor that takes an initializer_list.

    

<algorithm> (optional)

Many things you may want to do with containers are in the include file <algorithm> .

Here’s how to find an element in a container named digits. It can be list, vector, or whatever. (These code snippets are collected and compilable in source code project/folder ch23/algorithm.)

using namespace std;   // the ranges namespace is part of std;

                       //    without "using namespace std," say std::ranges::

auto i = ranges::find (digits, 7); ³

if (i != digits.end()) cout << "Found a 7!\n";

find returns an iterator referencing the first element of digits equal to 7. If there is no such element, it returns digits.end().

Here’s how to copy the contents of one container to another. They can be different types of container:

ranges::copy (digits, back_inserter (newContainer));

Or maybe just copy the ones that match some criterion. We can pass in a function:

bool isEven (int i) { return i % 2 == 0; }

..

ranges::copy_if (digits, back_inserter (anotherNewContainer), isEven);

Most of these functions should work for any container type. ranges::sort (digits); does what you think it does. (Operator < for its elements must be defined.) But if you want to sort a list, you’ll have to use its member function: myList.sort ();. Go figure.

These functions erase from your container a value or erase all elements that match some condition:⁴

erase_if (digits, isEven); // returns quantity erased. Not part of ranges:: //   (just std::)

erase    (digits, 11);    // ditto. Erases all instances of 11

STL containers don’t overload the << and >> operators for I/O. Understandable, since we all may want different ways to print or read in containers, but it’s still a pain. STL provides another way to print, weirdly named

ranges::copy (digits, ostream_iterator<int>(cout, " ")); // "copy" digits //   to cout

int is what we have a list of, cout is where it’s going, and " " is what to print after each element. You’ll want #include <iterator> (though it may be provided by another system include).

There are more useful functions; an Internet search will get you what you need. cplusplus.com and cppreference.com are good places to start.

Antibugging

• You add or remove elements in or from a loop, and get a crash. When you do anything to change the contents of your container, it may invalidate iterators already in the container. Consider this code (assume digits is a vector):

  for (auto i = digits.begin(); i != digits.end(); ++i)

      if (isEven(*i))

          digits.erase (i);    // erase element referenced by i

                               // (different "erase" -- a member of //   vector)

  After you erase whatever’s at i, i points to a nonexistent element. The loop increments i and gets to another nonexistent element at who-knows-where, and the result is unpredictable.

  Which iterators are invalidated by this kind of erase and how to fix it depends on container type. You can investigate and write a fix for whatever container you chose, or use the built-in erase (myContainer, predicate) function. I know what I’d recommend.

Exercises

1. 1.

   In the string “SoxEr776asdCsdfR1234qqE..T12Ci-98jOapqwe0DweE” there is a secret code. Use an <algorithm> function to extract only the capital letters and read the code.

    
2. 2.

   (Uses file I/O) First, make a file of strings. Then make two copies of it. In one, alter the order and the capitalization of some of the strings. In the other, replace some of the strings.

   Now write a program that can read two files into vectors or lists and, using STL functions, tell if the files are different, ignoring order and capitalization. Use an STL function not covered in this section (so you’ll need an Internet search) that changes a string to all caps or all lowercase. To find what’s in one sequence but not the other, consider this algorithm:

   for each element in sequence 1 (using iterators)

      use the "find" function to see if it's also in sequence 2
    
3. 3.

   Do the preceding problem, but instead of using find and a loop, use set_difference (also not covered earlier).

    

Footnotes

1

If your compiler handles concepts, you can insist the type auto represents have some characteristic, to prevent errors:

for (std::integral auto& i: myVector) i *= 2;                        // Won’t compile if myVector’s base type isn’t integral

 

2

When converting to span from phoneNumber, C++ knows phoneNumber’s size and can put it in the span. But remainder is just a pointer. To create a span for it, we have to specify its size.

 

3

If you’re not C++20 compliant, for each of these functions, forget ranges:: and replace the container with its begin and end:auto i = find (digits.begin(), digits.end(), 7);

 

4

Before C++20, we used a function remove_if, which didn’t actually remove the things you told it to (!). It just moved them to the end and returned an iterator referencing the first of the things you wanted gone. To actually make them go away, you had to erase from the iterator it returned to the end:auto removables = remove_if (digits.begin(), digits.end(), isEven);digits.erase (removables, digits.end());

Good riddance to that one.