Table of Contents

In this blog post, we’ll write an iterator that works with a vector of vectors. We’ll explore a “manual” version as well as leverage C++20 ranges/views to do the hard work.

The problem statement  

What’s the use case? See this popular interview question (found in DailyCodingProblem: https://www.dailycodingproblem.com/)

Implement a 2D iterator class. It will be initialized with an array of arrays and should implement the following methods: next() : returns the next element in the array of arrays. If there are no more elements, raise an exception. has_next() : returns whether or not the iterator still has elements left. For example, given the input [[1, 2], [3], [], [4, 5, 6]] , calling next() repeatedly should output 1, 2, 3, 4, 5, 6 .

Transforming the problem into C++, we can write the following client code:

int main() {
    std::vector<std::vector<int>> input = {{1, 2}, {3}, {}, {4, 5, 6}};
    TwoDIterator it(input);

    while (it.has_next())
        std::print("{} ", it.next());
}

The case is to implement TwoDIterator.

Initial Version  

The main idea for the iterator is to track the “inner” position as well as the “outer”. When the inner position reaches the end of some inner vector, we need to check if we have more vectors to traverse.

Here’s some basic code:

#include <vector>
#include <stdexcept>
#include <print>

class TwoDIterator {
public:
    using Vec2D = std::vector<std::vector<int>>;

    TwoDIterator(const Vec2D& data) 
    : data_(data), outer_(0), inner_(0) {
        advance_to_next_valid();
    }

    bool has_next() const {
        return outer_ < data_.size();
    }

    int next() {
        if (!has_next()) throw std::out_of_range("No more elements");

        int val = data_[outer_][inner_];
        ++inner_;
        advance_to_next_valid();
        return val;
    }

private:
    void advance_to_next_valid() {
        while (outer_ < data_.size() && inner_ >= data_[outer_].size()) {
            ++outer_;
            inner_ = 0;
        }
    }

    const Vec2D& data_;
    size_t outer_, inner_;
};

int main() {
    std::vector<std::vector<int>> input = {{1, 2}, {3}, {}, {4, 5, 6}};
    TwoDIterator it(input);

    while (it.has_next())
        std::print("{} ", it.next());
}

Play @Compiler Explorer

The key part of this solution is the advance_to_next_valid() function. It checks if we can move further and if there are any more vectors in the outer range.

Applying Ranges and Views from C++20  

While the solution works fine, in C++20, we can leverage ranges and views.

From my previous article (How to join or concat ranges, C++26 - C++ Stories) we know that if we have nested ranges, we can use join view to do the flattening:

#include <iostream>
#include <ranges>
#include <vector>

int main() {
    std::vector<std::vector<int>> nested{{1, 2}, {3}, {}, {4, 5, 6}};
    
    auto flat = nested | std::views::join;

    for (int i : flat)
        std::cout << i << ' ';
}

Run @Compiler Explorer

So the question is how to leverage it in our class? (We want to keep the interface of has_next() and next() as this is our requirement).

Adding C++20 Views to our class  

Conceptually we want to add a join view iterators as a data member to the class TwoDIterator. However, the main issue is that it’s relatively complex to specify the correct type of such data members we cannot write:

class VecVecIt {
    auto flat = nested | std::views::join; // ??
    auto beg_ = flat.begin();  // ??
    auto end_ = flat.end(); // ??
public:
    // ...
};

Let’s try step by step:

  • We cannot use auto for auto-type deduction for data members; we have to specify the exact type. Later we can initialize those data members in constructors.
  • For simplification we can write using Vec2D = std::vector<std::vector<int>>;
  • std::ranges::join_view<Vec2D> doesn’t work as std::vector isn’t a view, and join requires views.

Here’s the Clang compiler error:

<source>:33:35: error: constraints not satisfied for class template 'join_view' [with _Vp = std::vector<std::vector<int>>]
   33 |     using JoinView = std::ranges::join_view<Vec2D>;  
      |                                   ^~~~~~~~~~~~~~~~
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/16.0.0/../../../../include/c++/16.0.0/ranges:2888:14: note: because 'std::vector<std::vector<int>>' does not satisfy 'view'
 2888 |     requires view<_Vp> && input_range<range_reference_t<_Vp>>

To “convert” a vector into a view, we can write:

std::ranges::ref_view<const Vec2D>

Now we can combine the previous steps into:

using Vec2D = std::vector<std::vector<int>>;  
using JoinView = std::ranges::join_view<std::ranges::ref_view<const Vec2D>>;  
using Iterator = std::ranges::iterator_t<JoinView>;

Here’s the final class:

#include <vector>
#include <stdexcept>
#include <print>
#include <ranges>

class TwoDIteratorJoin {  
public:  
    using Vec2D = std::vector<std::vector<int>>;  
    using JoinView = std::ranges::join_view<std::ranges::ref_view<const Vec2D>>;  
    using Iterator = std::ranges::iterator_t<JoinView>;  
  
    explicit TwoDIteratorJoin(const Vec2D& data)  
        : flattened_(data | std::views::join),  
          iter_(flattened_.begin()),  
          end_(flattened_.end()) {}  
  
    [[nodiscard]] bool has_next() const {  
        return iter_ != end_;  
    }  
  
    [[nodiscard]] int next() {  
        if (!has_next()) throw std::out_of_range("No more elements");  
        return *iter_++;  
    }  
  
private:  
    JoinView flattened_;  
    Iterator iter_, end_;  
};

int main() {
    const std::vector<std::vector<int>> input = {{1, 2}, {3}, {}, {4, 5, 6}};
    TwoDIteratorJoin it(input);

    while (it.has_next())
        std::print("{} ", it.next());
}

Run @Compiler Explorer

Summary  

In this article, we explored two approaches to implementing a 2D iterator in C++. The first, a manual solution, required us to carefully manage both outer and inner indices to traverse a vector of vectors. While this approach is straightforward and works well, it can become verbose and error-prone as complexity grows.

With the advent of C++20, ranges and views offer a much more elegant and expressive alternative. By leveraging std::views::join, we can flatten nested containers and iterate over their elements with minimal boilerplate. The main challenge is specifying the correct types for view-based data members, but once addressed, the resulting code is concise, robust, and easy to maintain.

Back To you

  • Do you use Ranges and Views from C++20?
  • Have you ever needed to write a custom iterator?