How to implement end sentinel for back_insert_iterator?

Question

I want to fill a container by consequtive values of iterators to elements of another container (often occured real life problem), say:

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

There is attractive std::iota algorithm in STL, but it is range-based and for std::back_inserter(c2) there is no way to achieve desired currently. However in the next versions of STL I can expect the iota algorithm of the form:

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

How to implement EndSentinel and operator != (ForwardIterator, EndSentinel) to make above iota stop after exactly c1.size() step of the for loop in iota(std::back_inserter(c1), something(c1, c1.size()), std::begin(c1))?

Answer 1

There is no sentinel for std::back_insert_iterator (or any OutputIterator) and also no equality operator, because an output iterator is an "unlimited sequence": You can append elements to the end of a container or write to a file until you run out of memory or disk space.

However, it makes sense to have an output iterator with a sentinel if you need to call an algorithm which expects an "output sentinel" (because not expecting one may be unsafe if the output is a "limited sequence", such as a pre-allocated std::vector). Such an algorithm could look like:

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

In this case, all you need is a trivial sentinel, which compares unequal to everything. See also 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))>());

(This may seem odd, but it does make sense if you consider that even if you repeat the same operation *out = expr on the same value of out, the output will be in a different state each time, so in a certain sense, no two output iterators are ever necessarily equivalent...)

However, older algorithms often don't allow the iterator and sentinel to have different types:

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

In this case, you can write a sub class or wrapper of std::back_insert_iterator, which has a default constructor and always compares unequal to itself.

This is easy in C++20, where std::back_insert_iterator has a 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> >());

Note that even in C++20, std::back_insert_iterator does not have an equality operator.

If you have to support older versions of C++, then you may have to implement your own std::back_insert_iterator from scratch, or use boost::optional or in-place construction to work around the lack of a default constructor.

Full test program for C++20

Answer 2

Your question includes an iota implementation which is different than the one in the standard I believe. Here is the standard version I know http://en.cppreference.com/w/cpp/algorithm/iota.

Your iota (which I will rename it as miota in my code) allows different type of iterators for begin and end.

What you want in the algorithm is; end sentinel needs to be different from begin (the inserter) until all values are processed. For processing values you only take one object and you use increment and copy-construction on that object.

Therefore, your end sentinel should know about the value processing and when finished the end sentinel should become equal to the inserter somehow.

I did it via holding begin/end iterators of the original container in a class called IotaHelper. This uses shared_ptr for sharing state with the sentinel class which is called IotaEndSentinel.

When you increment the value inside miota, it actually increments the begin iterator of the IotaHelper. When you check equality with the inserter and the sentinel it actually checks the iterator equality inside the IotaHelper.

All code with a basic example is here:

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

I have tried to do this because it was fun. But please don't use this method for hacking output iterators like back_insert_iterator and make a generic method for yourself for different containers.

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

EDIT:

After using heap-allocation that code was smelling to me. Instead of trying to reason about the "value and the process" we can reason about the "iterators and the process".

We can build an iterator-wrapper which contains the process iterator and the insert iterator together.

When the algorithm needs to dereference the wrapper, it will return the insert iterator.

When the algorithm needs to compare to other "wrapper or sentinel", wrapper will compare the process iterator.

In the end we can use such iterator for both std::iota and your miota.

Complete example is here:

#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

I dont think you can do it - or maybe I dont understand your question, but..

according to http://en.cppreference.com/w/cpp/algorithm/iota, this algorithm works on existing range of elements - so it does not make sense to use it with: std::back_inserter as first iterator which basicly is used to insert elements.

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

a different solution which uses 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++;});