Chia thùng chứa thành các khối, C++

Question

Cho một vector của N các phần tử v = (1, 2, 3, 4, ... , N) trình lặp lại phạm vi trả về trên tất cả các khối có kích thước K<N. Phạm vi cuối cùng có thể nhỏ hơn K nếu N%K!=0.

Ví dụ:

v = ("a","b","c","d","e") 

hiển thị chuỗi

"ab", "cd", "e" 

N=v.size(); 
K=2; 

Một giải pháp khả thi là:

for(unsigned int i=0; i<v.size(); i+=K) 
    cout << boost::join(v | boost::adaptors::sliced(i, min(i+K, v.size())), ""); 

Giải pháp này là khá ok nhưng nó có một số vấn đề:

1. for vòng lặp - có cần thiết không?
2. nếu bạn viết i+K thay vì min(i+K, v.size()) thuật toán bị nghiền nát, bạn cần chú ý thêm đến trường hợp biên. Điều này có vẻ xấu xí và phân tâm.

Bạn có thể đề xuất giải pháp thanh lịch hơn không? Bởi giải pháp thanh lịch, tôi có nghĩa là việc sử dụng một thuật toán chung, xây dựng trong hoặc được cung cấp bởi thư viện thường được sử dụng (chẳng hạn như tăng).

-------------------------- [edit] ----------------- ---------

Một số trong số các bạn đã làm ví dụ làm việc ở đây.

#include <iostream> 
#include <vector> 
#include <string> 
#include <boost/range/adaptor/sliced.hpp> 
#include <boost/algorithm/string/join.hpp> 
#include <boost/assign.hpp> //just for fun 

using namespace std; 
using namespace boost::assign; 

int main(int , char **) 
{ 
    const int K = 2; 
    vector<string> v; 
    v += "a","b","c","d","e"; 

    for(unsigned int i=0; i<v.size(); i+=K) 
     cout << boost::algorithm::join( 
        v | boost::adaptors::sliced(i, min(i+K, v.size())), "") 
      << endl; 
} 

Output:

ab 
cd 
e 

Answer 1

Đây là một loại-of-generic giải pháp với hiệu suất tốt:

template <class T, class Func> 
void do_chunks(T container, size_t K, Func func) { 
    size_t size = container.size(); 
    size_t i = 0; 

    // do we have more than one chunk? 
    if (size > K) { 
     // handle all but the last chunk 
     for (; i < size - K; i += K) { 
      func(container, i, i + K); 
     } 
    } 

    // if we still have a part of a chunk left, handle it 
    if (i % K) { 
     func(container, i, i + i % K); 
    } 
} 

Answer 2

Tôi không biết nếu đó là rất thanh lịch, nhưng bạn có thể sử dụng trình lặp có chức năng chuẩn trước và khoảng cách:

template<typename Iterator, typename Func, typename Distance> 
void chunks(Iterator begin, Iterator end, Distance k ,Func f){ 
    Iterator chunk_begin; 
    Iterator chunk_end; 
    chunk_end = chunk_begin = begin; 

    do{ 
     if(std::distance(chunk_end, end) < k) 
      chunk_end = end; 
     else 
      std::advance(chunk_end, k); 
     f(chunk_begin,chunk_end); 
     chunk_begin = chunk_end; 
    }while(std::distance(chunk_begin,end) > 0); 
} 

Answer 3

WRT "Đối với vòng lặp là cần thiết?"

Cấu trúc vòng lặp là cần thiết nếu bạn muốn tránh sử dụng std::distance() vì người dùng cần theo dõi số tiền còn lại. (Đối với container truy cập ngẫu nhiên, std::distance() là rẻ --but cho tất cả những người khác nó là quá tốn kém cho thuật toán này.)

WRT i + K/min() vấn đề

Đừng viết i + K hoặc bất kỳ thứ gì có thể gây ra các vấn đề về gói/tràn/tràn. Thay vào đó theo dõi số tiền còn lại và trừ đi. Điều này sẽ yêu cầu sử dụng min().

WRT giải pháp thanh lịch

thuật toán này là nhiều hơn "thanh lịch" ở chỗ:

1. Hai "WRT" mục đầu tiên ở trên không phải là vấn đề.
2. Nó không sử dụng bất kỳ thư viện bên ngoài nào; - nó chỉ sử dụng std::copy_n() và std::advance().
3. Nó khai thác tra cứu phụ thuộc vào đối số nếu cần thiết/mong muốn.
4. Sử dụng vùng chứa size_type của vùng chứa.
5. Nó sẽ hoạt động hiệu quả với bất kỳ vùng chứa nào.
6. Nếu K < = 0 thì std::domain_error bị ném.

Giải pháp là C++ 11 mặc dù nó có thể dễ dàng được chuyển đổi thành C++ 98 nếu bạn cũng viết copy_n().

#include <vector> 
#include <string> 
#include <sstream> 
#include <iterator> 
#include <iostream> 
#include <stdexcept> 
#include <algorithm> 

template < 
    typename Container, 
    typename OutIter, 
    typename ChunkSepFunctor 
> 
OutIter chunker(
    Container const& c, 
    typename Container::size_type const& k, 
    OutIter o, 
    ChunkSepFunctor sep 
) 
{ 
    using namespace std; 

    if (k <= 0) 
    throw domain_error("chunker() requires k > 0"); 

    auto chunkBeg = begin(c); 
    for (auto left=c.size(); left != 0;) 
    { 
    auto const skip = min(left,k); 

    o = copy_n(chunkBeg, skip, o); 

    left -= skip; 
    advance(chunkBeg, skip); 

    if (left != 0) 
     sep(); 
    } 
    return o; 
} 

int main() 
{ 
    using namespace std; 

    using VECTOR = vector<string>; 
    VECTOR v{"a","b","c","d","e"}; 

    for (VECTOR::size_type k = 1; k < 7; ++k) 
    { 
    cout << "k = " << k << "..." << endl; 
    chunker(
     v, k, 
     ostream_iterator<VECTOR::value_type>(cout), 
     []() { cout << endl; } 
    ); 
    } 
    cout << endl; 
} 

EDIT: Sẽ tốt hơn để viết chunker() để các sep functor nhận được iterator đầu ra và trả về một iterator đầu ra. Bằng cách này, bất kỳ cập nhật nào giữa các khối xuất ra liên quan đến trình vòng lặp đầu ra có thể được xử lý một cách chính xác và thường trình linh hoạt hơn rất nhiều. (Ví dụ, điều này sẽ cho phép functor nhớ vị trí cuối của mỗi đoạn, functor để sao chép các khối, làm trống vùng chứa và đặt lại trình lặp đầu ra; vv) Nếu điều này là không mong muốn, thì giống như Thư viện chuẩn có thể có nhiều hơn một tình trạng quá tải với các yêu cầu khác nhau sep, hoặc loại bỏ hoàn toàn đối số. Đây được cập nhật chunker() trông như thế này:

template < 
    typename Container, 
    typename OutIter, 
    typename ChunkSepFunctor 
> 
OutIter chunker(
    Container const& c, 
    typename Container::size_type const& k, 
    OutIter o, 
    ChunkSepFunctor sep 
) 
{ 
    using namespace std; 

    if (k <= 0) 
    throw domain_error("chunker() requires k > 0"); 

    auto chunkBeg = begin(c); 
    for (auto left=c.size(); left != 0;) 
    { 
    auto const skip = min(left,k); 

    o = copy_n(chunkBeg, skip, o); 

    advance(chunkBeg, skip); 
    left -= skip; 

    if (left != 0) 
     o = sep(o); 
    } 
    return o; 
} 

và cuộc gọi đến đoạn sẽ là ít khá nhưng nhìn chung có ích hơn (mặc dù không phải trong trường hợp này):

chunker(
    v, k, 
    ostream_iterator<VECTOR::value_type>(cout), 
    [](ostream_iterator<VECTOR::value_type> o) { cout << endl; return o; } 
); 

này đã bật ra được một một thói quen nhỏ thanh lịch đáng ngạc nhiên.

Answer 4

tôi chút sửa đổi anwser bởi @BenjaminB và thêm một ví dụ của việc sử dụng chức năng này:

#include <iostream> 
#include <vector> 

using namespace std; 

template<typename Iterator, typename Func> 
void chunks(Iterator begin, 
      Iterator end, 
      iterator_traits<string::iterator>::difference_type k, 
      Func f) 
{ 
    Iterator chunk_begin; 
    Iterator chunk_end; 
    chunk_end = chunk_begin = begin; 

    do 
    { 
     if(std::distance(chunk_end, end) < k) 
      chunk_end = end; 
     else 
      std::advance(chunk_end, k); 
     f(chunk_begin,chunk_end); 
     chunk_begin = chunk_end; 
    } 
    while(std::distance(chunk_begin,end) > 0); 
} 

int main() { 
    string in_str{"123123123"}; 

    vector<string> output_chunks; 

    auto f = [&](string::iterator &b, string::iterator &e) 
    { 
     output_chunks.emplace_back(b, e); 
    }; 

    chunks(in_str.begin(), in_str.end(), 3, f); 

    for (string a_chunk: output_chunks) 
    { 
     cout << a_chunk << endl; 
    } 

    return 0; 
} 

Kết quả là:

123 
123 
123 

Hope ai đó sẽ tìm thấy nó hữu ích.