清理双向迭代器代码

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_指的是一个有效的值，或者你的迭代器是一个过去的结尾。

当存在outer_it_ == outer_end_时，存在James的“一过性”迭代器，这是您需要检查的情况。这是只有inner_it_应该有一个无效值的情况。因此，您可以摆脱bool，并直接检查outer_it_ == outer_end_。

而且，我觉得这行嫌疑人：

inner_it_ = --outer_it_->end(); 

难道outer_it_是一个typedef的指针？如果是这样，你不能在指针值上调用--。这肯定会工作：

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

而且，它传达的意图比较好，因为第一个看起来像你递减end()迭代器本身！