c++ - 如何实现 back_insert_iterator 的结束哨兵？

Question

我想通过迭代器的相应值填充一个容器到另一个容器的元素(经常发生现实生活中的问题)，比如:

std::container1< T > c1{/* initialized */};
assert(!c1.empty());
std::continer2< typename std::container1< T >::iterator > c2;
auto it = std::begin(c1), const end = std::end(c1);
do { c2.push_back(it); } while (++it != end);

STL 中有吸引人的std::iota 算法，但它是基于范围的，对于std::back_inserter(c2) 没有办法达到期望现在。然而，在下一版本的 STL 中，我可以期待 iota 算法的形式:

template< typename ForwardIterator, typename EndSentinel, typename T >
void
iota(ForwardIterator first, EndSentinel last, T value)
{
    for (; first != last; ++first) {
        *first = value;
        ++value;
    }
}

如何实现 EndSentinel 和 operator != (ForwardIterator, EndSentinel) 使上面的 iota 正好在 c1.size 之后停止() for 循环在 iota(std::back_inserter(c1), something(c1, c1.size()), std::begin(c1) 中的步骤)?

Answer 1

std::back_insert_iterator(或任何 OutputIterator)没有哨兵，也没有相等运算符，因为输出迭代器是一个“无限序列”:您可以将元素追加到末尾容器或写入文件，直到内存或磁盘空间用完。

但是，如果您需要调用期望“输出哨兵”的算法，则使用带有哨兵的输出迭代器是有意义的(因为如果输出是“有限序列”，则不期望可能不安全，例如一个预分配的 std::vector)。这样的算法可能如下所示:

template<typename InIter, typename InSentinel, typename OutIter, typename OutSentinel>
OutIter modernAlgorithm(InIter first, InSentinel last, OutIter outFirst, OutSentinel outLast);

在这种情况下，您所需要的只是一个普通哨兵，它比较不等于一切。另见 this answer .

template<typename T>
struct TrivialSentinel
{
    bool operator==(const T&) { return false; }
    bool operator!=(const T&) { return true; }
    friend bool operator==(const T&, TrivialSentinel&) { return false; }
    friend bool operator!=(const T&, TrivialSentinel&) { return true; }
};

modernAlgorithm(v.begin(), v.end(), std::back_inserter(r), TrivialSentinel<decltype(std::back_inserter(r))>());

(这可能看起来很奇怪，但如果你考虑到即使你对 out 的相同值重复相同的操作 *out = expr ，它确实有意义，输出每次都会处于不同的状态，所以在某种意义上，没有两个输出迭代器一定是等价的...)

但是，较旧的算法通常不允许迭代器和哨兵具有不同的类型:

template<typename InIter, typename OutIter>
OutIter olderAlgorithm(InIter first, InIter last, OutIter outFirst, OutIter outLast);

在这种情况下，您可以编写 std::back_insert_iterator 的子类或包装器，它具有默认构造函数并且始终与自身比较不相等。

这在 C++20 中很容易，其中 std::back_insert_iterator 有一个 default constructor :

// C++20

template<typename C>
struct BackInsertIteratorWithSentinel : public std::back_insert_iterator<C>
{
    BackInsertIteratorWithSentinel() {}  // C++20 only
    BackInsertIteratorWithSentinel(C& c) : std::back_insert_iterator<C>(c) {}
    
    bool operator==(const BackInsertIteratorWithSentinel&) { return false; }
    bool operator!=(const BackInsertIteratorWithSentinel&) { return true; }
};

template<typename C>
BackInsertIteratorWithSentinel<C> BackInserterWithSentinel(C& c)
{
    return BackInsertIteratorWithSentinel<C>(c);
}

template<typename C>
BackInsertIteratorWithSentinel<C> BackInserterWithSentinel()
{
    return BackInsertIteratorWithSentinel<C>();
}

olderAlgorithm(v.begin(), v.end(), BackInserterWithSentinel(r), BackInserterWithSentinel<std::vector<int> >());

请注意，即使在 C++20 中，std::back_insert_iterator 也没有相等运算符。

如果你必须支持旧版本的 C++，那么你可能必须从头开始实现你自己的 std::back_insert_iterator，或者使用 boost::optional 或者在-放置构造来解决缺少默认构造函数的问题。

Full test program for C++20