This chapter covered iterators, list containers, and new functions for strings, vectors, and lists.

As before, I’m just going to post an unordered list of definitions, jargon, types and functions, etc.

Chapter 5 / Using sequential containers and analyzing strings

On the standard library:

”..the standard library provides useful data structures and functions … [and] reflects a consistent architecture.” In the text, they explain how knowing how to use one kind of container(vectors) will help me to learn and use others.

predicate

Apparently, a “predicate” is jargon for a function that is passed as a true / false condition for a loop etc.

Two ways for functions to change stuff, so far

So far, this book has identified 2 ways for functions to manipulate objects: by what it returns, and by manipulating any nonconst references passed to the function when called.

vectors and fast random access

Vector containers are optimized for fast random access and are very slow for accessing specific indexed values …

vector.push_back(x)

Appends the given x value to end of container.

vector.erase(vector.begin() + i)

Erases the value at index i. The parameter within the parentheses is an element value, not the index of the value. Note that erasing also lessens the number of elements by 1, so for loop iterations where you erase() you must not increase the counting variable so that the invariant remains true.

On loops and erasing…

It is important that you DO NOT precompute the number of elements in the container and compare that for each iteration; erasing changes the number of elements in a container! Therefore, vector.size() must be called for each iteration(for example, inside of the while condition), for a fresh count of the number of elements.

Sequential versus random access

Sequential and random are two different ways of accessing a container; one proceeds sequentially, the other uses indices or otherwise to access varied elements. Different data structures may be optimal for different tasks, and in particular different ways of accessing a container. Here’s a quote from the book:

“The reason we care about the sequence in which we access container elements is that different types of containers have different performance characteristics and support different operations. If we know that our program uses only those operations that a particular type of container supports efficiently, then we can make our program more efficient by using that kind of container.” (Koenig & Moo, 79)

Iterator

Could an iterator possibly be a special type for use with containers in completing iterations of a loop more optimally? An iterator is a value that:

“…identifies a container and an element in the container …lets us examine the value stores in that element …provides operations for moving between elements in the container …restricts the available operations in ways that correspond to what the container can handle efficiently.” (Koenig & Moo, 80)

iterator and const_iterator

These are two types associated with “standard”(?) containers. iterator allows modification of elements, and const_iterator type only allows reading of elements. Type is written as vector<double>::const_iterator, for example.

vector.begin()

Container methods like .begin() or .end() actually return an iterator type value. Authors tell there is also an automatic one-way conversion between values of type iterator and type const iterator—less overhead for the developer. Being able to compare the iterator to .end() is great, because it means that we do not have to compute an i index any longer—one less step, and much more intuitive. Abstraction is great.

++iter

The ++ operator is overloaded for the iterator type, so that it means to increment sequentially…

The dereference * operator

The iterator is a weird value that is quasi-index and quasi-reference to a specific value… To read the specific value(or access for writing), it is necessary to use the dereference operator: if ( (*iter).name == "Patrick" ) { ... } Note: * is lower precedence than other operations, and may need to be enclosed within parentheses.

For iterators of a struct container, there is a short-cut:

For iterators of a struct container, there is a short-cut for writing (*iter).memberName; you may use the -> syntax: iter->memberName. Cool.

Aside: I’m glad I have some background in scripting and programming, working with containers, etc, because the exercises in this book don’t do some of these types justice… whereas I can think of ways I could have implemented my past-written programs differently using new stuff from this book.

.erase() invalidates…

vector.erase(iter) invalidates all iterators at that element and beyond… Therefore, even if you precompute an iterator for the value 10 elements deeper in the container, or an iterator for the last value in the list, it will vanish when you call .erase(). The function returns the iterator positioned on the immediate sequential value, however. iter = vector.erase(iter) yields the value of the iter + 1…

The list type

Lists are better suited than vectors for maneuvering elements within the middle of a container:

“Just as vectors are optimzied for fast random access, lists are optimized for fast insertion and deleetion anywhere within the container. …if a program deletes many elements from the middle of the container, then lists will be fsater for large inputs [than vectors].” (Koenig & Moo 85)

“Template”

A “template” is jargon for a function or class that can operator with multiple data types, instead of hard-coded for just one data type. vectors and lists are examples of templates, declared with the type they use, like so: vector<double>.

Guess what <algorithm>-defined function works on vectors but not lists?

The <algorithm>-defined sort() function does not work on list containers. And I was building the chapter exercise well before the author detailed this fact—so I had to troubleshoot why my program was no longer compiling.. The list class has its own member function to .sort() values.

On performance…

The authors computed the performance time for computing the chapter exercise(a grading program) using lists or vectors for students’ records. For a small size of 735 records, each choice of container type ran in 0.1 seconds. But for larger amounts of records:

“For the file with 73,500 records, the list version of the program took less than nine seconds to run, whereas the vector version took nearly ten minutes.”

[continued]

The authors point this out as a “good example of the effect of data structure choices on performance.”

strings also work like containers

It is possible to use indices or iterators with a string, among overloaded operators etc.

isspace( char )

Defined in <cctype>. This predicate takes a char and returns true for whitespace values and false for anything else.

Left-hand rule

&& and || are operators that test the left operand first, and short-circuit as soon as the first false condition arises… a consideration for better performance, I imagine.

stringName.substr(i, len)

The member function substr() of the string class takes an index and a length, and returns a new string of the given argument.

getline(istreamName, stringName)

The getline() function is defined in <string> and is useful for grabbing a whole line of input, including whitespace; the more common cin parses out whitespace… getline returns an istream reference, as cin does, and therefore can be used as a condition in a statement(as all istreams can).

+=

This is the compound assignment operator.

list[indexVar++]

By placing the increment operator ++ after the indexVar, it is incremented only after the existing value is passed as the index… or likewise, for when the operation is used in other places.

newStringName = string(stringSizeVar, ' ')

This should have been noted in an earlier set of chapter notes, but: the string() function takes the string size(a special data type) and a character literal, and creates a new string that long and with that character…

container.rbegin() and container.rend()

These supposedly return iterators referring to the last and first elements(reverse), allowing access to the container in reverse order… although the book hasn’t presented an exercise utilizing these so I can’t know the precise nature of these iterators.

vector<double> doppelganger(original)

This creates a new vector doppelganger which is a copy of the existing vector original.

container<type> name(155)

This creates a new container with 155 elements initialized with whatever value is default for the type(i.e. class defines).

container<type> name(155, otherVar)

This creates a new container with 155 elements initialized to the value of otherVar.

container<type> name(b, e)

b and e are existing iterators for an identical-type container that already exists. This will create a new container with the elements copied from the other existing container between iterators b and e.

containerName.empty()

This is a predicate which indicates whether the container has any elements or no elements.

container.insert(d, b, e)

This function copies the elements in the range [b, e) and inserts them into the container just before iterator(?) d.

container.erase(iter) or container.erase(b, e)

Erases the element at position iter or erases the elements in range [b, e).

*iter

The dereference operator, *, passes the value stored at the position of the iterator. As noted above, this is frequently used for class objects, and a special operator exists: iter->memberName is the same as (*iter).memberName.

vectorName.reserve(n)

Preallocates enough memory for the vector to hold n elements. It does not affect the computable number of elements in the container; for example, vectorName.size() would still yield the actual number of elements, and not n unless they were coincidentally the same value.

vectorName.resize(n)

This function gives the vector a new size, n, and truncates any exceeding elements, or adds sufficient new elements initialized to the appropriate/default value defined by the class.

isalpha(char)

Predicate for whether a character is alphabetic. Defined in <cctype>.

isdigit(char)

Predicate for whether a character is a digit. Defined in <cctype>.

isalnum(char)

Predicate for whether a character is a letter or a digit. Defined in <cctype>.

ispunct(char)

Predicate for whether a character is a punctuation mark. Defined in <cctype>.

isupper(char)

Predicate for whether a character is an uppercase letter. Defined in <cctype>.

islower(char)

Predicate for whether a character is a lowercase letter. Defined in <cctype>.

toupper(c)

Returns the uppercase equivalent to c. Defined in <cctype>.

tolower(c)

Returns the lowercase equivalent to c. Defined in <cctype>.

The end

That chapter took me awhile.