user923005 said:
[...]
Or even in modern C:
void swap( void *a, void *b, size_t size )
{
char temp[size];
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
} [...]
For certain values of "elegant".
If there isn't enough space to allocate the temporary buffer, this
version invokes undefined behavior. In an alternative version using
malloc(), you can catch an allocation error and fall back to an
alternative technique.
If someone uses malloc() in an exchange function, they need to be
slapped[0], unless you are exchanging 5 GB x-ray images or some other
absurdity [in which case you would probably use a customized exchange
function just for that purpose].
Having an exchange function fail because not enough auto memory is
available is not more probable than having the C program fail in some
other function because not enough automatic storage is available.
Hence, if the technique is dangerous here, then C programs are
dangerous in general. The dreadful, dreary slowness of malloc() makes
this notion so unpalatable that the core dump is almost pleasant[1] by
contrast.
Using a VLA and risking undefined behavior if you run out of memory
(you could be swapping very large objects) isn't what I'd call
elegant. You could, I suppose, restrict the size of the objects beng
swapped.
Using a VLA is no more dangerous than using an object of the same size
as the VLA.
If we are using the function generically, that indicates that
somewhere in the program we are eventually going to refer to actual
objects to feed to our exchange function. How do we tend to use
exchange functions? Often (for instance) to sort things in a vector
or to reform a heap or to reorder a tree or something of that nature.
An exchange function is mathematically useless, unless there is some
kind of order implied. Ordering implies a collection of objects (e.g.
if there are only two of them, then actually exchanging them is a
waste of time). If the addition of a single temporary to automatic
memory is unsafe, then the program itself is unsafe. Certainly, we
are going to be manipulating collections of these things elsewhere in
the program.
If you want to use a temporary that's the full size of the objects
being swapped, malloc() is the only safe way to go. If malloc() isn't
acceptable, just swap one byte at a time.
Or do something clever like the Bentley / McIlroy sort I posted (which
tends to be a lot faster than swapping one byte at a time).
On the other hand, perhaps it really means that the C++ template is
even more superior than I ever imagined.
The reason I am kicking up such a fuss on this subject is that this
(exchange/compare sorts of operations) is the kind of thing that will
have a severe impact on performance (even on a vector in the ideal
case of selection sort which minimizes exchanges we will still have
exchanges proportional at least to N). Writing a bad exchange
function (and I consider an exchange function that calls malloc() and
free() a very, very bad one) will definitely have a very severe effect
on overall performance.
