“结束()”后置插入器的迭代器？

Question

对于诸如从 std::back_inserter() 返回的迭代器，是否有可以用作“结束”迭代器的东西？

乍一看这似乎有点无意义，但我有一个 API，它是：

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

foo 对输入序列执行一些操作，生成输出序列。 （foo 知道 Who 的长度，但可能等于也可能不等于输入序列的长度。）

output_end 参数的取值是奇数部分：std例如，::copy 不会这样做，并且假设您不会向它传递垃圾。 foo 这样做是为了提供范围检查：如果您传递的范围太小，它就会以防御性编程的名义抛出异常。 （而不是潜在地覆盖内存中的随机位。）

现在，假设我想传递 foo 一个后插入器，特别是来自 std::vector 的插入器，它在外部没有限制的内存限制。我仍然需要一个“结束”迭代器 - 在这种情况下，它永远不会比较相等。 （或者，如果我有一个 std::vector 但长度有限制，也许它有时可能比较相等？）

我该如何去做呢？我确实有能力更改 foo 的 API - 是否最好不检查范围，而是提供替代方法来获取所需的输出范围？ （对于原始数组来说无论如何都是需要的，但对于向后插入到向量中则不需要。）这看起来不太健壮，但我正在努力使“健壮”（上面）工作。

Answer 1

正如我在对 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_it == out_end；由于 out_it 是一个 back_insert_iterator，因此此测试将始终返回 false（这是所需的行为）。

Answer 2

如果 foo 正在检查以确保 distance(output_begin, output_end) 足够大以包含结果，那么您可以使用什么作为“end”迭代器？ back_inserter 将元素添加到末尾；根据定义，back_inserter 添加元素的位置与序列末尾之间的距离为0。

在我看来，带有 std::copy 类似签名 foo(InIt, InIt, OutIt) 的 foo 是你最好的选择。它并不是真正的“不健壮”。对于大多数算法，出于性能原因，您只想在调试版本中进行这种范围检查，并且一个不错的标准库实现（如 Visual C++ 标准库）已经在调试版本中提供了大量范围检查。

或者，您可以创建一个 back_inserting_foo(InIt, InIt, Container)，尽管为此创建一个特殊情况会有点不寻常，并且会给函数的用户带来更大的负担，让他们无法知道他们需要哪个重载用于不同类型的迭代器。

Answer 3

您可以通过在写出每个元素之前执行安全检查来避免更改 foo() 的 API（请参见下文） ，而不是在开始时使用 distance() 检查 詹姆斯·麦克内利斯建议。

执行此操作需要编写自己的“迭代器适配器”以提供“增强型”输出迭代器，该迭代器可以测试它是否位于有效范围的末尾。然后，您可以正确地将模板类型名称从 OutputIterator 更改为 SafeOutputIterator —— 即使这只是作为文档，因为它无法在 C++ 中强制执行。我们区分“有界”和“无界”迭代器对：对于后者，没有两个迭代器会比较相等，事实上，除了其类型之外，任何其他迭代器都不需要第二个迭代器。

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

您可以在每次写入 *curr_output_iter 之前让 foo() 检查 curr_output_iter != output_end，或者插入safe_output_iterator::operator=() 中的检查。后者似乎更可取，因为每当一对 safe_output_iterator 被传递给任何任意算法时，您就不会忘记执行检查（大概这类似于 STL 的调试版本的工作方式）。您还可以为固定大小的数组编写 soi_begin_cont() 和 soi_end_cont() 的重载。

如果 ranges 是这样的话，所有这些都会变得不那么麻烦。由 STL 算法而不是迭代器对使用——例如，这样单个函数模板就可以返回跨越整个数组的适当范围。