Очистка двунаправленного кода итератора

Question

Я изменил James' flattening iterator, чтобы действовать как двунаправленный итератор, если это возможно, но я не думаю, что мои изменения очень элегантны (особенно полагаясь на bool, чтобы увидеть, установлен ли внутренний итератор). Тем не менее, я не могу придумать лучшего решения. У кого-нибудь есть идеи?

#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

Отличный вопрос и отличная попытка.

Итератор всегда должен ссылаться на действительное значение или на один конец. *iter всегда должен быть действителен, если только iter == end, где end является одним концом. Этот итератор «один-на-конец» является причиной ваших забот. Либо inner_it_ ссылается на действительное значение, либо ваш итератор является одним из прошедших.

Итератор «one-past-end» Джеймса существует, когда outer_it_ == outer_end_, и это ситуация, в которой вы должны проверить. Это только ситуация, в которой inner_it_ должно иметь недопустимое значение. В результате вы можете избавиться от bool и сразу же проверить outer_it_ == outer_end_.

Кроме того, я нахожу эту линию подозреваемый:

inner_it_ = --outer_it_->end(); 

Возможно ли, что outer_it_ является ЬурейиМ к указателю? Если это так, вы не можете позвонить -- по значению указателя. Это, безусловно, работать:

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

и, кроме того, он выражает намерение лучше, потому что первые выглядит как вы декремент самого end() итератора!