A Simple Program Using `std::list`

Like the last two, this program reads in a list of numbers from std::cin, and then calculates a few statistics about them. This version uses std::list<double>, where std::list is a linked list. (Unlike the one you'll find in Homework 5, it is a doubly linked list, where each list node links to both the next and previous nodes.)

Also, rather than using std::sort, we showcase some other standard-library algorithms that take in begin/past-the-end values.

#include <iostream>
#include <algorithm>
#include <list>

int main() {
    std::list<double> values;

    while (true) {
        double value;
        std::cin >> value;
        if (!std::cin.good()) {
            break;
        }
        values.push_back(value);
    }

    double total = 0.0;
    for (auto p = values.begin(); p != values.end(); ++p) {
        total += *p;
    }

    std::cout << "Read " << values.size() << " values" 
              << ", total " << total
              << ", average " << total/values.size() << std::endl;

    auto minElem = std::min_element(values.begin(), values.end());
    auto maxElem = std::max_element(values.begin(), values.end());
    std::cout << "Min is " << *minElem
              << ", max is " << *maxElem << std::endl;

    return 0;
}

The animated GIF below shows the compilation and use of this code.

This is really cool. We needed a listy thing, and first we used an array and now we've used a linked list, and the code hardly changed. Neat!
Hay! Hold your horses!!! I don't see how this could possibly work!
Why?
That for loop. How can it possibly work?
Huh?
If p is a double*, how can ++p get to the next list node?
You're right. List nodes aren't contiguous, and even if they were, there is more data than just the double value.
I'm suspicious of auto. I knew they were going to try to sneak something in under the radar. I'm just not sure what it is!

What's Going On?

Remember how we said we could make new types that behave like existing ones?

Let's look at the for loop:

for (auto p = values.begin(); p != values.end(); ++p) {
    total += *p;
}

Earlier (on the page Spot the Operations), we determined what operations are in play for a loop like this one. Let's restate them, but replace all the occurrences of double* with iterator.

Copy-initialization of an iterator (for p)
!= operator on two iterators
++ operator to update a variable holding a iterator
* operator on a iterator
+= operator adding to total

So if we had a new, custom iterator class that supported the first four operations in this list, the loop could work, even though an iterator isn't a pointer.

And that's exactly what std::list<double> does. The begin() and end() functions don't return a double* at all. They return an instance of a custom class with overloaded operators. The specific class is std::list<double>::iterator, so we could have written the loop as:

for (std::list<double>::iterator p = values.begin(); p != values.end(); ++p) {
    total += *p;
}

The key thing is that this custom class works enough like a pointer for the loop to work.

Oh, this is even cooler!
Yes! I wanted us to overload operator*, and now it's happened.
Just so I'm clear, the “iterators” returned by begin() and end() on a std::list<double> are not pointers.
That's right. They return an iterator, which is a custom class. Maybe there's a private pointer data member inside it doing something, but that's not for us to worry about. To us, the iterator just feels a lot like a pointer, allowing us to move through the list with a standard loop (even though behind-the-scenes we're really jumping around in memory from list node to list node).
Why, oh, why would anyone want to make more things that feel like pointers!! Arghh!
Loops with pointers that work over arrays are very familiar to C programmers. It's part of their tradition. Providing iterators that work like pointers helps them feel at home in C++, even when the data structure is a totally different one.

The type std::list<double>::iterator does not support pointer-math style operations (because it can't do so efficiently), it only supports going forwards and backwards with ++p and --p, which is why it's known as a “bidirectional iterator”.

In contrast, std::vector<double> also has an iterator type (it doesn't return a pointer for begin() and end() either!). The type std::vector<double>::iterator does support pointer-math–style operations. Thus it's known as a “random-access iterator”.

(When logged in, completion status appears here.)

Previous Page Go to Parent Page

CS 70

Warning: Missing Prerequisites

A Simple Program Using `std::list`

What's Going On?

Instructor Controls

Warning: Missing Prerequisites

A Simple Program Using std::list

What's Going On?

Instructor Controls

A Simple Program Using `std::list`