Orient Orient - 1 month ago 15
C++ Question

How to implement end sentinel for back_insert_iterator?

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

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