Extract input iterator from std::copy and std::copy_n

std::copy_n array
copy_n vs memcpy
std::array copy
std::fill_n
std::vector copy range
std::back_inserter
c++ vector
c++ iterator copy

I trying to implement an unserialization method that take an input iterator and perform a series of chunk reads (using std::copy and std::copy_n). Something like this (just an example):

template <class InputIt>
InputIt unserialize(InputIt it)
{
  std::copy_n(it, sizeof(header_type), reinterpret_cast<char*>(&header));
  std::copy_n(it, header.payload_size, std::back_inserter(payload));
  it = optional.unserialize(it);
  return it;
}

How do I advance input iterator in this case so each following call to std::copy_n continue read from it and I can finally return it?

I want to be generic to iterator categories (especially RandomAccessIterator and InputIterator) for performance reasons and hope it is possible to use std::copy methods without need to rewrite these. Stuff like bound checking and such will be done by iterator adapter or checked before unserialization call if size is known.

What do not work nor acceptable:

  1. Using std::copy_n<InputIt&>(it, ...) may work for some categories but not for all and it's too unreliable.
  2. Using std::advance after each call leads to rereading same block again for some iterators. Not preferable and may be impossible for some sources.

UPDATE Making iterator reference adapter doesn't help as random access iterator version of copy_n return pointer to past the last element copied while input iterator version return pointer to the last element copied. So I guess own version of copy_n works best with additional iterator adapter for bound checking.

For random access iterator this form can be used - and it is fine:

template <class InputIt, class N, class OutputIt>
InputIt copy_n_advance_input(InputIt it, N dist, OutputIt outIt)
{
    std::copy_n(it, dist, outIt);
    return std::next(it, dist);
}

Unfortunately - problems are when we want to deal with one pass input iterator - like here (got 'd' - not 'c'):

std::string s = "abcd";
std::istringstream ss{s};
auto e = copy_n_advance_input(std::istream_iterator<char>(ss), 
                             2, 
                             std::ostream_iterator<char>(std::cout, ","));
std::cout << "\n" << *e << "\n";

So it seems it is needed, as usual in STL, two forms:

template <class InputIt, class N, class OutputIt>
InputIt copy_n_advance_input_impl(InputIt it, N dist, OutputIt outIt,
                                  std::input_iterator_tag)
{
    while (dist-- > 0)
    {
        *outIt = *it;
        ++outIt;
        ++it;
    }
    return it;
}

template <class InputIt, class N, class OutputIt>
InputIt copy_n_advance_input_impl(InputIt it, N dist, OutputIt outIt, 
                                  std::random_access_iterator_tag)
{
    std::copy_n(it, dist, outIt);
    return std::next(it, dist);
}

template <class InputIt, class N, class OutputIt>
InputIt copy_n_advance_input(InputIt it, N dist, OutputIt outIt)
{
    return copy_n_advance_input_impl(it, dist, outIt, typename std::iterator_traits<InputIt>::iterator_category {});
}

Note, the proposed version for std::input_iterator_tag is not as efficient as in STL (at least for gcc) - it does extra iteration for input - this iteration is not necessary to perform copy - but it is needed to return beginning of "after copy" range (stl_algo.h):

754   template<typename _InputIterator, typename _Size, typename _OutputIterator>
755     _OutputIterator
756     __copy_n(_InputIterator __first, _Size __n,
757          _OutputIterator __result, input_iterator_tag)
758     {
759       if (__n > 0)
760     {
761       while (true)
762         {
763           *__result = *__first;
764           ++__result;
765           if (--__n > 0)
766         ++__first;
767           else
768         break;
769         }
770     }
771       return __result;
772     }

Last note - it is wiser to use, for random-access-iterators (like std::vector::iterator) the version that just calls std algorithms - because they can be even more optimized - e.g. for contiguous memory iterator over POD types - that can be just memcpy'ied. Or some specialization for std::vector<bool> or std::deque<T> exist, that uses their internal structure to perform copy in most efficient way.

Extract input iterator from std::copy and std::copy_n - c++ - android, I trying to implement an unserialization method that take an input iterator and perform a series of chunk reads (using std::copy and std::copy_n). Something like​  Input iterators to the initial position in a sequence of at least n elements to be copied. InputIterator shall point to a type assignable to the elements pointed by OutputIterator. Number of elements to copy. If this value is negative, the function does nothing. Size shall be (convertible to) an integral type.

You could create an iterator adapter that always works through a reference to the supplied iterator. Here's the basic skeleton of such an adapter:

#include <iterator>

template<typename InputIterator>
struct IteratorReference
{
    InputIterator& it;

    IteratorReference(InputIterator& it)
        : it(it)
    {}
    // {copy, move, destructor} == default

    // iterator methods (TODO: add the rest)
    IteratorReference& operator++()
    { ++it; return this; }

    typename InputIterator::reference operator*()
    { return *it; }

    // Convert back to original iterator
    operator InputIterator() const
    { return it; }
};


template<typename InputIterator>
IteratorReference<InputIterator> make_iterator_reference(InputIterator it)
{
    return it;
}

To use it, simply create and use a wrapper in place of the original iterator:

#include <algorithm>
#include <vector>

struct Header
{
    std::size_t payload_size;
};

template <class InputIt>
InputIt unserialize(InputIt it, Header& header, std::vector<char>& payload)
{
    auto i_ref = make_iterator_reference(it);
    std::copy_n(i_ref, sizeof header, reinterpret_cast<char*>(&header));
    std::copy_n(i_ref, header.payload_size, std::back_inserter(payload));
    i_ref = optional.unserialize(i_ref);
    return i_ref;
}

std::copy_n - copy_n, template <class InputIterator, class Size, class OutputIterator> OutputIterator copy_n Copies the first n elements from the range beginning at first into the range beginning copy_n algorithm example #include <iostream> // std::cout #​include  Constrained algorithms: std::ranges::copy, std::ranges::sort, 1) Copies exactly count values from the range beginning at first to the range beginning at result. Formally, for each non-negative integer i < n, performs * (result + i) = * (first + i). Overlap of ranges is not permitted.

I know this is an old question, but... Recently I've run into similar issue, and I feel pretty sad when I see there isn't any good solution for this problem... Nevertheless, I've tried to write an iterator wrapper like what Toby Speight said, and I've extended it a bit. This wrapper is only used for InputIterator, because other kind of iterators supported by std::copy and std::copy_n are multipass iterators, and it's possible to directly use std::next and std::advance on them instead of using this wrapper.

template<typename Iterator>
struct Wrapper {
    using traits = std::iterator_traits<Iterator>;
    using difference_type = typename Traits::difference_type;
    using reference = typename Traits::reference;
    //...

    reference operator*() const { return *(*(this->current)); }

    //need implement operator++(int) too, in the similar way
    Wrapper& operator++() { 
        if(this->indicator != 0) {
            ++(*(this->current));
            --this->indicator;
        }

        return *this;
    }

    //need to implement operator!= too, in the similar way
    bool operator==(const Wrapper& other) const { 
        return *(this->current) == *(other.current) or this->indicator == other.indicator;
    }

    Iterator* current;
    difference_type indicator;
};

template<typename Iterator>
struct Range {
    using category = typename std::iterator_traits<Iterator>::iterator_category;
    //...
    using difference_type = typename std::iterator_traits<Iterator>::difference_type;

    constexpr bool isForwardOrAbove() { 
        return std::is_base_of_v<std::forward_iterator_tag, category>;
    }

    using iterator = std::conditional_t<isForwardOrAbove(), Iterator, Wrapper<Iterator>>;

    std::pair<iterator, iterator> splitSubRange(difference_type n) {
        if constexpr (isForwardOrAbove()) {
            //forward iterators are multi-pass iterators, so using std::advance on one iterator will not invalidate its copies
            auto oldBegin = this->begin;
            std::advance(this->begin, n);
            return {oldBegin, std::next(oldBegin, n)};
        }
        else {
            //non-forward-iterator
            return {{&(this->begin), n}, {&(this->end), 0}};
        }
    }

    Iterator begin;
    Iterator end;
}

To use them, firstly you need a Range object which holds iterators, and use the splitSubRange method to obtain plain iterators, or, if they are only InputIterators, iterator wrappers.

template<typename InputIterator>
InputIterator unserialize(InputIterator begin, InputIterator end) {
    auto range = Range<InputIterator>{begin, end};
    auto [begin, end] = range.splitSubRange(sizeof(header_type));
    //before having "used" the iterator obtained from range, you shouldn't use range again.
    std::copy(begin, end, header.begin());
    //after having "used" the iterator, you can use the range object to obtain the next sub-range
    auto [begin2, dummy] = range.splitSubRange(sizeof(header_type_2));
    std::copy_n(begin2, sizeof(header_type_2), header2.begin());
    ...
    return range.begin;
}

std::copy_n() function with example in C++ STL, This website uses cookies to ensure you get the best experience on our website. C++ STL | std::copy_n() function: Here, we are going to learn about the of elements to be copied. iterator target_start – is the beginning iterator of target Input: //declaring & initializing an int array int arr[] = { 10, 20, 30, 40,  Input iterators to the initial and final positions in a sequence. The range copied is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. Output iterator to the

std::copy, std::copy_if, Constrained algorithms: std::ranges::copy , std::ranges::sort , . Output iterator to the element in the destination range, one past the last element copied. Various varieties of copy () exist in C++ STL that allows to perform the copy operations in different manners, all of them having their own use. These all are defined in header <algorithm>. This articles introduces everyone to these functions for usage in day-to-day programming. 1. copy (strt_iter1, end_iter1, strt_iter2) : The generic copy

std::copy doesn't work on List types? · Issue #892 · capnproto , I get a compiler error that there's no matching std::copy/std::copy_n: _OutputIterator = float *] copy_n(_InputIterator __first, _Size __orig_n,  1) Copies all elements in the range [first, last) starting from first and proceeding to last - 1. The behavior is undefined if d_first is within the range [first, last).In this case, std::copy_backward may be used instead.

Different methods to copy in C++ STL, Different methods to copy in C++ STL | std::copy(), copy_n(), copy_if(), How to find the Entry with largest Value in a C++ Map · Difference between Iterators and exit(0) vs exit(1) in C/C++ with Examples · cin get() in C++ with Examples  node_type extract( const key_type& x ); 1) Unlinks the node that contains the element pointed to by position and returns a node handle that owns it. 2) If the container has an element with key equivalent to x, unlinks the node that contains that element from the container and returns a node handle that owns it.

Comments
  • All I can suggest is to reimplement your own copy_n function that takes a reference to the iterator, but that's not really desirable - especially given how much work has gone into standard library implementations to optimize their performance.
  • "Using std::advance after each call leads to rereading same block again for some iterators." - can you describe exactly what you mean here? Perhaps give an example.
  • Are you sure std::copy_n<InputIt&> is not guaranteed to work?
  • A simple test using const char* as iterator not working with std::copy_n<InputIt&> but works with possible implementation from cppreference.com.
  • @TobySpeight I can't agree more about how much hard work has gone into std library. Also all compiler optimizations that has been done to this code. I was afraid of this answer and I guess I will go for it but I really hope there will be other suggestions too.
  • This solution is kind of natural. And it exactly there I end up before asking the question (I should mention it, sorry). And maybe it is the best one, but as mentioned in question I like to avoid to rewrite these functions if there other solutions to this. Still, thank you for sharing, maybe it helps others.
  • I was thinking about some kind of new iterator wrapper that keep track of incrementation of original iterator- but it failed just because of that optimal implementation of __copy_n for not random iterators - it just returns one less value. And it is very complicated - if you like I can share it - but I really doubt in its usefullness
  • No Piotr, that's fine, thank you! It is something I will try (just to compare to this solution) but it is simple to write one.
  • try with std::forward_list - for not random_access_iterators - it might now work - I've tried similar solution - see comments under my answer...
  • I hadn't seen your comment, @PiotrNycz. I confess I haven't run this code - only compiled it. If the question had posted a full example, I'd have been able to experiment with it and actually test what I answer with.
  • As I mentioned in UPDATE part of the question using iterator reference adapter is not good idea as random access type and input type will advance iterator differently.
  • @pechkin, could this answer be adapted a little, to get where you want to be? We'd need to keep track of whether the underlying iterator has been dereferenced since last incremented (would we need another layer of wrapping for this?). It might get too complicated, but perhaps worth investigating. If there's a real need, you might want to make a Standard Library enhancement proposal for algorithms that accept input iterators by reference (or ones that return a pair).
  • @TobySpeight, I guess I'm looking for a "simple trick" people used to solve this problem, but maybe there aren't any. To continue with my project I used my version of std::copy_n for now, but I agree, this problem must get an attention of standard library committee.