Lặp lại làm phẳng

Question

Có bất kỳ trình thực hiện vòng lặp hiện có nào (có lẽ trong tăng cường) thực hiện một số loại trình lặp làm phẳng không?

Ví dụ:

unordered_set<vector<int> > s; 

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

flattening_iterator<unordered_set<vector<int> >::iterator> it(...), end(...); 
for(; it != end; ++it) 
{ 
    cout << *it << endl; 
} 
//would print the numbers 1 through 12 

Answer 1

Tôi không biết về bất kỳ thực hiện trong một thư viện lớn, nhưng nó trông giống như một vấn đề thú vị vì vậy tôi đã viết một thực hiện cơ bản. Tôi đã chỉ thử nghiệm nó với các trường hợp thử nghiệm tôi trình bày ở đây, vì vậy tôi không khuyên bạn nên sử dụng nó mà không cần thử nghiệm thêm.

Vấn đề phức tạp hơn một chút vì có vẻ như một số vùng chứa "bên trong" có thể trống và bạn phải bỏ qua chúng. Điều này có nghĩa rằng việc nâng cấp flattening_iterator bởi một vị trí có thể thực sự đẩy trình vòng lặp vào vùng chứa "bên ngoài" bởi nhiều vị trí. Bởi vì điều này, các flattening_iterator cần phải biết nơi kết thúc của phạm vi bên ngoài là để nó biết khi nó cần phải dừng lại.

Triển khai này là trình lặp chuyển tiếp. Một iterator hai chiều cũng sẽ cần phải theo dõi sự khởi đầu của phạm vi bên ngoài. Các mẫu chức năng flatten được sử dụng để làm cho việc xây dựng flattening_iterator s dễ dàng hơn một chút.

#include <iterator> 

// A forward 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 OuterIterator::value_type::iterator inner_iterator; 

    typedef std::forward_iterator_tag    iterator_category; 
    typedef typename inner_iterator::value_type  value_type; 
    typedef typename inner_iterator::difference_type difference_type; 
    typedef typename inner_iterator::pointer   pointer; 
    typedef typename inner_iterator::reference  reference; 

    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_; 
}; 

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

Sau đây là một thử nghiệm sơ khai tối thiểu:

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

int main() 
{ 
    // Generate some test data: it looks like this: 
    // { { 0, 1, 2, 3 }, { 4, 5, 6, 7 }, { 8, 9, 10, 11 } } 
    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++); 
    } 

    // Flatten the data and print all the elements: 
    for (auto it(flatten(v.begin(), v.end())); it != v.end(); ++it) 
    { 
     std::cout << *it << ", "; 
    } 
    std::cout << "\n"; 

    // Or, since the standard library algorithms are awesome: 
    std::copy(flatten(v.begin(), v.end()), flatten(v.end()), 
       std::ostream_iterator<int>(std::cout, ", ")); 
} 

Như tôi đã nói ngay từ đầu, tôi đã không kiểm tra này triệt để. Hãy cho tôi biết nếu bạn tìm thấy bất kỳ lỗi nào và tôi sẽ vui lòng sửa chúng.

Answer 2

bạn có thể làm một cách sử dụng iterator mặt tiền trong thúc đẩy.

tôi đã viết sản phẩm iterator mà bạn có thể sử dụng làm mẫu lẽ: http://code.google.com/p/asadchev/source/browse/trunk/work/cxx/iterator/product.hpp

Answer 3

Tôi quyết định "cải thiện" một chút về khái niệm lặp làm phẳng, mặc dù như ghi chú của James bạn đang mắc kẹt bằng cách sử dụng Ranges (ngoại trừ phần chứa bên trong), vì vậy tôi chỉ sử dụng phạm vi và thông qua phạm vi được làm phẳng, với độ sâu tùy ý.

Trước tiên tôi sử dụng một viên gạch xây dựng:

template <typename C> 
struct iterator { using type = typename C::iterator; }; 

template <typename C> 
struct iterator<C const> { using type = typename C::const_iterator; }; 

Và sau đó được xác định một (rất ít) ForwardRange khái niệm:

template <typename C> 
class ForwardRange { 
    using Iter = typename iterator<C>::type; 
public: 
    using pointer = typename std::iterator_traits<Iter>::pointer; 
    using reference = typename std::iterator_traits<Iter>::reference; 
    using value_type = typename std::iterator_traits<Iter>::value_type; 

    ForwardRange(): _begin(), _end() {} 

    explicit ForwardRange(C& c): _begin(begin(c)), _end(end(c)) {} 

    // Observers 
    explicit operator bool() const { return _begin != _end; } 

    reference operator*() const { assert(*this); return *_begin; } 
    pointer operator->() const { assert(*this); return &*_begin; } 

    // Modifiers 
    ForwardRange& operator++() { assert(*this); ++_begin; return *this; } 
    ForwardRange operator++(int) { ForwardRange tmp(*this); ++*this; return tmp; } 

private: 
    Iter _begin; 
    Iter _end; 
}; // class ForwardRange 

Đây là gạch xây dựng của chúng tôi ở đây, mặc dù trên thực tế chúng ta có thể làm gì chỉ với phần còn lại:

template <typename C, size_t N> 
class FlattenedForwardRange { 
    using Iter = typename iterator<C>::type; 
    using Inner = FlattenedForwardRange<typename std::iterator_traits<Iter>::value_type, N-1>; 
public: 
    using pointer = typename Inner::pointer; 
    using reference = typename Inner::reference; 
    using value_type = typename Inner::value_type; 

    FlattenedForwardRange(): _outer(), _inner() {} 

    explicit FlattenedForwardRange(C& outer): _outer(outer), _inner() { 
     if (not _outer) { return; } 
     _inner = Inner{*_outer}; 
     this->advance(); 
    } 

    // Observers 
    explicit operator bool() const { return static_cast<bool>(_outer); } 

    reference operator*() const { assert(*this); return *_inner; } 
    pointer operator->() const { assert(*this); return _inner.operator->(); } 

    // Modifiers 
    FlattenedForwardRange& operator++() { ++_inner; this->advance(); return *this; } 
    FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; } 

private: 
    void advance() { 
     if (_inner) { return; } 

     for (++_outer; _outer; ++_outer) { 
      _inner = Inner{*_outer}; 
      if (_inner) { return; } 
     } 
     _inner = Inner{}; 
    } 

    ForwardRange<C> _outer; 
    Inner _inner; 
}; // class FlattenedForwardRange 

template <typename C> 
class FlattenedForwardRange<C, 0> { 
    using Iter = typename iterator<C>::type; 
public: 
    using pointer = typename std::iterator_traits<Iter>::pointer; 
    using reference = typename std::iterator_traits<Iter>::reference; 
    using value_type = typename std::iterator_traits<Iter>::value_type; 

    FlattenedForwardRange(): _range() {} 

    explicit FlattenedForwardRange(C& c): _range(c) {} 

    // Observers 
    explicit operator bool() const { return static_cast<bool>(_range); } 

    reference operator*() const { return *_range; } 
    pointer operator->() const { return _range.operator->(); } 

    // Modifiers 
    FlattenedForwardRange& operator++() { ++_range; return *this; } 
    FlattenedForwardRange operator++(int) { FlattenedForwardRange tmp(*this); ++*this; return tmp; } 

private: 
    ForwardRange<C> _range; 
}; // class FlattenedForwardRange 

Và rõ ràng, it works

Answer 4

Tôi đến trễ một chút ở đây, nhưng tôi vừa xuất bản a library (multidim) để giải quyết vấn đề đó. Cách sử dụng khá đơn giản: để sử dụng ví dụ của bạn,

#include "multidim.hpp" 

// ... create "s" as in your example ... 

auto view = multidim::makeFlatView(s); 
// view offers now a flattened view on s 

// You can now use iterators... 
for (auto it = begin(view); it != end(view); ++it) cout << *it << endl; 

// or a simple range-for loop 
for (auto value : view) cout << value; 

Thư viện chỉ có tiêu đề và không phụ thuộc. Yêu cầu C++ 11 mặc dù.