You may have heard of an iterator. You might have even used one and hadn’t even known it. Iterators are a common tool in all sorts of languages from C++ and the STL to .NET to java and beyond. When you use an array and loop through it or manipulate its “internal pointer” from subscript 1 to subscript 2 you are manipulating the most basic of iterators. In the later .NET languages, you hear of the term “collections” and these collections involve iterators as well. But for our story we are going to go back to C++ and the Standard Template Library (STL) to show you how you can iterate a list, and to make things interesting, iterate through a list of pointers. So no need to change that browser window, you are safe right here on the Programming Underground!
The history of iteration goes back to the beginnings of most programming languages. Loops like the for or while loop are one of the main program control statements which tell the computer to repeat something several times. To iterate, iterate, iterate over again until some conditions are met. Some of these loops call a function, some repeat calculations or display output, but some of the most useful loops involve iterating over a list of some kind. This list could be a list of integers in an array or a collection of Student objects or even a list of database records.
To help facilitate this iteration the computer needed a way to keep track of the current item. It does this with an internal pointer which points at the current item in the list. In our example below the iterator is going to point to a pointer variable which in turn points to the actual ice cream cone instance in memory. We could have had it point directly to the iceCreamCone object itself, but what fun is that? Plus this way it is going to be more flexible for us. Lets say we needed to sort these cones. We can sort their pointers, leaving the objects in memory exactly the way they are. Without having to move around big objects in memory, it speeds up performance.
Before we get into the example, I want to address the topic of iterator types. We had a question recently on the board asking about the difference between a const_iterator and a regular iterator. The difference is access. With a const_iterator we move through the objects in the list but are NOT ALLOWED to actually modify the object the iterator is pointing to. Just like anything else marked as “const” we are telling the compiler that we do not intend to modify the contents of the list. Just iterate through them and pull information out of each object. The reason we would want to do this is to protect the contents of the list and make sure that if any code is trying to alter the list, our compiler will catch it and notify us at compile time. Because obviously if we don’t want our list changed and something in our code is trying to change it, we have an error somewhere. Regular iterators on the other hand allow us to move through the list, and when we are pointing to an object in the list, we are allowed to modify its contents. Maybe we are searching for a specific instance and want to update its data. We iterate, find it, then update it.
Below is a graphical picture of how our example is setup. We have our iterator arrow iterating down the list of pointers. Yeah I know, it is a pathetic looking arrow, but we are an equal opportunity arrow provider. Each pointer variable is a memory address pointing to the memory location of where our iceCreamCone objects are stored. The cones could be stored all over memory, but since pointers to them are stored in a nice list of pointers, we can iterate through the list and find them all.
To initialize our pointer, we first must setup an iterator variable using a statement like list
Besides const iterators and regular iterators there are many other iterators which do some other things like reverse etc. So be sure to check those out. All objects based on list have iterators including vectors and maps to name a couple.
What does this all look like?
#include <iostream>
#include <list>
#include <string>
#include <time.h>
using namespace std;
// Class called "iceCreamCone"
// Has a flavor, cone type, and number of scoops
class iceCreamCone {
private:
string flavor;
string conetype;
int scoops;
public:
// Constructor defines that our cones will default to vanilla 1 scoop
iceCreamCone() {
flavor = "vanilla";
conetype = "waffle";
scoops = 1;
}
// Define some properties
string getFlavor() { return flavor; }
void setFlavor(string newFlavor) { flavor = newFlavor; }
string getConeType() { return conetype; }
void setConeType(string newConeType) { conetype = newConeType; }
int getScoops() { return scoops; }
void numberOfScoops(int numScoops) { scoops = numScoops; }
};
int main() {
// Here we are creating a list of iceCreamCone object POINTERS
list<iceCreamCone*> lst;
int n;
cout << "Number of Cones to Make:" << "\n";
cin >> n;
// Lets define an array of flavors and randomly pick a flavor
// as we create our cones
string flavors[4] = {"vanilla","strawberry","chocolate","bubblegum"};
srand(time(NULL));
// Create a pointer to an ice cream cone object
iceCreamCone *cone;
// In the loop we are going to create an object and set it to our pointer
// We are going to then "configure" it to be a random flavor and random number of
// scoops between 1 and 3
for( int i=0; i < n; i++ ) {
cone = new iceCreamCone();
cone->numberOfScoops((rand() % 3) + 1);
// Set a random flavor from our array
cone->setFlavor(flavors[((rand() % 4))]);
// Push 'the pointer' onto our list of pointers
lst.push_back(cone);
}
// Here is where we iterate through the list. Much like an internal pointer
// points at each element in an array, this one points to each pointer in the list.
// We also use a const_iterator which is an iterator that we are telling the
// compiler that we WILL NOT try to modify the element it points to.
int counter = 0;
list<iceCreamCone*>::const_iterator the_iterator;
the_iterator = lst.begin();
while( the_iterator != lst.end() ) {
// For each cone pointer we list the index in the list, the flavor and the scoops it has
// Notice that we have out pointer iterator wrapped in parenthesis to force it to evaluate to
// a pointer which we then can dereference to get at the functions.
cout << "Index is: " << counter << " Flavor of cone: " << (*the_iterator)->getFlavor() << endl;
cout << "Number of scoops: " << (*the_iterator)->getScoops() << endl;
the_iterator++;
counter++;
}
// Remember these are pointers to objects, thus they need to be deleted at the end.
// We iterate through the list using a regular interator this time and delete
// each pointer as we go.
list<iceCreamCone*>::iterator reg_iterator = lst.begin();
while( reg_iterator != lst.end() ) {
delete *reg_iterator;
reg_iterator++;
}
// Clear up the list
lst.clear();
return 0;
}
At the top of the code we define our custom class iceCreamCone. Then in main we create a list of pointers to iceCreamCone objects which we then load by creating objects and storing pointers to them in the list (using push_back method of the list object). During this process of adding the pointers, we create the object first, configure its number of scoops and flavor, then add the pointer to the list. We will get at these values later when we iterate through.
As part of the configuration of flavors, we simply pluck a random flavor out of an array of flavor strings (no not like flavored dental floss) we have created. The process is…
1) Create an iceCreamCone object
2) Set its number of scoops with a random number between 1 and 3
3) Set its flavor using a random flavor from the flavors array
4) Store the pointer into the list using push_back()
Once we have the list setup we create our first const iterator. We set it to the beginning of the list and start a while loop that continues until it hits the end of the loop. I have setup a counter variable to also show the index value and show you how we are just going sequentially through the list.
Now remember that the iterator is pointing to the object in the list. To use this iterator to get at the object, we have to treat it as a pointer. In our case it is pointing to our pointer variables. This is where the trick comes in. We use the asterisk to dereference our iterator, but then we surround it with parenthesis to say “evaluate the iterator first” and then we use the pointer it returns to access the object. Hopefully that doesn’t sound too confusing. Re-read that sentence again if it didn’t make sense the first time.
Using this dereferenced pointer, we get at the methods of each ice cream cone and do this until we run through the entire list. Now since we used the “new” keyword to create these instances (back when we loaded the list), we must also remember to use the “delete” function to free up the memory.
Again we setup another iterator. This time it is going to be a regular iterator and we will start at the top of the list again. We move through the list and delete the pointer variable that our iterator is pointing at thus freeing it. After we loop through the list, we delete the list itself and we are done!
Hopefully the graphic above has made more sense to you and explains the code a bit better. I figured with the graphic, in code comments, and then a summary at the end you will get the basic idea of how iterators work, the difference between a const and a regular iterator, and how you could do something fancy like storing pointers in a list.
Keep in mind that this would work in a similar way for vectors and map objects. It is essentially the same for a lot of these template objects in the STL and you can use this example to help migrate through some of the trickier parts of dealing with iterators and iterating over lists.
Thanks again for reading and remember, iterators are your friends, friends, friends. 🙂
