如何为 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 在 iota(std::back_inserter(c1), something(c1, c1.size()), std::begin(c1)) 中的 for 循环的 c1.size() 步之后停止？

Answer 1

我认为你做不到 - 或者我不明白你的问题，但是..

根据 http://en.cppreference.com/w/cpp/algorithm/iota，此算法适用于现有元素范围 - 因此将它与以下一起使用没有意义： std::back_inserter 作为第一个迭代器，它主要用于插入元素。

I want to fill a container by consequtive values of iterators to elements of another container

一个不同的解决方案，它使用 generate_n:

live

   std::vector<int> src = {0,1,2,3};
   std::vector<std::vector<int>::iterator> dst;
   std::generate_n(std::back_inserter(dst), src.size(), [it=src.begin()]() mutable {return it++;});

Answer 2

您的问题包含一个 iota 实现，这与我认为的标准中的实现不同。这是我知道的标准版本 http://en.cppreference.com/w/cpp/algorithm/iota.

您的 iota（我将在我的代码中将其重命名为 miota）允许开始和结束使用不同类型的迭代器。

你想要的算法是；在处理完所有值之前，end sentinel 需要不同于 begin（插入器）。对于处理值，您只需要一个对象，然后对该对象使用增量和复制构造。

因此，您的终端哨兵应该了解值处理，完成后终端哨兵应该以某种方式等于插入器。

我是通过在名为 IotaHelper 的 class 中保存原始容器的 begin/end 个迭代器来实现的。这使用 shared_ptr 与称为 IotaEndSentinel.

的哨兵 class 共享状态

当您在 miota 中增加 value 时，它实际上增加了 IotaHelper 的开始迭代器。当您检查插入器和哨兵是否相等时，它实际上会检查 IotaHelper.

中的迭代器相等性

所有带有基本示例的代码都在这里：

#include <iterator>
#include <numeric>
#include <vector>
#include <iostream>
#include <utility>
#include <memory>

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

template<typename Container>
struct IotaHelper
{
    using Iterator = typename Container::iterator;
    using IteratorPair = std::pair<Iterator, Iterator>;

    IotaHelper(Iterator begin, Iterator end)
        :
        pair(std::make_shared<IteratorPair>(begin, end))
    { }

    operator Iterator()
    {
        return pair->first;
    }

    IotaHelper& operator++()
    {
        ++pair->first;
        return *this;
    }

    std::shared_ptr<IteratorPair> pair;
};

template<typename Container>
struct IotaEndSentinel
{
    using Helper = IotaHelper<Container>;
    using Iterator = typename Helper::Iterator;

    IotaEndSentinel(const Helper& helper)
        :
        helper(helper)
    {}

    template<typename C>
    friend bool operator!=(const std::back_insert_iterator<C>& bii,
                           const IotaEndSentinel& sentinel)
    {
        return sentinel.helper.pair->first != sentinel.helper.pair->second;
    }

    Helper helper;
};

int main()
{
    using Container0 = std::vector<int>;
    using Container1 = std::vector<Container0::iterator>;

    Container0 c0 = {1, 2, 3, 4, 5};
    Container1 c1;

    IotaHelper<Container0> iotaHelper(c0.begin(), c0.end());

    miota(std::back_inserter(c1),
          IotaEndSentinel<Container0>(iotaHelper), 
          iotaHelper);

    std::cout << "Result: ";
    for (auto iter : c1)
    {
        std::cout << *iter << ", ";
    }

    std::cout << std::endl;
}

我尝试这样做是因为它很有趣。但是请不要使用这种方法来破解像 back_insert_iterator 这样的输出迭代器，并为自己制作一个适用于不同容器的通用方法。

template<typename SourceContainer, typename IteratorContainer>
void FillIterators(SourceContainer& sc, IteratorContainer& ic)
{
    for (auto iter = sc.begin(); iter != sc.end(); ++iter)
    {
        ic.insert(ic.end(), iter);
    }
}

编辑：

在使用堆分配之后，我觉得那段代码很臭。我们可以推理 "iterators and the process".

而不是试图推理 "value and the process"

我们可以构建一个包含进程迭代器和插入迭代器的迭代器包装器。

当算法需要取消引用包装器时，它将 return 插入迭代器。

当算法需要与其他算法进行比较时 "wrapper or sentinel"，wrapper 将比较进程迭代器。

最后我们可以为 std::iota 和你的 miota 使用这样的迭代器。

完整示例在这里：

#include <iterator>
#include <numeric>
#include <vector>
#include <iostream>
#include <utility>
#include <memory>

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

template<typename InsertIterator, typename Iterator>
struct InsertWrapper
{
    InsertWrapper(const InsertIterator& inserter, const Iterator& iter)
        :
        inserter(inserter),
        iter(iter)
    { }

    bool operator!=(const InsertWrapper& other) const
    {
        //only compare process iterators
        return iter != other.iter;
    }

    bool operator!=(const Iterator& sentinel) const
    {
        //compare process iterator against the sentinel
        return iter != sentinel;
    }

    InsertIterator& operator*()
    {
        //return inserter for dereference
        return inserter;
    }

    InsertWrapper& operator++()
    {
        //iterate inserter as the process progresses
        ++inserter;
        ++iter;

        return *this;
    }

    InsertIterator inserter;
    Iterator iter;
};

template<typename InsertIterator, typename Iterator>
InsertWrapper<InsertIterator, Iterator> WrapInserter(const InsertIterator& inserter,
                                                     const Iterator& iter)
{
    return InsertWrapper<InsertIterator, Iterator>(inserter, iter);
}

int main()
{
    using Container0 = std::vector<int>;
    using Container1 = std::vector<Container0::iterator>;

    Container0 c0 = {1, 2, 3, 4, 5};
    Container1 c1;

    //use wrapper as usual iterator begin/end
    std::iota(WrapInserter(std::back_inserter(c1), c0.begin()),
              WrapInserter(std::back_inserter(c1), c0.end()), 
              c0.begin());

    std::cout << "std::iota result: ";
    for (auto iter : c1)
    {
        std::cout << *iter << ", ";
    }

    std::cout << std::endl;

    c1.clear();

    miota(WrapInserter(std::back_inserter(c1), c0.begin()),
          c0.end(), //end iterator as sentinel
          c0.begin());

    std::cout << "miota result: ";
    for (auto iter : c1)
    {
        std::cout << *iter << ", ";
    }

    std::cout << std::endl;
}

Answer 3

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

但是，如果您需要调用期望“输出哨兵”的算法，则使用带有哨兵的输出迭代器是有意义的（因为如果输出是“有限序列”，则不期望可能不安全，例如 pre-allocated std::vector）。这样的算法可能如下所示：

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

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

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，输出也会是不同的，这确实是有道理的state 每次，所以在某种意义上，没有两个输出迭代器一定是等价的...）

然而，旧算法通常不允许迭代器和哨兵具有不同的类型：

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

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

这在 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 或 in-place 构造来解决缺少的问题默认构造函数。

Full test program for C++20

如何为 back_insert_iterator 实现结束哨兵？

How to implement end sentinel for back_insert_iterator?

c++

algorithm

iterator

stl

idioms