Copy range up to delimiter

Question

The problem I was trying to solve sounded pretty basic, but turned out to be a bit hairy.

I need to select some lines of arbitrary length from an input stream (file or standard input) and print them to output. In other words, a function that just echos the line would do the job. The input stream is encoded in UTF-8. For reasons that I don't quite understand, the normal <string> mangles the stream, so I couldn't use:

std::string line;
std::readline(line);
std::cout << line;

I did solve it using basic_istream::getline(); however, this function writes to a buffer, and I need to tell it how big the buffer is. To make it deal with lines of arbitrary length, I need to read to a buffer in a loop, checking whether failbit is set (when the end of the line wasn't reached).

Then, the easier solution was to use iterators on the input and the output stream, like this:

template<typename I, typename O, typename T>
I copy_until(I first, I last, O d_first, T delim)
{
    while (first != last && *first != delim) {
        *d_first = *first;
        ++first;
        ++d_first;
    }
    return first;
}

This copies from first up to last at most, and stops if the delimiter is encountered. It returns a pointer to the first character in the input range that was not copied.

It can be used like this to copy all input to output:

int main()
{
    std::istreambuf_iterator<char> first(std::cin);
    std::istreambuf_iterator<char> last;
    std::ostreambuf_iterator<char> d_first(std::cout);

    while (first != last) {
        first = copy_until(first, last, d_first, '\n');
        std::cout.put(*first);
        ++first;
    }
}

The third argument of copy_until could of course be a unary predicate, then instead of while (first != last && *first != delim) it would say while (first != last && !p(*first)).

More important questions:

• Is there an algorithm in <algorithm> that I have overlooked? copy_if and partition_point come close, but they don't do exactly that, and partition_point followed by copy_n will not work with forward iterators.
• I am not sure how to declare that the two iterators need to point to the same type as the type of the delimiter or the argument to the unary predicate.
• Not certain about the return value. This one is the most useful for my particular use case.
• Or maybe there is a much, much easier way that avoids this altogether. But copy_until might be useful in other contexts?

Answer 1

template<typename I, typename O, typename T>
I copy_until(I first, I last, O d_first, T delim) {

• Make your interfaces explicit. While I and O simply translate to iterator direction, what category type is your function requiring? Use the interface to document concepts (e.g. InputIterator, OutputIterator).

• Declare read-only input parameters that are expensive or of an unknown type (T) by const&.

---

Not certain about the return value. This one is the most useful for my particular use case.

• When determining your functions return specification, consider what useful information the caller may want. You return first because the function may not consume the entire range. It is important to know where copy_until ended so it may be restarted. How about d_first? Knowing where to resume copying seems like something a caller would also want.

---

I am not sure how to declare that the two iterators need to point to the same type as the type of the delimiter or the argument to the unary predicate.

Or maybe there is a much, much easier way that avoids this altogether. But copy_until might be useful in other contexts?

Why not both? Having a copy_while function that takes a predicate would be useful. boost::copy_until takes a predicate and is just a negated version of their boost::copy_while. See boost/algorithm/cxx11/copy_if.hpp.

---

• Is there an algorithm in <algorithm> that I have overlooked? copy_if and partition_point come close, but they don't do exactly that, and partition_point followed by copy_n will not work with forward iterators.

To meet the requirements of input iterators, you are not going to be able to improve on what you already have. If you want to optimize for other cases, you can refer to the notes on std::copy:

Notes

In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable.

So, if you have TriviallyCopyable types and are working with contiguous areas of memory, something as simple as a std::find and a call to std::copy can offer speed-up.

You would end up with something like this:

#include <algorithm>
#include <iterator>
#include <tuple>

namespace detail {
struct StandardVersion {};
struct OptimizedVersion {};

template <typename InputIterator, typename OutputIterator, typename T>
auto copy_until(InputIterator first, InputIterator last, OutputIterator out,
                const T& stop_value, StandardVersion)
    -> std::tuple<InputIterator, OutputIterator> {
  while (bool(first != last) && bool(*first != stop_value)) {
    *out++ = *first++;
  }

  return std::make_tuple(first, out);
}

template <typename ContigousIterator, typename OutputIterator, typename T>
auto copy_until(ContigousIterator first, ContigousIterator last,
                OutputIterator out, const T& stop_value, OptimizedVersion)
    -> std::tuple<ContigousIterator, OutputIterator> {
  const auto stop_iter = std::find(first, last, stop_value);
  return std::make_tuple(stop_iter, std::copy(first, stop_iter, out));
}
};

template <typename InputIterator, typename OutputIterator, typename T>
inline auto copy_until(InputIterator first, InputIterator last,
                       OutputIterator out, const T& stop_value) {
  using InputValueType =
      typename std::iterator_traits<InputIterator>::value_type;
  using OutputValueType =
      typename std::iterator_traits<OutputIterator>::value_type;
  using InputCategory =
      typename std::iterator_traits<InputIterator>::iterator_category;
  using OutputCategory =
      typename std::iterator_traits<OutputIterator>::iterator_category;

  return detail::copy_until(
      first, last, out, stop_value,
      std::conditional_t<
         std::is_trivially_copyable<InputValueType>::value
         && std::is_base_of<std::random_access_iterator_tag, InputCategory>::value
         && std::is_base_of<std::random_access_iterator_tag, OutputCategory>::value,
         detail::OptimizedVersion, 
         detail::StandardVersion>{});
}

Note: While the concept of ContiguousIterator is being added to the standard in C++17, a std::contiguous_iterator_tag isn't being added. Dispatching on std::random_access_iterator_tag will use the optimized call to the contiguous operations of std::copy for all random access containers except std::deque. std::deque is not guaranteed to be contiguous and would fall back to copying by element.

Answer 2

The third argument of copy_until could of course be a unary predicate, then instead of while (first != last && *first != delim) it would say while (first != last && !p(*first)).

Even better: remove the I last argument entirely! Just use the predicate for the whole thing, and the condition becomes while (!p(first)).

---

You're returning I (the place you stopped parsing the input stream), but similar functions in the STL return O (the place they stopped outputting to the output stream). The latter is more useful in STL cases, because typically the caller knows where he stopped parsing the input: it's last!

In your case, both I and O are useful; so why not return both?

template<typename I, typename O, typename Pred>
std::pair<I, O> copy_until(I first, O d_first, Pred pred)
{
    while (!pred(first)) {
        *d_first = *first;
        ++first;
        ++d_first;
    }
    return {first, d_first};
}

Your main thus becomes:

int main()
{
    std::istreambuf_iterator<char> first(std::cin);
    std::istreambuf_iterator<char> last;
    std::ostreambuf_iterator<char> d_first(std::cout);

    while (first != last) {
        std::tie(first, std::ignore) = copy_until(
            first, d_first, [=](auto it){ return it == last || *it == '\n'; }
        );
        if (first == last) break;  // Whoops!
        std::cout.put(*first);
        ++first;
    }
}

The // Whoops! comment indicates the fix for a crashing bug in your original main.

---

Boost.Algorithm actually has both copy_until and its inverse, copy_while: http://marshall.calepin.co/copy_while.html Strangely, Boost's version takes last as a parameter exactly the way yours does. In Boost's case, I think that might be because they're trying to target C++03, which doesn't have lambdas, so there's no way that's both easy and lightweight to express [last](auto it) { return it != last && *it != delim; } — in C++03 you had to do that with boost::bind and maybe boost::function as well.

---

I am not sure how to declare that the two iterators need to point to the same type as the type of the delimiter or the argument to the unary predicate.

The short answer is "don't"; complicated dependencies like that usually indicate that you've put the abstraction boundary in the wrong place (e.g. in this example, passing First, Last, Delim instead of First, Pred). But just for the record, you could do something crazy with enable_if, which can go on the return type of the function or on one of its parameters or on one of its template parameters, your choice.

auto copy_until(I first, I last, O d_first, T delim)
    -> std::enable_if_t<std::is_same_v<decltype(*first), T>, I>
{
    // ...
}

I'm pretty sure you don't want to assert that decltype(*d_first) is T, because that would prevent you from using something like a back_insert_iterator<vector<T>> with this algorithm.

Answer 3

Both answers were great (a pity I can't accept both). I need to add the "much easier way" answer. Since this was about copying (unformatted) new-line separated line from input to output, the simple function that does that would be:

template<typename InputStream, typename OutputStream>
void copy_line(InputStream& in, OutputStream& out)
{
    char c = in.get();
    while (in && c != '\n') {
        out.put(c);
        c = in.get();
    }
/* Or why not even:
    for (char c = in.get(); in && c != '\n'; c = in.get())
        out.put(c);
*/
}

This is almost identical in semantics to the copy_until() discussed above; it consumes the new line char, however, since this is more useful for my very specific use case.

All the recommendations in the other answers about return value, arguments, names and so on apply here too.

However

while reading I finally found that I have missed the obvious, namely, std::basic_istream::get() can directly read into a stream buffer...

template<typename InputStream, typename OutputStream>
void copy_line(InputStream& in, OutputStream& out)
{
    in.get(*out.rdbuf());
    in.ignore();
}

The ignore() is there because the delimiter is left on the input stream.