Iterator Lab

A video introduction is available.

In this lab, we will look at iterating over a non-container. We could have just as well called this the “Virtual Container Lab”, but the multiple meanings of virtual would confuse things.

The files for this lab are in ~cs253/Lab/Iterator. Copy them to a temporary directory. You must compile with the given Makefile, and not modify it. Compilation must not produce any warnings or errors.

Eventually, you will create a file called results.tar, and turn it in for credit.

A Non-Container

If someone asked you to name the continents, you might say:

Africa
Asia
North America
South America
Australia
Antarctica

(Then, an enjoyable argument about Europe would break out.)

Did you actually have that list of continents written down, and you iterated over them? Probably not. Instead, you generated that list, as needed. Similarly, in C++, we sometimes want to iterate over “containers” that don’t really hold anything, but instead have dynamically-generated contents.

Directory Iteration with Linux System Calls

Consider this program, dir-simple.cc:

#include <iostream>     // for cout
#include <string>       // for "…"s
#include <dirent.h>     // for opendir, readdir, closedir

using namespace std;

int main() {
    DIR *dp = opendir(".");
    while (dirent *d = readdir(dp))
        if (d->d_name != "."s && d->d_name != ".."s)
            cout << "Filename: " << d->d_name << '\n';
    closedir(dp);
    return 0;
}

d->d_name is a C string, but "…"s is a C++ string, so != comparison works.

It displays all the files in the current directory (“.”) except for the current directory itself (“.”) and the parent directory (“..”). It does so with the opendir() / readdir() / closedir() functions.

Every time readdir() is called, it reads another entry from the directory, in a system-dependent manner. It returns a pointer to a struct that contains the d_name field, a C-style string. If readdir() runs out of names in the directory, it returns a null pointer.

This program is certainly not in our usual C++ style, but it works. The opendir() / readdir() / closedir() functions are not part of any C++ standard, though they are POSIX, which is quite good. Until C++17’s Filesystem library, there was no standard C++ way to read a directory, so you take what you can get.

Here is a sample run. Note how the command ls -f1A (digit one, not the letter ell) produces the same filenames, in the same order:

% cp ~cs253/Lab/Iterator/* .
% make
g++ -std=c++17 -g -Wall -Wextra -Wpedantic -Werror -Wfatal-errors    dir-simple.cc   -o dir-simple
g++ -std=c++17 -g -Wall -Wextra -Wpedantic -Werror -Wfatal-errors dir-object.cc Directory.cc -o dir-object
% ./dir-simple
Filename: dir-object
Filename: dir-simple
Filename: Makefile
Filename: index.php
Filename: dir-simple.cc
Filename: dir-object.cc
Filename: Directory.h
Filename: Directory.cc
% ls -f1A
dir-object
dir-simple
Makefile
index.php
dir-simple.cc
dir-object.cc
Directory.h
Directory.cc

Directory Iteration in the C++ Manner

dir-object.cc is more in C++ style:

#include <iostream>
#include "Directory.h"

using std::cout;

int main() {
    Directory dir(".");
    for (auto name : dir)
        cout << "Filename: " << name << '\n';
}

We have a “container”, of type Directory, initialized with “.”, the current directory. We then iterate over that container using a typical for-each loop.

Of course, there’s complexity hidden in Directory.h and Directory.cc. Unsurprisingly, they use the opendir() / readdir() / closedir() functions.

Again, the filenames are produced in the same order as the command ls -f1A:

% cp ~cs253/Lab/Iterator/* .
% make
g++ -std=c++17 -g -Wall -Wextra -Wpedantic -Werror -Wfatal-errors    dir-simple.cc   -o dir-simple
g++ -std=c++17 -g -Wall -Wextra -Wpedantic -Werror -Wfatal-errors dir-object.cc Directory.cc -o dir-object
% ./dir-object
Filename: dir-object
Filename: dir-simple
Filename: Makefile
Filename: index.php
Filename: dir-simple.cc
Filename: dir-object.cc
Filename: Directory.h
Filename: Directory.cc
% ls -f1A
dir-object
dir-simple
Makefile
index.php
dir-simple.cc
dir-object.cc
Directory.h
Directory.cc

Understanding the code

As a group, discuss and understand Directory.h and Directory.cc.

Points to consider:

Why doesn’t the Directory ctor just read everything into a vector?

That would waste a lot of space, for a large directory. Also, we don’t need all the filenames at once, just one at a time.

What about iterator post-increment?

It’s not needed for this example, since a for-each loop uses only the efficient pre-increment. However, a well-done Directory class would implement post-increment.

What about iterator ==?

Same answer—it’s not needed for this example with for-each. However, a well-done Directory class would implement ==.

Exercises

What happens when the Directory ctor is given a non-existant directory name, or any other case that causes opendir() to fail? Try it. Fix it by having the constructor throw a descriptive runtime_error if opendir() fails. Label the changes with the comment “// Fix #1”.
It’s cumbersome for the . and .. filtering code to be in operator++. Move the filtering to a separate, private method called .wanted(), commenting the changes with “// Fix #2”.
Add a second, optional, argument to the Directory ctor that specifies a string to match. This is not a regular expression; it’s just a simple string. For example, Directory foo(".", "cat") would yield catalog, tomcat, and vacate, but not zulu. Do the string-matching in your new .wanted() method. If the string is not supplied to the constructor, then return all files (except for . and .., which are always rejected). Label the changes with “// Fix #3”.
Create a tar file results.tar that contains your work:

     tar -cvf results.tar Directory.h Directory.cc

How to submit your work:

In Canvas, check in the file results.tar to the assignment “Lab12”. It’s due 11:59ᴘᴍ MT Saturday, with a 24-hour late period for a 25% penalty.

How to receive negative points:

Turn in someone else’s work.

CS253: Software Development with C++

Spring 2023

Iterator