Cleaning up bidirectional iterator code

Question

I've modified James' flattening iterator to act as a bidirectional iterator if possible, but I don't think my changes are very elegant (particularly relying on a bool to see if the inner iterator has been set). However, I can't seem to come up with a nicer solution. Does anyone have any ideas?

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include <iterator>
#include <type_traits>

// An iterator that "flattens" a container of containers.  For example,
// a vector<vector<int>> containing { { 1, 2, 3 }, { 4, 5, 6 } } is iterated as
// a single range, { 1, 2, 3, 4, 5, 6 }.
template <typename OuterIterator>
class flattening_iterator
{
public:

    typedef OuterIterator outer_iterator;
    typedef typename std::iterator_traits<outer_iterator>::value_type::iterator inner_iterator;

    typedef typename std::iterator_traits<outer_iterator>::iterator_category outer_category;
    typedef typename std::iterator_traits<inner_iterator>::iterator_category inner_category;
    typedef typename std::common_type<outer_category, inner_category>::type common_category;

    typedef typename std::conditional<std::is_same<common_category, std::random_access_iterator_tag>::value,
                                      std::bidirectional_iterator_tag,
                                      common_category>::type iterator_category;

    typedef typename std::iterator_traits<inner_iterator>::value_type value_type;
    typedef typename std::iterator_traits<inner_iterator>::difference_type difference_type;
    typedef typename std::iterator_traits<inner_iterator>::pointer pointer;
    typedef typename std::iterator_traits<inner_iterator>::reference reference;

    flattening_iterator() { }
    flattening_iterator(outer_iterator it, outer_iterator begin, outer_iterator end)
        : outer_it_(it),
          outer_begin_(begin),
          outer_end_(end),
          inner_it_assigned_(false)
    {
        if (outer_begin_ == outer_end_) { return; }

        if (outer_it_ == outer_end_) { return; }

        inner_it_ = outer_it_->begin();
        inner_it_assigned_ = true;
        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;
    }

    flattening_iterator& operator--()
    {
        if(!inner_it_assigned_)
        {
            if(outer_begin_ != outer_end_)
            {
                decrement_through_empty_inner_containers();
            }

            return *this;
        }

        if(inner_it_ == outer_it_->begin())
        {
            decrement_through_empty_inner_containers();
        }
        else
        {
            --inner_it_;
        }

        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_assigned_ == false &&
           b.inner_it_assigned_ == false)
           return true;

        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();
        }
    }

    void decrement_through_empty_inner_containers()
    {
        --outer_it_;
        while(outer_it_ != outer_begin_ && outer_it_->begin() == outer_it_->end())
        {
            --outer_it_;
        }   

        if(outer_it_->begin() != outer_it_->end())
        {
            inner_it_ = --outer_it_->end();
            inner_it_assigned_ = true;
        }
    }

    outer_iterator outer_it_;
    outer_iterator outer_begin_;
    outer_iterator outer_end_;
    inner_iterator inner_it_;
    bool inner_it_assigned_;
};

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

template <typename Iterator>
std::reverse_iterator<flattening_iterator<Iterator>> flatten_reverse(Iterator start, Iterator first, Iterator last)
{
    return std::reverse_iterator<flattening_iterator<Iterator>>(flatten(start, first, last));
}

int main()
{
    std::vector<std::vector<int>> v(3);
    int i(0);

    for (auto it(v.begin()); it != v.end(); ++it)
    {
        it->push_back(i++); it->push_back(i++);
        it->push_back(i++); it->push_back(i++);
    }

    v.insert(v.begin(), std::vector<int>());
    v.insert(v.begin(), std::vector<int>());
    v.insert(v.begin() + 4, std::vector<int>());
    v.push_back(std::vector<int>());
    v.push_back(std::vector<int>());

    for (auto it(flatten(v.begin(), v.begin(), v.end())), end = flatten(v.end(), v.begin(), v.end());
        it != end;
        ++it)
    {
        std::cout << *it << ", ";
    }
    std::cout << "\n";

    for (auto it(flatten_reverse(v.end(), v.begin(), v.end())), end = flatten_reverse(v.begin(), v.begin(), v.end());
        it != end;
        ++it)
    {
        std::cout << *it << ", ";
    }
    std::cout << "\n";

    std::vector<std::vector<int>> v2;
    for (auto it(flatten(v2.end(), v2.begin(), v2.end())), end = flatten(v2.begin(), v2.begin(), v2.end());
        it != end;
        --it)
    {
        std::cout << *it << ", ";
    }
    std::cout << "\n";
}

Answer 1

Great question, and great attempt.

An iterator should always refer to a valid value, or one-past-the-end. *iter should always be valid unless iter == end where end is one-past-the-end. That "one-past-the-end" iterator is the cause of your worries. Either inner_it_ refers to a valid value, or your iterator is one-past-the-end.

James's "one-past-the-end" iterator exists when outer_it_ == outer_end_, and this is the situation you need to check for. This is the only situation in which inner_it_ should have an invalid value. As a result, you can get rid of the bool and just directly check outer_it_ == outer_end_.

Also, I find this line suspect:

inner_it_ = --outer_it_->end();

Is it possible that outer_it_ is a typedef to a pointer? If so, you can't call -- on a pointer value. This will definitely work:

inner_it_ = outer_it_->end();
--inner_it_;

and moreover, it conveys intent better, because the first looks like you're decrementing the end() iterator itself!