From: James Kuyper on
Mathias Gaunard wrote:
> On 4 sep, 15:39, James Kuyper <jameskuy...(a)verizon.net> wrote:
>> Mathias Gaunard wrote:
>>> On 31 ao t, 02:55, Thomas Maeder <mae...(a)glue.ch> wrote:
>>>> Provided the iterators are pointers (or close relatives to pointers),
>>>> which is the prerequisite for considiering the usage of memmove() or
>>>> memcpy(), std::copy can certainly determine whether the areas overlap.
>>> No, it can't.
>>> The compiler could do it, by doing alias analysis, which is a hard (NP-
>>> hard even) problem -- which is why you can't rely on the compiler
>>> doing it -- but a function certainly cannot.
>> NP problems are not necessarily hard to solve; the category
>> includes some of the very easiest problems to solve. I think what you
>> actually mean is NP-complete, which is the sub-set of NP problems for
>> which no polynomial-time solution is known.
....
> I suggest you look up the definitions on wikipedia. ...

I did so before writing that message, but sometimes you have to know
what to look for, before you can find it. I didn't realize that NP-hard
is a name of a complexity category, though I knew that NP is. I thought
you were just saying "as hard as an NP problem". The wikipedia page for
NP informally describes NP-complete as containing the hardest problems
in NP, so i presumed that this might be what you were referring to. I
apologize for confusing the issue. There's a link to NP-hard at the
bottom of that page, but it is not otherwise mentioned, so there was
nothing to remind me that NP-hard is a special term in itself.

> ... Note I'm no expert
> in such things however, nor do I have any desire to discuss them.

OK, I won't - beyond the following comment:

>> Those are very hard
>> problems, at least when 'n' is large.
>
> Size of the input is irrelevant to hardness of a problem.

So you're saying that the traveling salesman problem is just as hard
when 4 cities are involved as as when 100 are involved? If that's the
case, what is this "polynomial" about? What is the meaning of the
variable that the polynomial is in. What is the meaning of value of the
polynomial?

>> What is the 'n' you're thinking of here?
>
> The input of the problem is the source code of the program, preferably
> encoded as a control-flow graph or something like that. (I'm no expert
> of the subject)
>
> It's not four pointers.
> It seems you've been confusing alias analysis with the problem of
> determining whether two integer intervals overlap.

No, I've been confusing the question about whether or not std::copy<>
can determine whether it is safe to use memcpy() with whatever in the
world it is that you're discussing. That decision does not require alias
analysis, nor examination of the entire program; it can be made for
std::copy<T*,T*>(p,q,n) by using std::type_traits<T>.is_trivial and
std::less<T*>.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Florian Weimer on
* Mathias Gaunard:

> std::copy can't even call memcpy since the arguments are not
> guaranteed not to overlap, at best it can call memmove.

std::copy is undefined in this case (at least in C++98), so it's
perfectly fine to call memcpy.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Mathias Gaunard on
On 6 sep, 10:29, James Kuyper <jameskuy...(a)verizon.net> wrote:
>
> So you're saying that the traveling salesman problem is just as hard
> when 4 cities are involved as as when 100 are involved?

Yes.
Hardness depends on the complexity category, not the size of the
input.


> No, I've been confusing the question about whether or not std::copy<>
> can determine whether it is safe to use memcpy() with whatever in the
> world it is that you're discussing.

I was saying that determining it at compile-time requires alias
analysis, while you came in and confused that with determining that at
runtime.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: James Kuyper on
Mathias Gaunard wrote:
> On 6 sep, 10:29, James Kuyper <jameskuy...(a)verizon.net> wrote:
>> So you're saying that the traveling salesman problem is just as hard
>> when 4 cities are involved as as when 100 are involved?
>
> Yes.
> Hardness depends on the complexity category, not the size of the
> input.

OK, then the meaning you attach to the term "hard" is quite different
from any I've heard used before. In my understanding, the hardness of a
problem is a quantity that increases with the problem size; there must
be some term you use for this purpose, even if you don't call it
"hardness". My understanding is that the complexity categories describe
the asymptotic behavior of that function, as the size of the problem
gets large.

>> No, I've been confusing the question about whether or not std::copy<>
>> can determine whether it is safe to use memcpy() with whatever in the
>> world it is that you're discussing.
>
> I was saying that determining it at compile-time requires alias
> analysis, while you came in and confused that with determining that at
> runtime.

No, I didn't confuse compile-time determination with runtime
determination, I was confused by your insistence that the safety of
using memcpy() could not be determined at all, just because it couldn't
be determined at compile time, despite the fact that it's perfectly
straightforward to determine it at run time.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: James Kuyper on
Florian Weimer wrote:
> * Mathias Gaunard:
>
>> std::copy can't even call memcpy since the arguments are not
>> guaranteed not to overlap, at best it can call memmove.
>
> std::copy is undefined in this case (at least in C++98), so it's
> perfectly fine to call memcpy.

What is "this case"? The only thing we know about "this case" is that
the OP was considering using memcpy() rather than strcpy(). Do you know
of a case where use of strcpy() had defined behavior, and std::copy()
(with the appropriate length argument), has undefined behavior?

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]