Kết hợp hai vectơ STL với một mẫu thay thế

Question

Tôi có hai vector STL A và B và cần hợp nhất chúng thành một phần ba, trong đó các phần tử phải được sắp xếp theo cách, mọi phần tử thứ n trong vectơ đầu ra phải là vector B. mã hiện tại của tôi trông giống như sau:

std::vector<int> a(10, 4); 
std::vector<int> b(10, 8); 
std::vector<int> c; 
static const std::size_t STEP(3); 

std::vector<int>::const_iterator bIt = b.begin(); 
for(std::vector<int>::const_iterator aIt = a.begin(); 
    aIt != a.end(); ++aIt) 
{ 
    c.push_back(*aIt); 
    if((c.size() + 1) % STEP == 0) 
    { 
     c.push_back(*bIt); 
     ++bIt; //assume b is large enough 
    } 
} 

Các vector c bây giờ trông giống như: 4 4 8 4 4 8 ...

này hoạt động tốt, nhưng tôi tò mò nếu có không phải là một giải pháp thanh lịch hơn. Có cách nào sử dụng một thuật toán STL thay vì các vòng viết tay của tôi?

Answer 1

Điều này quá chuyên biệt để được bao phủ trực tiếp bởi <algorithm>. Tránh vòng lặp sẽ yêu cầu một trình vòng lặp tùy chỉnh.

template< typename I1, typename I2 > 
struct interleave_iterator 
    : std::iterator< forward_iterator_tag, typename I1::value_type > { 
    using typename I1::value_type; 

    I1 i1; 
    I2 i2; 
    size_t cnt, stride; 

    interleave_iterator(I1 in1, I2 in2, size_t in_stride=0, size_t in_off=0) 
     : i1(in1), i2(in2), cnt(in_off), stride(in_stride) {} 

    value_type &operator*() const { return cnt? * i1 : * i2; } 
    interleave_iterator &operator++() { 
     if (++ cnt == stride) { 
      cnt = 0; 
      ++ i2; 
     } else ++ i1; 
     return *this; 
    } 
    value_type *operator->() const 
     { return cnt? i1.operator->() : i2.operator->(); } 

    interleave_iterator &operator++(int) 
     { interleave_iterator r = *this; ++ *this; return r; } 

    friend bool operator== 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return lhs.i1 == rhs.i1 && lhs.i2 == rhs.i2; } 
    friend bool operator!= 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return ! (lhs == rhs); } 
}; 

Một chút quá mức, tôi nghĩ vậy.

Answer 2

Tôi phải thừa nhận tôi khá thích giải pháp Potatoswatter ... khá.

Như ông đã chứng minh, đây không phải là vấn đề về thuật toán, mà là sự lặp lại. Tuy nhiên giải pháp của ông không hoàn toàn phù hợp với hóa đơn bởi vì thử nghiệm cho các end của iteration là rất khó khăn: nó đòi hỏi nhiều chăm sóc trong việc chuẩn bị các container và tạo ra các iterators để tránh undefined hành vi.

Tôi nghĩ rằng vấn đề có thể được thể hiện tốt hơn nhiều bằng cách sử dụng một khái niệm khá giống với các trình vòng lặp: các khung nhìn.

Chế độ xem là giao diện Bộ điều hợp trên một hoặc nhiều vùng chứa. Nó không thực sự chứa bất cứ điều gì chính nó (đó là phần quan trọng). Tuy nhiên, nó cho thấy một giao diện tương tự như giao diện của một vùng chứa để bạn có thể mã hóa với các thành ngữ thông thường.

Những điều đẹp về lượt xem, là bạn thường có thể soạn chúng.

Ví dụ, một cái nhìn rất đơn giản:

/// Only allow to see a range of the container: 
/// std::vector<int> v(40, 3); // { 3, 3, 3, ... } 
/// auto rv = make_range_view(v, 4, 5); 
/// rv exposes the elements in the range [4,9) 
/// in debug mode, asserts that the range is sufficiently large 
template <typename Container> 
class range_view 
{ 
}; 

Đối với câu hỏi của bạn, bạn thà tạo ra một interleave_view:

/// Allow to interleave elements of 2 containers each at its own pace 
/// std::vector<int> v(40, 3); 
/// std::set<int> s = /**/; 
/// 
/// auto iv = make_interleave_view(v, 3, s, 1); 
/// Takes 3 elements from v, then 1 from s, then 3 from v, etc... 
template <typename C1, typename C2> 
class interleave_view 
{ 
}; 

Ở đây, vấn đề của iterator cuối cùng là bằng cách nào đó giảm bớt bởi vì chúng tôi biết cả hai thùng chứa và do đó chúng tôi có thể tự tạo ra các trình vòng lặp, đảm bảo chúng tôi chuyển các thông số thích hợp.

Tất nhiên nó có thể trở nên tẻ nhạt hơn một chút nếu các thùng chứa không cung cấp thành viên "kích thước" hiệu quả (list không, đó là O (n)). Tuy nhiên, nguyên tắc chung cho phép bạn kiểm soát nhiều hơn (và cho phép nhiều kiểm tra hơn), và an toàn hơn để sử dụng bởi vì bạn kiểm soát chính xác việc tạo các trình vòng lặp.

Lưu ý rằng trong C++ 0x, interleave_view thường chứa một số chuỗi không bị chặn.