5.3.3 Iterating Through a Set

As mentioned before, sets do not have an index value and are not stored in a sequential order. As a result, a standard for loop from zero to less than the length is not possible.

Instead, traversing a set is possible using an iterator as you saw in the last lesson.

For Loop Traversal

Like using an iterator for a vector, you can set up an iterator to iterate a set.

set<int> nums {2, 8, 4, 9};
for (set<int>::iterator itr = nums.begin(); itr != nums.end(); itr ++){
    cout << *itr << endl;
}

Notice in this example the iterator variable, itr, is declared and initialized inline. Each time through the loop, the iterator will point to a different value. You can then retrieve that value using the dereference operator, *.

Traversal Order

So what order will it print in? As mentioned earlier, sets are stored in a version of a binary tree. In a binary tree, new values are inserted in order.

Here is an example of a tree. The first member of the tree would be 4. The second member was either 2 or 9. Since the 9 is greater than the 4, it is inserted to the right. If the next value is 7, then it goes right since it is greater than 4, but then gets inserted to the left of 9 since it is less than 9.

If you were to insert a 3, where would it go? Since it is less than 4, it goes left at the top node, but greater than 2, so it gets inserted to the right of the 2.

When a set traversal is executed, it does what is called a depth-first traversal. This means it goes all the way to the bottom left of the tree, then works its way back to the right. In the above tree, this means the first value that will get printed is the 1. It then backs up and prints the two before exploring the nodes to the right on the two, in this case, 3.

If you follow this through, you will notice that the traversal is performed in sequential order.

While Loop Traversal

Just like other loops, a for loop can be converted into a while loop. Here is an example of a while loop traversal.

set<int> nums {4,2,9,7,1,5,8,3};

set<int>::iterator itr = nums.begin();

while(itr != nums.end()){
    cout << *itr << endl;
    itr ++;
}

Try This Example