Okay to move an object?

[Frederick Gotham]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?

I have an algorithm for rotating an array. It turns:

A B C D E F G

into:

B C D E F G A

and if run a second time, that would become:

C D E F G A B


I intend for it to be used on anything from and array of char's, to an
array of vector's.

Is there anything wrong with the way it moves objects around?

Here's some sample code:


#include <iostream>
using std::cout;

#include <cstdlib>
using std::memcpy;

#include <cstring>
using std::memmove;


template<class T>
void RotateArrayOnce( T * const p_start, T * const p_over )
{
unsigned long const len = p_over - p_start;

unsigned char * const p_temp_storage = new unsigned char[ sizeof(T)
];

memcpy( p_temp_storage, p_start, sizeof(T) );

memmove( p_start, p_start + 1, sizeof(T) * (len - 1) );

memmove( p_over - 1, p_temp_storage, sizeof(T) );

delete [] p_temp_storage;
}

int main()
{
char buffer[] = "ABCDE";

cout << buffer << '\n';

RotateArrayOnce(buffer, *(&buffer + 1) - 1 );

cout << buffer << '\n';

RotateArrayOnce(buffer, *(&buffer + 1) - 1 );

cout << buffer << '\n';

std::system("PAUSE");
}


At first thought, I don't see how it could be a problem to simply move an
object in memory (assuming the target location is suitably aligned).

Only thing I can see which could make things go awry is if the object
kept its own address stored within it for some reason.

 

[Phlip]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

std::vector _are_ actual arrays. ;-)

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?

That is, indirectly, a FAQ.

http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.7
"What is a 'POD type'?"

I intend for it to be used on anything from and array of char's, to an
array of vector's.

Are vectors PODs?

using std::memcpy;

You might try some member of the std::copy() family. They are templated, so
they will drill down to your actual type and invoke its copy operations.

If you stick with memcpy, you are performing the equivalent of
reinterpret_cast<char *>(&element) on each element. 'reinterpret_cast<>' is
bad, and should be avoided, including all similar situations that secretly
throw away type information.

And you have not yet made any case for not using std::vector, besides you
have stuck with functions that you understand. Don't reinvent wheels while
on the clock!

 

[Victor Bazarov]

(Before I begin, please don't suggest to me to use "std::vector"
rather than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy
or memmove)?

Huh? If you understand that we "have to copy an object properly",
why ask if it's OK to do it improperly?

I have an algorithm for rotating an array. It turns:

A B C D E F G

into:

B C D E F G A

and if run a second time, that would become:

C D E F G A B


I intend for it to be used on anything from and array of char's, to an
array of vector's.

Is there anything wrong with the way it moves objects around?

Yes. Unless your objects are of a POD type, using 'memcpy' or 'memmove'
on them is *undefined*. Usually it means that it's impossible to define
the consequences of that action without imposing too many limitations on
the language implementations.

V

 

[Daniel T.]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

Why? Would it be OK to suggest a method of accomplishing what you want
to accomplish?

template < typename FwIt >
void RotateArrayOnce( FwIt begin, FwIt end ) {
std::rotate( begin, begin + 1, end );
}

Unless you are doing a homework assignment, you are wasting your time.

If you *are* doing a homework assignment, the what you need to do is
walk the first element of the array down using std::swap.

 

[Kaz Kylheku]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?

Not in general, because objects may be entangled in relationships which
are hinged on their address.

An object may contain pointers to parts of itself. For instance, an
object representing a buffered I/O stream over a file might contain a
buffer, as well as a pointer to the current read position within the
buffer rather than an index. If you copy the object, its pointer still
points within the original object.

There may be other objects which know about that object, and refer to
it by its address. For instance, a node in a binary tree has a parent
which points to it via a child pointer. A naive copy of the object will
retain that parent, but that parent still points to the original object
as its child. Treating this node as the root of a subtree could wreck
the original tree, depending on what kind of operation is attempted.

C++ polymorphic objects may have this kind of information in them, as a
way of implementing the object system. For instance, the derived part
of an object could have a hidden back-pointer to a base class part or
vice versa. So you cannot treat these types of objects as raw memory to
be copied around.

Even plain C-like structures cannot necessarily be treated that way.
Although the C++ implementation may allow a bit copy, whether or not
that makes sense still depends on the meaning of that data type and how
it relates to other data.

For instance FILE streams in the Standard C library are not C++
classes, but it's still forbidden to copy them.

Another example is the va_list type, which can only be copied by
va_copy, not by assignment.

Only thing I can see which could make things go awry is if the object
kept its own address stored within it for some reason.

Or if that object is part of a larger data structure which knows about
that object's address!

Imagine if you populated the array with the nodes of a binary tree and
ran your sorting algorithm. It would scramble the link pointers within
that tree, destroying the whole thing.

You'd have to run some kind of "tree repair" afterward to rebuild the
structure. But then your sorting algorithm would no longer be generic:
it would work specifically with objects which may be bitwise copied
/provided/ that a special fixup is invoked afterward.

C++ doesn't provide any standard way to fix up the internal information
of class objects which may have such information (i.e. other than
"plain old datatypes").

 

[Frederick Gotham]

Kaz Kylheku posted:

Not in general, because objects may be entangled in relationships which
are hinged on their address.

The reply I was waiting for.

An object may contain pointers to parts of itself. For instance, an
object representing a buffered I/O stream over a file might contain a
buffer, as well as a pointer to the current read position within the
buffer rather than an index. If you copy the object, its pointer still
points within the original object.

While I had fathomed that this was possible, I was unsure as to whether
it was "acceptable".

Are you saying that it is indeed acceptable for an object to store its
own address within itself (or the address of a member object, or base
class object)? If so, I'll have to take this into account when moving the
object's bytes to another location in memory.

There may be other objects which know about that object, and refer to
it by its address.

When the "RotateArrayOnce" function is invoked, I can assume that nothing
will be depending upon its original address. (It's the programmer's
responsibility to ensure this before invoking my reusable code).

After all, the programmer would not re-arrange an array if the addresses
of the array's elements were of significance.

For instance, a node in a binary tree has a parent
which points to it via a child pointer. A naive copy of the object will
retain that parent, but that parent still points to the original object
as its child. Treating this node as the root of a subtree could wreck
the original tree, depending on what kind of operation is attempted.

Again, the programmer must ensure that they are "allowed" to re-arrange
the objects.

C++ polymorphic objects may have this kind of information in them, as a
way of implementing the object system. For instance, the derived part
of an object could have a hidden back-pointer to a base class part or
vice versa. So you cannot treat these types of objects as raw memory to
be copied around.

I see. (Again we're back to an object storing its own address within
itself).

Even plain C-like structures cannot necessarily be treated that way.

Why is that? Is it because it's also acceptable for a C-like structure to
store its own address within itself?

Although the C++ implementation may allow a bit copy, whether or not
that makes sense still depends on the meaning of that data type and how
it relates to other data.

I see. (Again, self-addressing).

For instance FILE streams in the Standard C library are not C++
classes, but it's still forbidden to copy them.

Another example is the va_list type, which can only be copied by
va_copy, not by assignment.

Yes... but I'm not real copying an object; all I'm doing is moving it.
I'll try to explain:

Whereas the object's bytes may have existed at address 0x00000012, it now
exists at address 0x00000008.

If I were to attempt, subsequent to the copy, to access the data at the
original address of 0x00000012, THEN I'd have a problem... but I do not
do this -- I choose to discard the data at the original address.

The net effect is a simple move of data in memory, nothing more.

(It actually reminds me of the old-fashioned way of moving a file:
You copy it, then delete the original.
Even if it's forbidden to have more than one copy of the file, it doesn't
matter... because I destroy the original immediately, ensuring that the
original is never accessed subsequent to being copied.)

Or if that object is part of a larger data structure which knows about
that object's address!

Again, I don't need to worry about this, because the programmer must
supply the function with an array which is "re-arrangeable".

Thank you very much Kaz for your help.

So this brings me on to my next question:


How do I (legitimately) move an object in memory?


Some people have suggested that I use "std::swap", but then I'd need to
have another object to swap it with... but that's not what I want -- I
simply want to move it into another raw memory location, without the need
for a guinea pig to swap it with.

Maybe a Standard library function like:

template<class T>
void MoveObjectInMemory( T &obj, unsigned char *p_destination );

 

[wij]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?

...

The discussions might help.
http://groups.google.com.tw/group/c...20c0521f3?q=swap_void&rnum=2#684c8b920c0521f3


IJ. Wang

 

[Jim Langston]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?

I have an algorithm for rotating an array. It turns:

A B C D E F G

into:

B C D E F G A

and if run a second time, that would become:

C D E F G A B


I intend for it to be used on anything from and array of char's, to an
array of vector's.

Is there anything wrong with the way it moves objects around?

Here's some sample code:


#include <iostream>
using std::cout;

#include <cstdlib>
using std::memcpy;

#include <cstring>
using std::memmove;


template<class T>
void RotateArrayOnce( T * const p_start, T * const p_over )
{
unsigned long const len = p_over - p_start;

unsigned char * const p_temp_storage = new unsigned char[ sizeof(T)
];

memcpy( p_temp_storage, p_start, sizeof(T) );

memmove( p_start, p_start + 1, sizeof(T) * (len - 1) );

memmove( p_over - 1, p_temp_storage, sizeof(T) );

delete [] p_temp_storage;
}

int main()
{
char buffer[] = "ABCDE";

cout << buffer << '\n';

RotateArrayOnce(buffer, *(&buffer + 1) - 1 );

cout << buffer << '\n';

RotateArrayOnce(buffer, *(&buffer + 1) - 1 );

cout << buffer << '\n';

std::system("PAUSE");
}


At first thought, I don't see how it could be a problem to simply move an
object in memory (assuming the target location is suitably aligned).

Only thing I can see which could make things go awry is if the object
kept its own address stored within it for some reason.

Consider a class that stores a pointer into a buffer. It creates a char
array either dynamically or statically, then stores a pointer at the current
position. To copy this class it would need a copy constructor, and would
also need an assigment operator for some uses.

Typically, you can not memcpy any object that has or needs a custom copy or
assigment operator. Look up the "rule of three", sorry, don't have a link
but it's in the FAQ.

memcpy should work for any POD (Plain old data) because POD does not need or
have custom copy and assigment operators. The correct way to do it would be
to invoke the classes copy operator.

 

[Daniel T.]

For instance FILE streams in the Standard C library are not C++
classes, but it's still forbidden to copy them.

Another example is the va_list type, which can only be copied by
va_copy, not by assignment.

Yes... but I'm not real copying an object; all I'm doing is moving it.
I'll try to explain:

Whereas the object's bytes may have existed at address 0x00000012, it now
exists at address 0x00000008.

If I were to attempt, subsequent to the copy, to access the data at the
original address of 0x00000012, THEN I'd have a problem... but I do not
do this -- I choose to discard the data at the original address.

The net effect is a simple move of data in memory, nothing more.

(It actually reminds me of the old-fashioned way of moving a file:
You copy it, then delete the original.
Even if it's forbidden to have more than one copy of the file, it doesn't
matter... because I destroy the original immediately, ensuring that the
original is never accessed subsequent to being copied.)

Or if that object is part of a larger data structure which knows about
that object's address!

Again, I don't need to worry about this, because the programmer must
supply the function with an array which is "re-arrangeable".

Thank you very much Kaz for your help.

So this brings me on to my next question:


How do I (legitimately) move an object in memory?


Some people have suggested that I use "std::swap", but then I'd need to
have another object to swap it with... but that's not what I want -- I
simply want to move it into another raw memory location, without the need
for a guinea pig to swap it with.

Maybe a Standard library function like:

template<class T>
void MoveObjectInMemory( T &obj, unsigned char *p_destination );
[/QUOTE]

Suddenly the requirements change. Before you wanted to swap objects now
you want to move an object to some specific memory location. Your design
is deeply flawed, but it can be done. Placement new and the copy
constructor is the way to go in this case.

 

[Jerry Coffin]

[ ... ]

Suddenly the requirements change. Before you wanted to swap objects now
you want to move an object to some specific memory location. Your design
is deeply flawed, but it can be done. Placement new and the copy
constructor is the way to go in this case.

I have to (for once) agree with Daniel: it sounds like your design is
deeply flawed. How about if we go back to somewhere close to the
beginning, and you tell us what you're really trying to accomplish
here? It seems to me that we're putting the cart before the horse,
trying to figure out how to do things before we figure out what
should really be done in the first place.

 

[Daniel T.]

I have to (for once) agree with Daniel

"for once" Jerry? Do I have a secret dissenter?

 

[Kaz Kylheku]

Are you saying that it is indeed acceptable for an object to store its
own address within itself (or the address of a member object, or base
class object)? If so, I'll have to take this into account when moving the
object's bytes to another location in memory.

Of course it's acceptable. Not only that, but it's common practice.

You can't take that into account in general, because objects are
opaque. Each object has a different set of rules for copying that
object. For some objects, the rule is simply that the object is not
copyable.

Objects are encapsulated in C++. If there isn't a copy constructor
provided, then you'd have to go behind the scenes, and break the
encapsulation.

The general case of this problem is intractable.

But there is also another problem: memory copying objects is a waste of
computing time. In general, programming is done by leaving objects
where they are and moving around only references to these objects. This
is so entrenched in computing that some programming languages only have
reference variables for objects that do not fit into a word of memory.
Those objects are never moved (except, perhaps, by garbage collection).

In C++ reference variables are emulated using pointers. (There are also
specially attributed values called references, but these are not
variables).

If you have a set of objects and you want to put them into an array and
shuffle that array, you should make it an array of pointers to these
objects. You move the pointers, and that pointer array then gives you a
rearranged /view/ on these objects, which actually stayed exactly where
they were.

Moreover, those objects don't have to be allocated in a contiguous
region of memory, either!

When the "RotateArrayOnce" function is invoked, I can assume that nothing
will be depending upon its original address. (It's the programmer's
responsibility to ensure this before invoking my reusable code).

But when programmers learn about that responsibility, they might not be
reusing that code.

After all, the programmer would not re-arrange an array if the addresses
of the array's elements were of significance.

Ah but the programmer /could/ if the array only held pointers to the
objects.

 

[Daniel T.]

template < typename FwIt >
void RotateArrayOnce( FwIt begin, FwIt end ) {
std::rotate( begin, begin + 1, end );
}

There's a flaw in the code above, it will only work with random access
iterators, not forward iterators. Sorry about that, the fix is simple
enough though that I will leave it as an exorcise for the reader.

 

[Jerry Coffin]

"for once" Jerry? Do I have a secret dissenter?

I didn't think it was any secret -- at least to my recollection, just
about every time we've exchanged posts, it seems like we've been in
serious disagreement.

 

[Tom Widmer]

(Before I begin, please don't suggest to me to use "std::vector" rather
than actual arrays.)

I understand that an object can have resources (e.g. dynamically
allocated memory), and so we have to copy an object properly via copy-
construction rather than using memcpy.

However, is it okay to move an object manually (i.e. by using memcpy or
memmove)? [snip]
At first thought, I don't see how it could be a problem to simply move an
object in memory (assuming the target location is suitably aligned).

Only thing I can see which could make things go awry is if the object
kept its own address stored within it for some reason.

Formally, you are allowed to memmove POD objects only. POD objects can't
have base classes, constructors, destructors or virtual functions (nor
members like that, nor reference nor const members). Basically, C style
structs and built in types are POD.

However, one can write non-standard code to memmove any object whose
copy constructor doesn't update any pointer that points within the
copied object (including hidden pointers due to virtual base classes).
This means in practice that you can move almost anything, as long as it
doesn't have any virtual base classes or explicit handling of internal
pointers. For example, moving std::containers (at least ones using
std::allocator) works fine on implementations that I'm aware of.

If you're doing this, obviously great care is required (I'd go as far as
to require that an explicit is_memmoveable<T> traits template be used to
enable the optimization for those classes and templates that support
it), and you need to be aware that your code is not standards compliant,
and possibly not portable to some compilers.

Tom

 

[Daniel T.]

I didn't think it was any secret -- at least to my recollection, just
about every time we've exchanged posts, it seems like we've been in
serious disagreement.

Well, that's in the philosophy and atheism newsgroups. I don't think
we've had any serious disagreements about how C++ works have we? I can't
find any via google at least.

 

[Frederick Gotham]

Kaz Kylheku posted:

If you have a set of objects and you want to put them into an array
and shuffle that array, you should make it an array of pointers to
these objects. You move the pointers, and that pointer array then
gives you a rearranged /view/ on these objects, which actually stayed
exactly where they were.

I have already taken the "array of pointers" route... but I still at some
point need to create a tangible array.

Moreover, those objects don't have to be allocated in a contiguous
region of memory, either!

Yes, I exploit this.


(I've put a more extensive reply elsewhere in the thread.)

 

[Frederick Gotham]

Jerry Coffin posted:

I have to (for once) agree with Daniel: it sounds like your design is
deeply flawed. How about if we go back to somewhere close to the
beginning, and you tell us what you're really trying to accomplish
here? It seems to me that we're putting the cart before the horse,
trying to figure out how to do things before we figure out what
should really be done in the first place.

Okay... here's how it all began.

I started out by writing code which would give all the permutations of
the order of letters in a word (actual human spoken word, not computer
word).

So, if you inputed "rain", you got back:

rain ainr ianr nair
rani airn iarn nari
rian anir inar niar
rina anri inra nira
rnai arin iran nrai
rnia arni irna nria


(Internally, my code works with an array of pointers, but there comes a
point when a tangible array needs to be created in order to print the
words to screen.)

This processing was elementary because I was dealing with char's, and so
I could copy and move them around willy-nilly.

I then decided to expand on my algorithm. I wanted to turn it into a
template so it would work with objects too.

I do not intend to copy any objects, but rather re-arrange them in
memory.

I know that it's a no-no to do a "shallow copy" on an object (e.g. by
using memcpy), but I thought that it would be okay in this case because
I'm performing a move rather than a copy, and so no resources would get
double-used. However, it seems that this route is not viable because an
object may store its own address within itself for particular reasons.

So basically I just want to re-arrange an array of objects in memory...
but "swap" wouldn't be the way to go, because I'm not performing a one-
for-one swap.

Of course, I have the option of swapping with a dummy object, but that
will be my last resort (I'm trying to keep efficient).

I've had another idea: Maybe document that the objects in question must
be movable, and I'll just go ahead and use memcpy...?

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

While I had fathomed that this was possible, I was unsure as to whether
it was "acceptable".

Are you saying that it is indeed acceptable for an object to store its
own address within itself (or the address of a member object, or base
class object)? If so, I'll have to take this into account when moving the
object's bytes to another location in memory.

It is unacceptable that you put arbitrary limitations on what an object can
make internally for his own purposes, just to make your container easier to
program. Nobody will use such a container.

 

[Christopher Dearlove]

So basically I just want to re-arrange an array of objects in memory...

but "swap" wouldn't be the way to go, because I'm not performing a one-
for-one swap.

If it's an expensive object to copy (maybe only if it's a very expensive
object to copy) you could use a list rather than an array and splice.
Of course then you need your algorithm that finds the re-arrangements
to use only bidirectional iterators, not random iterators (or indices).