How can I get a forward iterator to the last element?

Question

I'm looking for a convenient option to get the last element from a container/range which only supports forward traversal, which essentially means I cannot do stuff like std::prev(std::end()). For now the only idea I have is this one:

const std::forward_list<int> list{1, 2, 3, 4, 5};
auto it = list.cbegin();
std::advance(it, std::distance(it, list.cend()) - 1);
std::cout << *it << std::endl;

Is there a more convenient way to get to the last element of a forward traversal range? Boost is welcome.

@Irelia Forward iterators cannot move backwards, your code won't compile. — Kaiyakha
– Kaiyakha, Commented Apr 25, 2023 at 22:06
Walk the list with a forward sniffing iterator, return the previous successful iterator. — Eljay
– Eljay, Commented Apr 25, 2023 at 22:08
I'd say you have XY problem. Why did you choose a container with forward iterator only if you need to access last element? It is possible, as Eljay said, but it's probably not a good idea. — Yksisarvinen
– Yksisarvinen, Commented Apr 25, 2023 at 22:14
@Kaiyakha well, teamwork means to discuss such design decision amongst the whole team with equal rights to address concerns, no? — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Apr 25, 2023 at 22:17
Might be worth working up a business case demonstrating that use of algorithm X allows delivery of that module in Time t, but increases the delivery time of the four modules that use it to tn, ultimately delaying the project more than tn for module X and only t for the other four. — user4581301
– user4581301, Commented Apr 25, 2023 at 22:18

Mooing Duck · Accepted Answer · 2023-04-25 22:27:13Z

4

make a helper function that iterates until the next one would the end

template<class iterator>
iterator find_next_to_last(iterator first, iterator last) {
    assert(first != last);
    iterator next = first;
    while(++next != last)
        first = next;
    return first;
}

edited Apr 25, 2023 at 22:27

answered Apr 25, 2023 at 22:13

Mooing Duck

67.6k19 gold badges107 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Eljay Over a year ago

Should also check if (first == last) for an empty list, unless empty list is disallowed by contract (in which case assert(first != last);).

Mooing Duck Over a year ago

@Eljay good catch! After some thought, I decided to disallow by contract.

Eljay · Accepted Answer · 2023-04-26 01:28:50Z

I like Mooing Duck's answer, but I thought a tiny tweak to handle an empty list would be nice. Although nothing wrong with disallowing that situation by contract, plenty of functions in the standard library impose constraints by contract.

But to answer your question...

Is there a more convenient way to get to the last element of a forward traversal range?

...no, there is not a more convenient way in general. You need to walk the forward list to get to the back most element. (Assuming you can't cache an iterator to the back most element.)

#include <forward_list>
#include <iostream>
#include <iterator>
#include <utility>
#include<cassert>

template <typename I>
auto back(I it, I last) {
    using std::next;
    auto n = it;

    while (n != last) {
        it = std::exchange(n, next(n));
    }

    return it;
}

// Container-to-iterator-pair convenience function.
template <typename C>
auto back(C const& c) {
    using std::begin;
    using std::end;
    return back(begin(c), end(c));
}

static
auto operator<<(std::ostream& out, std::forward_list<int> const& l) -> std::ostream& {
    auto sep = "";

    for (auto&& x : l) {
        out << std::exchange(sep, " ") << x;
    }

    return out;
}

template <typename C, typename I>
struct print {
    C const& container;
    I const& it;
    print(C const& c, I const& i) : container{c}, it{i} {}
    bool valid() const {
        using std::begin;
        using std::end;
        using std::next;
        auto b = begin(container);
        auto e = end(container);
        while(b != e) {
            if (it == b) return true;
            b = next(b);
        }
        return it == e;
    }

    template <typename CC, typename II>
    friend auto operator<<(std::ostream& out, print<CC, II> const& p) -> std::ostream& {
        using std::end;
        assert(p.valid());

        if (end(p.container) == p.it) {
            return out << "(end)";
        }

        return out << *p.it;
    }
};
print(struct allow_ctad_t, struct allow2_ctad_t)->print<void, void>;

int main() {
    std::forward_list<int> const list{1, 2, 3, 4, 5};
    std::cout << list << "\n";
    auto it = back(list);
    std::cout << print(list, it) << "\n";
    std::cout << print(list, list.end()) << "\n";
}

Collectives™ on Stack Overflow

How can I get a forward iterator to the last element?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related