"end()" iterator cho bộ chèn lại?

Question

Đối với các trình vòng lặp như các trình lặp lại được trả về từ std::back_inserter(), có điều gì có thể được sử dụng làm trình lặp "kết thúc" không?

Điều này có vẻ một chút vô nghĩa lúc đầu, nhưng tôi có một API đó là:

template<typename InputIterator, typename OutputIterator> 
void foo(
    InputIterator input_begin, 
    InputIterator input_end, 
    OutputIterator output_begin, 
    OutputIterator output_end 
); 

foo thực hiện một số hoạt động trên các chuỗi đầu vào, tạo ra một chuỗi đầu ra. (Độ dài của ai được biết là foo nhưng có thể hoặc không thể bằng với chiều dài của chuỗi đầu vào.)

Tham số output_end là phần lẻ: std::copy không làm điều này, ví dụ, và giả sử bạn ' sẽ không vượt qua nó rác. foo hiện nó để cung cấp kiểm tra phạm vi: nếu bạn vượt qua một phạm vi quá nhỏ, nó ném một ngoại lệ, trong tên của chương trình phòng thủ. (Thay vì có khả năng ghi đè các bit ngẫu nhiên trong bộ nhớ.)

Bây giờ, nói rằng tôi muốn vượt qua foo một trình rút gọn trở lại, cụ thể là từ số std::vector không có giới hạn nào ngoài giới hạn bộ nhớ. Tôi vẫn cần một bộ lặp "kết thúc" - trong trường hợp này, cái gì đó sẽ không bao giờ so sánh bằng nhau. (Hoặc, nếu tôi có một số std::vector nhưng có giới hạn về chiều dài, có lẽ đôi khi nó có thể so sánh bằng nhau?)

Làm cách nào để tôi thực hiện việc này? Tôi có khả năng thay đổi API của foo - tốt hơn là không kiểm tra phạm vi và thay vào đó cung cấp phương tiện thay thế để có được phạm vi đầu ra được yêu cầu? (Mà sẽ là cần thiết anyways cho mảng thô, nhưng không cần thiết cho trở lại chèn vào một vector.) Điều này có vẻ ít mạnh mẽ, nhưng tôi đang đấu tranh để làm cho "mạnh mẽ" (ở trên) làm việc.

Answer 1

Nếu foo đang kiểm tra để đảm bảo rằng distance(output_begin, output_end) đủ lớn để chứa kết quả, bạn có thể sử dụng gì làm trình lặp "kết thúc"? A back_inserter thêm các phần tử vào cuối; các distance giữa vị trí mà tại đó back_inserter thêm phần tử và kết thúc chuỗi theo định nghĩa, 0.

A foo với std::copy giống như chữ ký foo(InIt, InIt, OutIt), theo ý kiến ​​của tôi, lựa chọn tốt nhất của bạn. Nó không thực sự "không mạnh mẽ". Đối với hầu hết các thuật toán, bạn chỉ muốn thực hiện việc kiểm tra phạm vi này trong các bản dựng gỡ lỗi vì lý do hiệu năng và việc thực hiện Thư viện chuẩn chuẩn (như Thư viện chuẩn Visual C++) đã cung cấp rất nhiều kiểm tra trong các bản dựng gỡ lỗi. Ngoài ra, bạn có thể tạo ra một back_inserting_foo(InIt, InIt, Container), mặc dù việc tạo một trường hợp đặc biệt cho điều này sẽ hơi khác thường và đặt gánh nặng lớn hơn cho người dùng của hàm để biết họ cần sử dụng quá tải nào cho các loại trình lặp khác nhau.

Answer 2

Bạn có thể tránh thay đổi foo() 's API bằng cách thực hiện việc kiểm tra an toàn khi bạn đi, bằng cách kiểm tra rằng curr_output_iter != output_end trước mỗi phần tử được viết ra (xem dưới đây), thay vì một lần vào lúc bắt đầu với một tấm séc distance() như James McNellis suggests.

Thực hiện việc này sẽ yêu cầu viết "bộ điều hợp lặp" của riêng bạn để cung cấp bộ lặp đầu ra "nâng cao" có thể kiểm tra xem nó có ở cuối phạm vi hợp lệ của nó hay không. Sau đó, bạn sẽ thay đổi đúng kiểu tên mẫu từ OutputIterator thành SafeOutputIterator - mặc dù điều này chỉ đóng vai trò là tài liệu vì đó là thứ không thể được thực thi trong C++.Chúng ta phân biệt giữa các cặp lặp "bounded" và "unbounded": sau này, không có hai trình vòng lặp nào so sánh bằng nhau, và trên thực tế trình lặp thứ hai sẽ không bao giờ cần thiết cho bất kỳ thứ gì ngoài loại của nó.

/* Metafunction for determining whether the range has a fixed endpoint. 
* Assume all iterators are bounded except for OutputIterators. */ 
template <typename Tag> 
struct helper { 
    static bool value = true; 
}; 

template <> 
struct helper<output_iterator_tag> { 
    static bool value = false; 
}; 

template <typename It> 
struct is_bounded { 
    static bool value = helper<typename iterator_traits<It>::iterator_category>::value; 
}; 

/* Wraps an output iterator. */ 
template<typename It, bool BOUNDED = is_bounded<It>::value> 
class safe_output_iterator { 
    typedef typename iterator_traits<It>::value_type value_type; 

public: 
    explicit safe_output_iterator(It iter, size_t limit = 0) : iter_(iter), limit_(limit) {} 

    safe_output_iterator& operator++() { /* Preinc */ 
     ++iter_; 
     return *this; 
    } 

    safe_output_iterator operator++(int) { /* Postinc */ 
     safe_output_iterator temp(*this); 
     ++iter_; 
     return temp; 
    } 

    /* Trick: Deferencing returns the same object, so that operator=() works */ 
    safe_output_iterator& operator*() { 
     return *this; 
    } 

    /* Will be called despite "dereferencing" this iterator object */ 
    safe_output_iterator& operator=() { 
     /* Insert check for limit == 0 here if you want */ 
     --limit_; 
     return *_iter; 
    } 

    /* Addition to the OutputIterator concept. */ 
    bool operator==(safe_output_iterator const& x) { 
     return BOUNDED && limit_ == x.limit_; 
    } 

    bool operator!=(safe_output_iterator const& x) { 
     return !(*this == x); 
    } 

private: 
    It iter_; 
    size_t limit_; 
}; 

/* Helper function templates to avoid typing out long typenames */ 

/* Handle iterators */ 
template <typename It> 
safe_output_iterator<It> soi_begin(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

template <typename It> 
safe_output_iterator<It> soi_end(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

/* Handle STL containers like vector and list */ 
template <typename C> 
safe_output_iterator<It> soi_begin_cont(C cont) { 
    return safe_output_iterator<typename C::iterator>(cont.begin(), cont.size()); 
} 

template <typename C> 
safe_output_iterator<It> soi_end_cont(C cont) { 
    /* Actually the iterator supplied (here cont.end()) is unimportant... */ 
    return safe_output_iterator<typename C::iterator>(cont.end()); 
} 

Bây giờ bạn có thể viết mã như:

vector<int> u(10, 42), v(ENOUGH_SPACE), w, x(ENOUGH_SPACE); 

// Explicit iterator pair; bounded 
foo(u.begin(), u.end(), soi_begin(v.begin(), ENOUGH_SPACE), soi_end(v)); 

// Explicit iterator pair; unbounded (2nd iterator ignored, but we need the type) 
foo(u.begin(), u.end(), soi_begin(w.back_inserter()), soi_end(w.back_inserter())); 

// Use whole container 
foo(u.begin(), u.end(), soi_begin_cont(x), soi_end_cont(x)); 

Bạn có thể có foo() séc curr_output_iter != output_end trước mỗi viết qua *curr_output_iter, hoặc cách khác chèn dấu check ở mục safe_output_iterator::operator=(). Sau này có vẻ thích hợp hơn khi bạn không thể thực hiện kiểm tra bất cứ khi nào một cặp safe_output_iterator s được chuyển cho bất kỳ thuật toán tùy ý nào (có lẽ điều này tương tự như cách các phiên bản gỡ lỗi của tác phẩm STL). Bạn cũng có thể viết các tình trạng quá tải của soi_begin_cont() và soi_end_cont() cho các mảng có kích thước cố định.

Tất cả điều này sẽ ít phức tạp hơn nếu ranges được sử dụng bởi các thuật toán STL thay vì các cặp lặp - theo cách đó, một mẫu hàm có thể trả về một phạm vi thích hợp trải rộng toàn bộ mảng.

Answer 3

Như tôi đã đề cập trong một chú thích cho câu trả lời j_random_hacker, nếu bạn sửa đổi các thuật toán như vậy mà lặp được truyền cho nó có thể được các loại khác nhau, ví dụ,

template <typename InIt1, InIt2, OutIt1, OutIt2> 
void foo(InIt1 in_begin, InIt2 in_end, OutIt1 out_begin, OutIt2 out_end) { } 

sau đó bạn có thể dễ dàng viết một back_inserter_end lớp để kiểm tra chống lại:

class back_inserter_end 
    : std::iterator<std::output_iterator_tag, void> 
{ }; 

bool operator==(back_inserter_end, back_inserter_end) { return true; } 
bool operator!=(back_inserter_end, back_inserter_end) { return false; } 

template <typename Container> 
bool operator==(const back_insert_iterator<Container>&, back_inserter_end) { 
    return false; 
} 

template <typename Container> 
bool operator==(back_inserter_end, const back_insert_iterator<Container>&) { 
    return false; 
} 

template <typename Container> 
bool operator!=(const back_insert_iterator<Container>&, back_inserter_end) { 
    return true; 
} 

template <typename Container> 
bool operator!=(back_inserter_end, const back_insert_iterator<Container>&) { 
    return true; 
} 

sau đó bạn có thể gọi bạn "an toàn" thuật toán:

foo(it, it, std::back_inserter(v), back_inserter_end()); 

Bên trong thuật toán "an toàn" của bạn, bạn có thể kiểm tra xem out_it == out_end trước khi sử dụng out_it hay chưa; kể từ out_it là back_insert_iterator, kiểm tra này sẽ luôn trả lại false (đó là hành vi mong muốn).