`std::forward_list` walk until iterator is null?

Question

Is it possible to walk a std::forward_list, incrementing an iterator, until said interator is null? The old-fashioned way...

In the following example, I create a print() function.

#include <iostream>
#include <forward_list>

void print(std::forward_list<int>::iterator fl_it, std::forward_list<int>::iterator e) {

    while (fl_it != e) {
        std::cout << *fl_it  << ' ';
        ++fl_it;
    }

    std::cout << std::endl;  //-> 1 2 3
}

int main() {
    std::forward_list<int> fl = {1, 2, 3};
    print(fl.begin(), fl.end());
    std::cout << std::endl;
    return 0;
}

Notice how passing an iterator pointing to the end of the list is necessary, so that we know when to stop walking.

What I want to do is simply pass an iterator to the head of the list, and step along until there are no more elements, like so:

void print(std::forward_list<int>::iterator fl_it) {
    while (fl_it != nullptr) {
        std::cout << *fl_it << ' ';
        ++fl_it;
    }
    std::cout << std::endl;
}

My compiler doesn't like this fl_it != nullptr business.

My first inclination was to look for a method to check if the iterator is null, and references the end of the list. Sadly, such a method does not exist.

Any ideas?

Think of it this way: If you had the first element of an array and no other information, could you get to the end? — AndyG, Jan 12 '17 at 20:09
And would you be able to *identify* the end when you came to it? — jaggedSpire, Jan 12 '17 at 20:10
It should be noted that there *are* some kinds of iterators which *sort of* have this functionality--`std::istream_iterator` for one has an `istream&` constructor and a default constructor. The default-constructed iterator acts as the end iterator for the range, and the istream constructed iterator will compare equal with a default-constructed iterator when it encounters the end of the wrapped istream. So you could pass an `istream_iterator` into a function, and simply construct the end iterator inside it. But this doesn't apply for many types of iterators. — jaggedSpire, Jan 12 '17 at 20:14
@AndyG, in an array, no, you need an argument count. A linked list is a different animal: we have the ability to set the pointer of the last node to a sentinel value. — kmiklas, Jan 12 '17 at 20:35

score 2 · Answer 1 · answered Jan 12 '17 at 20:10

You don't.

std::forward_list is a standard library container. Like all containers, it goes from begin to end. There are no "null" iterators. Operations therefore are on a range of iterators.

Note that the Range TS proposal intends to allow "sentinel" types instead of requiring end iterators. A single sentinel could compare equal to the end iterator of any range. So forward_list could indeed be updated to have such a value.

But it still wouldn't be a "null" iterator.

score 0 · Answer 2 · edited May 23 '17 at 10:29

0

You should realise that the iterator object is not exactly a pointer. It is an object and it represents the position of an item in a datastructure. Also incrementing the end iterator does not result in a null iterator. It is undefined behavior. Look at Can an STL map iterator go out of bounds through incrementing?

edited May 23 '17 at 10:29

Community

1
1

answered Jan 12 '17 at 20:12

Tapan Chugh

354
2
4

score 0 · Answer 3 · answered Jan 12 '17 at 20:16

0

The iterator is not null when at the end of the list, instead it is equal to the list's end iterator fl.end(). So both iterators need to be passed to the function.

The internal implementation of the iterator depends on the STL library used, for std::forward_list its interface is such that it fulfills the ForwardIterator concept: http://en.cppreference.com/w/cpp/concept/ForwardIterator .

answered Jan 12 '17 at 20:16

tmlen

8,533
5
31
84

"both iterators need to be passed to the function" <-- seems sorta anti-thematic where forward linked lists are concerned, no? Aren't one-direction linked lists supposed to have an end marker? We're supposed to be able to march along until we hit the end of the line. – kmiklas Jan 12 '17 at 20:20
Internally `fl.end()` probably represents a sentinel value, and comparing it to the end iterator actually checks if a pointer is null (depending on how `std::forward_list` is implemented). But in STL for all container types, two iterators are always used to iterate through the list. – tmlen Jan 12 '17 at 20:27

`std::forward_list` walk until iterator is null?

3 Answers3