Iterator Lab

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.                 

Eventually, you will create a file called dir.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;
}

Note that 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?
• What about iterator post-increment?
• What about iterator ==?

Exercises

1. 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”.
2. 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”.
3. 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”.
4. Create a tar file dir.tar that contains your work:

    tar -cvf dir.tar Directory.h Directory.cc

How to submit your work:

In Canvas, check in the file dir.tar to the assignment “Lab12”.                 

How to receive negative points:

Turn in someone else’s work.