"end()" итератор для вставных вставок?

Question

Для итераторов, таких как те, которые были возвращены с std::back_inserter(), есть ли что-то, что можно использовать как итератор «end»?

Это кажется немного бессмысленным сначала, но у меня есть API, который:

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

foo выполняет некоторую операцию на входной последовательности, генерирует выходную последовательность. (Длина Кто сейчас известно foo, но может или не может быть равна длине входной последовательности в.)

Изъятие параметра output_end нечетная часть: std::copy не делает этого, к примеру, и предполагает, что вы» не собираюсь передавать ему мусор. foo делает это для проверки диапазона: если вы передаете диапазон слишком малым, он выдает исключение во имя защитного программирования. (Вместо потенциальной перезаписи случайных бит в памяти.)

Теперь, скажем, я хочу передать foo устройство для вставки назад, в частности, одно из std::vector, которое не имеет ограничений за пределами ограничений памяти. Мне все еще нужен итератор «end» - в этом случае то, что никогда не сравнится с равным. (Или, если у меня был std::vector, но с ограничением по длине, возможно, он иногда сравнивался бы равным?)

Как мне это сделать? У меня есть возможность изменить API foo - лучше ли не проверять диапазон, а вместо этого предоставлять альтернативные средства для получения требуемого выходного диапазона? (Что было бы необходимо в любом случае для необработанных массивов, но не обязательно для обратных вставок в вектор.) Это казалось бы менее надежным, но я изо всех сил стараюсь сделать «надежную» (выше) работу.

Answer 1

Если foo проверяет, имеет ли размер distance(output_begin, output_end) достаточный размер, чтобы содержать результаты, что вы могли бы использовать в качестве «конечного» итератора? A back_inserter добавляет элементы в конец; distance между местом, где back_inserter добавляет элементы и конец последовательности, по определению, 0.

A foo с std::copy-like signature foo(InIt, InIt, OutIt), на мой взгляд, ваш лучший вариант. На самом деле это не «непрочно». Для большинства алгоритмов вы просто хотите выполнить такую ​​проверку диапазона в отладочных сборках по соображениям производительности, а достойная реализация стандартной библиотеки (например, стандартная библиотека Visual C++) уже обеспечит много проверок диапазона в отладочных сборках.

В качестве альтернативы вы можете создать back_inserting_foo(InIt, InIt, Container), хотя создание специального случая для этого было бы немного необычным и создавало бы большую нагрузку для пользователей функции, чтобы узнать, какую перегрузку им нужно использовать для разных типов итераторов.

Answer 2

Вы можете избежать изменений API foo() «s, выполняя проверку безопасности, как вы идете, проверяя, что curr_output_iter != output_end перед каждым элементом выписано (см ниже), а не один раз в начале с distance() чекой как James McNellis suggests.

Для этого потребуется написать собственный «адаптер итератора», чтобы обеспечить «расширенный» итератор вывода, который может проверить, находится ли он в конце допустимого диапазона. Затем вы по праву смените шаблонные имена с OutputIterator на SafeOutputIterator - хотя это просто служит документацией, потому что это то, что невозможно выполнить на C++.Мы различаем «ограниченные» и «неограниченные» пары итераторов: для последних два итератора никогда не сравнится одинаково, и на самом деле 2-й итератор никогда не понадобится ни для чего, кроме его типа.

/* 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()); 
} 

Теперь вы можете написать код, как:

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

Вы можете иметь foo() проверку curr_output_iter != output_end перед каждым писать через *curr_output_iter, или же вставить чек в safe_output_iterator::operator=(). Последнее кажется предпочтительным, поскольку вы не можете забыть выполнять проверку всякий раз, когда пара safe_output_iterator s передается произвольному алгоритму (по-видимому, это похоже на то, как работают отладочные версии работы STL). Вы также можете написать перегрузки soi_begin_cont() и soi_end_cont() для массивов фиксированного размера.

Все это было бы гораздо менее громоздким, если бы вместо пар итератора использовались ranges алгоритмами STL - таким образом, один шаблон функции мог бы возвращать соответствующий диапазон, охватывающий весь массив, например.

Answer 3

Как я уже говорил в комментарии к ответу j_random_hacker, в если изменить алгоритм таким образом, что итераторы, передаваемые в него могут быть различных типов, например,

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

, то вы можете очень легко написать back_inserter_end класс для тестирования против:

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

Вы можете назвать свой "безопасный" алгоритм:

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

Внутри вашего «безопасного» алгоритма вы можете проверить, out_it == out_end перед использованием out_it; поскольку out_it - это back_insert_iterator, этот тест всегда будет возвращать false (что является желательным поведением).