How Can I Create a Flattening Iterator in C to Simplify Iteration Over Nested Containers?

Flattening Iterators in C

Conventional iterators navigate through the elements of a single container, but sometimes we encounter nested containers, where each element in the outer container represents a separate collection. To traverse all elements sequentially, we need a mechanism to "flatten" the nested structure.

This is where flattening iterators come into play. They seamlessly combine multiple levels of containers, presenting them as a single cohesive sequence. One can iterate over the flattened elements using a standard range-based loop, as if they were all contained in a singular container.

Implementation

While there isn't a built-in implementation in major C libraries, an example implementation can be crafted:

#include <iterator>

template <typename OuterIterator>
class flattening_iterator {
public:
    using outer_iterator = OuterIterator;
    using inner_iterator = typename OuterIterator::value_type::iterator;

    using iterator_category = std::forward_iterator_tag;
    using value_type = typename inner_iterator::value_type;

    flattening_iterator() {}
    flattening_iterator(outer_iterator it) : outer_it_(it), outer_end_(it) {}
    flattening_iterator(outer_iterator it, outer_iterator end)
        : outer_it_(it), outer_end_(end) {
        if (outer_it_ == outer_end_) return;
        inner_it_ = outer_it_->begin();
        advance_past_empty_inner_containers();
    }

    reference operator*() const { return *inner_it_; }
    pointer operator->() const { return &*inner_it_; }

    flattening_iterator& operator++() {
        ++inner_it_;
        if (inner_it_ == outer_it_->end()) advance_past_empty_inner_containers();
        return *this;
    }

    flattening_iterator operator++(int) {
        flattening_iterator it(*this);
        ++*this;
        return it;
    }

    friend bool operator==(const flattening_iterator& a, const flattening_iterator& b) {
        if (a.outer_it_ != b.outer_it_) return false;
        if (a.outer_it_ != a.outer_end_ && b.outer_it_ != b.outer_end_ &&
            a.inner_it_ != b.inner_it_)
            return false;
        return true;
    }

    friend bool operator!=(const flattening_iterator& a, const flattening_iterator& b) {
        return !(a == b);
    }

private:
    void advance_past_empty_inner_containers() {
        while (outer_it_ != outer_end_ && inner_it_ == outer_it_->end()) {
            ++outer_it_;
            if (outer_it_ != outer_end_) inner_it_ = outer_it_->begin();
        }
    }

    outer_iterator outer_it_;
    outer_iterator outer_end_;
    inner_iterator inner_it_;
};

To use this flattening iterator, we can leverage the flatten function template:

template <typename Iterator>
flattening_iterator<Iterator> flatten(Iterator it) {
    return flattening_iterator<Iterator>(it, it);
}

template <typename Iterator>
flattening_iterator<Iterator> flatten(Iterator first, Iterator last) {
    return flattening_iterator<Iterator>(first, last);
}

Example Usage

Consider this nested container:

std::unordered_set<std::vector<int>> s;
s.insert(std::vector<int>());
s.insert({ 1, 2, 3, 4, 5 });
s.insert({ 6, 7, 8 });
s.insert({ 9, 10, 11, 12 });

By utilizing the flattening iterator, we can seamlessly iterate over all the numbers:

for (auto it(flatten(s.begin(), s.end())); it != s.end(); ++it) {
    std::cout << *it << endl;  // prints 1, 2, 3, ..., 12
}

Conclusion

Flattening iterators provide an efficient and elegant method to traverse nested containers in a linear fashion. This approach eliminates the need for complex nested loops or manual index management. While not part of the standard library, this implementation can be readily incorporated into your codebase to enhance flexibility and improve readability.

The above is the detailed content of How Can I Create a Flattening Iterator in C to Simplify Iteration Over Nested Containers?. For more information, please follow other related articles on the PHP Chinese website!