itertools.tee tương đương với Boost :: Range?

Question

Python của itertools có tee cho iterables n-plicating:

def tee(iterable, n=2): 
    it = iter(iterable) 
    deques = [collections.deque() for i in range(n)] 
    def gen(mydeque): 
     while True: 
      if not mydeque:    # when the local deque is empty 
       newval = next(it)  # fetch a new value and 
       for d in deques:  # load it to all the deques 
        d.append(newval) 
      yield mydeque.popleft() 
    return tuple(gen(d) for d in deques) 

tôi không thể tìm ra tương đương trong Boost::Range. Tôi có thiếu thứ gì đó hay tôi nên tự mình cuộn?

Answer 1

itertools.tee rất phù hợp cho các lần lặp lại một lần có mặt khắp mọi nơi trong Python. Ví dụ Generators là một lần, và chúng thường được sử dụng.

Nhưng nếu bạn đã có danh sách/deque bạn sẽ không sử dụng itertools.tee cho nó, vì nó sẽ liên quan đến trùng lặp thừa - bạn chỉ có thể lặp qua danh sách gốc/deque hơn và hơn nữa.

C++ cũng có khái niệm về phạm vi một lần, ví dụ Input Iterator, nhưng chúng không phổ biến ở mọi nơi. Nó là kết quả của một tập hợp các mục tiêu của chương trình C++ điển hình - cung cấp cho người dùng tối đa nhất có thể duy trì hiệu suất tốt nhất. Đó là một suy nghĩ khác nếu bạn muốn.

Để minh họa điều này chúng ta hãy so sánh boost::transformed và itertools.imap (hoặc generator expressions):

Cả hai đều cung cấp quan điểm của chuỗi đầu vào thông qua trao "lăng kính". itertools.imap lợi nhuận đơn qua iterable, trong khi boost :: biến lợi nhuận dao động xem có cùng chuyên mục như phạm vi đầu vào - ví dụ, nếu bạn muốn vượt qua Random Access Range như là đầu vào bạn sẽ nhận được Random Access Phạm vi như kết quả.

Thực tế khác là C++ sử dụng value semantics theo mặc định, trong khi python có ngữ nghĩa con trỏ. Nó có nghĩa rằng nếu bản sao lặp trong C + +, và "bump" nó nhiều lần - bản gốc iterator sẽ không được thay đổi (mặc dù nó có thể bị vô hiệu nếu nó là duy nhất vượt qua phạm vi, nhưng nó không phải là điểm).

Nhưng, đôi khi bạn muốn tích lũy các giá trị từ phạm vi một lần và xem chúng nhiều lần. Trong trường hợp này, giải pháp phổ biến nhất là tích lũy giá trị cho một số thùng chứa một cách rõ ràng, bằng tay. Ví dụ:

vector<int> cache(first,last); 

---

Tuy nhiên, giấy gói tee-như vẫn còn có thể có trong C++, đây là proof-of-concept. Cách sử dụng:

auto forward_range = tee_range(first,last); 

tee_range mất đơn vượt qua phạm vi như là đối số và trả về phía trước phạm vi (đó là đa-pass) (đó cũng là make_tee_iterator, mà làm việc ở cấp iterator). Vì vậy, bạn có thể mang bản sao của phạm vi đó và lặp nó nhiều lần:

auto r = forward_range; 
auto out = ostream_iterator<int>(cout," "); 
copy(forward_range,out); 
copy(forward_range,out); 
copy(r,out); 

Therer cũng được improvenment qua itertools.tee - trong nội bộ, chỉ có một deque được sử dụng để các giá trị bộ nhớ cache.

live demo:

#include <boost/range/adaptor/transformed.hpp> 
#include <boost/iterator/iterator_facade.hpp> 
#include <boost/smart_ptr/make_shared.hpp> 
#include <boost/range/iterator_range.hpp> 
#include <boost/smart_ptr/shared_ptr.hpp> 
#include <boost/container/vector.hpp> 
#include <boost/container/deque.hpp> 
#include <boost/range/algorithm.hpp> 
#include <algorithm> 
#include <iterator> 
#include <cassert> 
#include <limits> 

template<typename InputIterator> 
class tee_iterator : public boost::iterator_facade 
    < 
     tee_iterator<InputIterator>, 
     const typename std::iterator_traits<InputIterator>::value_type, 
     boost::forward_traversal_tag 
    > 
{ 
    typedef typename std::iterator_traits<InputIterator>::value_type Value; 
    typedef unsigned Index; 
    struct Data 
    { 
     boost::container::deque<Value> values; 
     boost::container::vector<tee_iterator*> iterators; 
     InputIterator current,end; 
     Index min_index, current_index; 
     Index poped_from_front; 
     // 
     Data(InputIterator first,InputIterator last) 
      : current(first), end(last), min_index(0), current_index(0), poped_from_front(0) 
     {} 
     ~Data() 
     { 
      assert(iterators.empty()); 
     } 
    }; 
    boost::shared_ptr<Data> shared_data; 
    Index index; 
    static Index get_index(tee_iterator *p) 
    { 
     return p->index; 
    } 
public: 
    tee_iterator() 
     : index(std::numeric_limits<Index>::max()) 
    {} 
    tee_iterator(InputIterator first,InputIterator last) 
     : shared_data(boost::make_shared<Data>(first,last)), index(0) 
    { 
     shared_data->iterators.push_back(this); 
    } 
    tee_iterator(const tee_iterator &x) 
     : shared_data(x.shared_data), index(x.index) 
    { 
     if(shared_data) 
      shared_data->iterators.push_back(this); 
    } 
    friend void swap(tee_iterator &l,tee_iterator &r) 
    { 
     using std::swap; 
     *boost::find(l.shared_data->iterators,&l) = &r; 
     *boost::find(r.shared_data->iterators,&r) = &l; 
     swap(l.shared_data,r.shared_data); 
     swap(l.index,r.index); 
    } 
    tee_iterator &operator=(tee_iterator x) 
    { 
     swap(x,*this); 
    } 
    ~tee_iterator() 
    { 
     if(shared_data) 
     { 
      erase_from_iterators(); 
      if(!shared_data->iterators.empty()) 
      { 
       using boost::adaptors::transformed; 
       shared_data->min_index = *boost::min_element(shared_data->iterators | transformed(&get_index)); 
       Index to_pop = shared_data->min_index - shared_data->poped_from_front; 
       if(to_pop>0) 
       { 
        shared_data->values.erase(shared_data->values.begin(), shared_data->values.begin()+to_pop); 
        shared_data->poped_from_front += to_pop; 
       } 
      } 
     } 
    } 
private: 
    friend class boost::iterator_core_access; 
    void erase_from_iterators() 
    { 
     shared_data->iterators.erase(boost::find(shared_data->iterators,this)); 
    } 
    bool last_min_index() const 
    { 
     return boost::count 
     (
      shared_data->iterators | boost::adaptors::transformed(&get_index), 
      shared_data->min_index 
     )==1; 
    } 
    Index obtained() const 
    { 
     return Index(shared_data->poped_from_front + shared_data->values.size()); 
    } 
    void increment() 
    { 
     if((shared_data->min_index == index) && last_min_index()) 
     { 
      shared_data->values.pop_front(); 
      ++shared_data->min_index; 
      ++shared_data->poped_from_front; 
     } 
     ++index; 
     if(obtained() <= index) 
     { 
      ++shared_data->current; 
      if(shared_data->current != shared_data->end) 
      { 
       shared_data->values.push_back(*shared_data->current); 
      } 
      else 
      { 
       erase_from_iterators(); 
       index=std::numeric_limits<Index>::max(); 
       shared_data.reset(); 
      } 
     } 
    } 
    bool equal(const tee_iterator& other) const 
    { 
     return (shared_data.get()==other.shared_data.get()) && (index == other.index); 
    } 
    const Value &dereference() const 
    { 
     if((index==0) && (obtained() <= index)) 
     { 
      shared_data->values.push_back(*(shared_data->current)); 
     } 
     assert((index-shared_data->poped_from_front) < shared_data->values.size()); 
     return shared_data->values[index-shared_data->poped_from_front]; 
    } 
}; 

template<typename InputIterator> 
tee_iterator<InputIterator> make_tee_iterator(InputIterator first,InputIterator last) 
{ 
    return tee_iterator<InputIterator>(first,last); 
} 

template<typename InputIterator> 
boost::iterator_range< tee_iterator<InputIterator> > tee_range(InputIterator first,InputIterator last) 
{ 
    return boost::iterator_range< tee_iterator<InputIterator> > 
    (
     tee_iterator<InputIterator>(first,last), 
     tee_iterator<InputIterator>() 
    ); 
} 
// _______________________________________________________ // 

#include <iostream> 
#include <ostream> 
#include <sstream> 

int main() 
{ 
    using namespace std; 
    stringstream ss; 
    ss << "1 2 3 4 5"; 
    istream_iterator<int> first(ss /*cin*/),last; 
    typedef boost::iterator_range< tee_iterator< istream_iterator<int> > > Range; // C++98 
    Range r1 = tee_range(first,last); 
    Range r2 = r1, r3 = r1; 
    boost::copy(r1,ostream_iterator<int>(cout," ")); 
    cout << endl; 
    boost::copy(r2,ostream_iterator<int>(cout," ")); 
    cout << endl; 
    boost::copy(r2,ostream_iterator<int>(cout," ")); 
} 

Output là:

1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 

---

Boost.Spirit có Multi Pass iterator trong đó có mục tiêu tương tự.

Trình lặp vòng lặp đa_thức sẽ chuyển đổi bất kỳ trình lặp đầu vào nào thành trình vòng lặp chuyển tiếp thích hợp để sử dụng với Spirit.Qi. multi_pass sẽ đệm dữ liệu khi cần thiết và sẽ loại bỏ bộ đệm khi nội dung của nó không cần thiết nữa. Điều này xảy ra nếu chỉ có một bản sao của vòng lặp tồn tại hoặc nếu không có backtracking có thể xảy ra.