std::copy() doesn't detect overlapping ranges

• Key: STDCXX-78
• Type: Improvement
• Status: Open
• Priority: Minor
• Assignee: Unassigned
• Reporter: Martin Sebor
• Component/s: 25. Algorithms
• Affects Version/s: 4.1.2, 4.1.3, 4.1.4, 4.2.0, 4.2.1
• Fix Version/s: 4.3.0

Description

Quoting from the response to the following post:
http://mail-archives.apache.org/mod_mbox/incubator-stdcxx-dev/200511.mbox/[e-mail]%3e

-------- Original Message --------
Subject: Re: questions about the lib.alg.copy test
Date: Wed, 30 Nov 2005 17:33:10 -0700
From: Martin Sebor <[e-mail]>
To: [e-mail]
References: <[e-mail]>

Anton Pevtsov wrote:
[...]
>
> 2. The copy algorithm can work in case when the destination range
> overlaps the source range (of course, first position of the source range
> should not be contained in the destination range). Current version
> doesn't contain special test for this case, but I prefer to have such
> test. What do you think about it?

The requirement in 25.2.1, p3 is that "result shall not be in the
range [first, last)." The algorithm doesn't detect violations of
this requirement but it probably should in debug mode. This would
be a useful enhancement in general. Let me file an enhancement for
it.

Martin

Comments

[Martin Sebor]

This might be harder than it seemed. The implementation of the algorithm looks like this:

template <class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator res)
{
    _RWSTD_ASSERT_RANGE (first, last);

    for (; !(first == last); ++first,++res)
        *res = *first;
    return res;
}

The naive solution is to change it like so:

template <class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator res)
{
    _RWSTD_ASSERT_RANGE (first, last);
    _RWSTD_ASSERT_NOT_IN_RANGE (res, first, last);

    for (; !(first == last); ++first,++res)
        *res = *first;
    return res;
}

But it doesn't work because a) there's no _RWSTD_ASSERT_NOT_IN_RANGE() and b) if there was (as a parallel to _RWSTD_ASSERT_RANGE), it would require some changes to the __rw_in_range() function template to make it work with cv-qualified pointers (i.e., in the common case when InputIterator=const T* and OutputIterator=T*).

All this might be worth doing if it can be used in other algorithms besides std::copy(). Otherwise it seems like a lot of effort and overhead for just one algorithm.

[Martin Sebor]

Let's see if this is worth doing in 4.3.