By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,846 Members | 2,094 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,846 IT Pros & Developers. It's quick & easy.

Okay to move an object?

P: n/a

(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.
--

Frederick Gotham
Jun 26 '06 #1
Share this Question
Share on Google+
35 Replies


P: n/a
Frederick Gotham wrote:
(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-lit....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!

--
Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!
Jun 27 '06 #2

P: n/a
Frederick Gotham wrote:
(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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 27 '06 #3

P: n/a
In article <fw*******************@news.indigo.ie>,
Frederick Gotham <fg*******@SPAM.com> wrote:
(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.
Jun 27 '06 #4

P: n/a
Frederick Gotham wrote:
(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").

Jun 27 '06 #5

P: n/a
Kaz Kylheku posted:
Frederick Gotham wrote:

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.

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.)

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!

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 );
--

Frederick Gotham
Jun 27 '06 #6

P: n/a
wij
Frederick Gotham wrote:
(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/co...4c8b920c0521f3
IJ. Wang

Jun 27 '06 #7

P: n/a
"Frederick Gotham" <fg*******@SPAM.com> wrote in message
news:fw*******************@news.indigo.ie...

(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.
Jun 27 '06 #8

P: n/a
In article <Z3*******************@news.indigo.ie>,
Frederick Gotham <fg*******@SPAM.com> wrote:
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.)

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!

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 );


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.
Jun 27 '06 #9

P: n/a
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.net says...

[ ... ]
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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '06 #10

P: n/a
In article <MP************************@news.sunsite.dk>,
Jerry Coffin <jc*****@taeus.com> wrote:
I have to (for once) agree with Daniel


"for once" Jerry? Do I have a secret dissenter? :-)
Jun 27 '06 #11

P: n/a
Frederick Gotham wrote:
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.

Jun 27 '06 #12

P: n/a
"Daniel T." <da******@earthlink.net> wrote:
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. :-)
Jun 27 '06 #13

P: n/a
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.net says...
In article <MP************************@news.sunsite.dk>,
Jerry Coffin <jc*****@taeus.com> wrote:
I have to (for once) agree with Daniel


"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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '06 #14

P: n/a
Frederick Gotham wrote:
(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
Jun 27 '06 #15

P: n/a
In article <MP************************@news.sunsite.dk>,
Jerry Coffin <jc*****@taeus.com> wrote:
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.net says...
In article <MP************************@news.sunsite.dk>,
Jerry Coffin <jc*****@taeus.com> wrote:
I have to (for once) agree with Daniel


"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.


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.
Jun 27 '06 #16

P: n/a
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
Jun 27 '06 #17

P: n/a
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...?

--

Frederick Gotham
Jun 27 '06 #18

P: n/a
Frederick Gotham wrote:
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.


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.

--
Salu2

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
Jun 27 '06 #19

P: n/a
> 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).
Jun 27 '06 #20

P: n/a
Albo posted:

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.

The C++ Standard does such a thing already -- it has measures in place
which simply scorn "stupid" use of classes. Below is an example of code
which SHOULD work properly, but which the C++ Standard says need not work
properly, because it deems it to be "stupid" use of a class:
class ArbitraryClass {
public:

static unsigned counter;

ArbitraryClass()
{
++counter;
}

ArbitraryClass( const ArbitraryClass & )
{
++counter;
}
};

unsigned ArbitraryClass::counter = 0;

class Manipulator {
public:

~Manipulator()
{
if ( 2 == ArbitraryClass::counter ) return;

/* Now some gratuitous undefined behaviour: */

int *p;

*p = 42;
}
} global_object;

int main()
{
ArbitraryClass obj = ArbitraryClass();
}

The C++ Standard gives explicit permission for only one object of
ArbitraryClass to be constructed in the above code, and by implication,
decrees that it's "stupid" for someone to depend on an extra instance of
their class being created. As you put it, Albo, this certainly puts
limitations on what an object can make internally for his own purposes.
--

Frederick Gotham
Jun 27 '06 #21

P: n/a
Frederick Gotham wrote:
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).

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


You are aware of std::next_permutation, right?
e.g.

std::string s("rain");
std::sort(s.begin(), s.end());
do
{
std::cout << s << '\n';
}
while (std::next_permutation(s.begin(), s.end()));

In any case, for a permutations algorithm, isn't the fundamental
operation a swap rather than a move?

Tom
Jun 27 '06 #22

P: n/a
Frederick Gotham wrote:
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.


The C++ Standard does such a thing already -- it has measures in place

(snip)

It seems that we have different concepts of "arbitrary".

--
Salu2

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
Jun 27 '06 #23

P: n/a
Tom Widmer posted:

You are aware of std::next_permutation, right?
e.g.

std::string s("rain");
std::sort(s.begin(), s.end());
do
{
std::cout << s << '\n';
}
while (std::next_permutation(s.begin(), s.end()));

Where could I find an exhaustive and very detailed C++ library
reference... preferably with good example code? (Including the standard
library which is inherited from C).

This isn't the first time I've found myself writing code when I simply
could have used something in the standard library.

Also... to clarify something:

What is the STL and what does it stand for? I thought it was simply an
abbreviation of "Standard Library", but I think Alf corrected me earlier
as to the usage of the term.
--

Frederick Gotham
Jun 27 '06 #24

P: n/a
=?ISO-8859-15?Q?Juli=E1n?= Albo posted:
Frederick Gotham wrote:
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.


The C++ Standard does such a thing already -- it has measures in place

(snip)

It seems that we have different concepts of "arbitrary".

Vague, one-line posts are ineffectual.
The C++ Standard, if it wished, could also impose such a limitation as
"An object should not store its own address within itself, or the address
of a member object, or base object.". It could then implement a universal
swap algorithm quite elementarily as follows:

template<class T>
void swap( T &a, T &b )
{
unsigned char p_buf[sizeof(T)];

memcpy( p_buf, &a, sizeof(T) );

memcpy( &a, &b, sizeof(T) );

memcpy( &b, p_buf, sizeof(T) );
}
Instead of storing raw memory addresses within itself, the Standard could
encourage programmers to store offsets.
--

Frederick Gotham
Jun 27 '06 #25

P: n/a
Frederick Gotham wrote:
Tom Widmer posted:
You are aware of std::next_permutation, right?
e.g.

std::string s("rain");
std::sort(s.begin(), s.end());
do
{
std::cout << s << '\n';
}
while (std::next_permutation(s.begin(), s.end()));
Where could I find an exhaustive and very detailed C++ library
reference... preferably with good example code? (Including the standard
library which is inherited from C).


Here are a few:
http://www.dinkumware.com/manuals/
http://www.sgi.com/tech/stl/table_of_contents.html (STL only)
http://msdn.microsoft.com/library/de...nstlsample.asp

MSDN includes example code.
This isn't the first time I've found myself writing code when I simply
could have used something in the standard library.

Also... to clarify something:

What is the STL and what does it stand for? I thought it was simply an
abbreviation of "Standard Library", but I think Alf corrected me earlier
as to the usage of the term.


STL stands for "Standard Template Library", a library of algorithms,
iterators and containers developed by Stepanov and others at Bell labs
and HP (IIRC) and incorporated in slightly modified form into the C++
standard library. The "original" STL is still maintained separately from
the standard library version by SGI (see the link above).

Tom
Jun 27 '06 #26

P: n/a
Frederick Gotham wrote:
The C++ Standard, if it wished, could also impose such a limitation as
"An object should not store its own address within itself, or the address
of a member object, or base object.". It could then implement a universal
swap algorithm quite elementarily as follows:


Buy they don't do. Probably for a good reason, such as consider that a
requisite so strict will be unacceptable for many uses, and that is
undesirable for standard containers.

Better that arguing, you can make a reality check: implement a container
with such limitations and test in what cases is usable and how easy is to
check if a class meets the requisites.

--
Salu2

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
Jun 27 '06 #27

P: n/a
=?ISO-8859-15?Q?Juli=E1n?= Albo posted:
Frederick Gotham wrote:
The C++ Standard, if it wished, could also impose such a limitation
as "An object should not store its own address within itself, or the
address of a member object, or base object.". It could then implement
a universal swap algorithm quite elementarily as follows:


Buy they don't do. Probably for a good reason, such as consider that a
requisite so strict will be unacceptable for many uses, and that is
undesirable for standard containers.

Not if we write an "OffsetPointer" class that behaves exactly like a
domestic pointer.

I'll start off with some sample code. Here's a class which stores its own
address within itself (or the address of a member, etc.):

#include <cstddef>
#include <cstdlib>
#include <iostream>

class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

char *p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

int main()
{
StringStream ss;

ss.Append('H');
ss.Append('e');
ss.Append('l');
ss.Append('l');
ss.Append('o');
ss.Append('!');

ss.Print();

std::system("PAUSE");
}
If we were to re-locate an object of the StringStream class in memory, then
its "p_pos" member would become corrupted.
I propose to change the "p_pos" member from:

char *p_pos;

to:

OffsetPointer<char> p_pos;
but without changing anything else. Thus, the class's definition would
become:

#include <offp.hpp> /* Contains definition of OffsetPointer */
#include <cstddef>
#include <iostream>

class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

OffsetPointer<char> p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

And then I would implement the OffsetPointer class something like the
following:
#include <cstddef>
#include <cstdlib>
#include <iostream>

template<class T>
class OffsetPointer {
protected:

mutable T *p ;

mutable const OffsetPointer *old_this;

public:

OffsetPointer( T * const arg_p )
: old_this(this), p(arg_p) {}

OffsetPointer( const OffsetPointer &original )
: old_this(this), p(original.p) {}

/* old_this becomes refreshed when copy-constructed
or assigned. */

OffsetPointer &operator=( const OffsetPointer &rhs ) { p = rhs.p; }
protected:

void ValidateP() const
{
if ( this == old_this ) return;

if ( this > old_this )
{
std::size_t const moved_forward_bytes =
reinterpret_cast<const unsigned char*>(this)
- reinterpret_cast<const unsigned char*>(old_this);

p = reinterpret_cast<T*>(
const_cast<unsigned char*>(
reinterpret_cast<const unsigned char*>(p)
)

+ moved_forward_bytes );

}
else
{
std::size_t const moved_backward_bytes =
reinterpret_cast<const unsigned char*>(old_this)
- reinterpret_cast<const unsigned char*>(this);

p = reinterpret_cast<T*>(
const_cast<unsigned char*>(
reinterpret_cast<const unsigned char*>(p)
)

- moved_backward_bytes );
}

old_this = this;
}

public:

operator T* &() const
{
ValidateP();

return p;
}
};
class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

OffsetPointer<char> p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

template<class T>
void AdvanceObjectAndIncrementPointer( T * &p_obj )
{
std::memcpy( p_obj + 1, p_obj, sizeof(T) );

++p_obj;
}

int main()
{
unsigned char * const p_buf =
new unsigned char[ sizeof(StringStream) * 7 ];
StringStream *p_ss = new(p_buf) StringStream;

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('H');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('e');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('l');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('l');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('o');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('!');

p_ss->Print();
std::system("PAUSE");
/* Time for clean up: */

p_ss->~StringStream();
delete [] p_buf;
}
As you can see, it wouldn't be too complicated for C++ to adopt a policy of
"A class should be written in such a way that an object of it may be re-
located in memory without ill-effect".
--

Frederick Gotham
Jun 27 '06 #28

P: n/a
Frederick Gotham wrote:
The C++ Standard, if it wished, could also impose such a limitation
as "An object should not store its own address within itself, or the
address of a member object, or base object.". It could then implement
a universal swap algorithm quite elementarily as follows:

Buy they don't do. Probably for a good reason, such as consider that a
requisite so strict will be unacceptable for many uses, and that is
undesirable for standard containers.

Not if we write an "OffsetPointer" class that behaves exactly like a
domestic pointer.
I'll start off with some sample code. Here's a class which stores its own
address within itself (or the address of a member, etc.):


And then you force all programmers in the world to rewrote his classes using
your artifacts. And the same for any other thing incompatible with your
goal. I suspect that there are few people willing to accept such
incompatible changes in the C++ standard, just for the implementation of
some type of container that can be more efficient on some situations.

--
Salu2

Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
Jun 27 '06 #29

P: n/a

"Frederick Gotham" <fg*******@SPAM.com> wrote in message
news:1a*******************@news.indigo.ie...
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.


Why?

Your previous post made a similar statement:
(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.)


What prevents you from traversing your array of pointers (to characters, or
to whatever objects you choose) in order to output whatever information you
need? At what point do you actually need to move the objects (and why)?

-Howard



Jun 27 '06 #30

P: n/a
"Frederick Gotham" <fg*******@SPAM.com> wrote in message
news:c1*******************@news.indigo.ie...
=?ISO-8859-15?Q?Juli=E1n?= Albo posted:
Frederick Gotham wrote:
The C++ Standard, if it wished, could also impose such a limitation
as "An object should not store its own address within itself, or the
address of a member object, or base object.". It could then implement
a universal swap algorithm quite elementarily as follows:


Buy they don't do. Probably for a good reason, such as consider that a
requisite so strict will be unacceptable for many uses, and that is
undesirable for standard containers.

Not if we write an "OffsetPointer" class that behaves exactly like a
domestic pointer.

I'll start off with some sample code. Here's a class which stores its own
address within itself (or the address of a member, etc.):

#include <cstddef>
#include <cstdlib>
#include <iostream>

class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

char *p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

int main()
{
StringStream ss;

ss.Append('H');
ss.Append('e');
ss.Append('l');
ss.Append('l');
ss.Append('o');
ss.Append('!');

ss.Print();

std::system("PAUSE");
}
If we were to re-locate an object of the StringStream class in memory,
then
its "p_pos" member would become corrupted.
I propose to change the "p_pos" member from:

char *p_pos;

to:

OffsetPointer<char> p_pos;
but without changing anything else. Thus, the class's definition would
become:

#include <offp.hpp> /* Contains definition of OffsetPointer */
#include <cstddef>
#include <iostream>

class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

OffsetPointer<char> p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

And then I would implement the OffsetPointer class something like the
following:
#include <cstddef>
#include <cstdlib>
#include <iostream>

template<class T>
class OffsetPointer {
protected:

mutable T *p ;

mutable const OffsetPointer *old_this;

public:

OffsetPointer( T * const arg_p )
: old_this(this), p(arg_p) {}

OffsetPointer( const OffsetPointer &original )
: old_this(this), p(original.p) {}

/* old_this becomes refreshed when copy-constructed
or assigned. */

OffsetPointer &operator=( const OffsetPointer &rhs ) { p = rhs.p; }
protected:

void ValidateP() const
{
if ( this == old_this ) return;

if ( this > old_this )
{
std::size_t const moved_forward_bytes =
reinterpret_cast<const unsigned char*>(this)
- reinterpret_cast<const unsigned char*>(old_this);

p = reinterpret_cast<T*>(
const_cast<unsigned char*>(
reinterpret_cast<const unsigned char*>(p)
)

+ moved_forward_bytes );

}
else
{
std::size_t const moved_backward_bytes =
reinterpret_cast<const unsigned char*>(old_this)
- reinterpret_cast<const unsigned char*>(this);

p = reinterpret_cast<T*>(
const_cast<unsigned char*>(
reinterpret_cast<const unsigned char*>(p)
)

- moved_backward_bytes );
}

old_this = this;
}

public:

operator T* &() const
{
ValidateP();

return p;
}
};
class StringStream {
private:

static std::size_t const buflen = 64;

char buffer[buflen];

OffsetPointer<char> p_pos;

public:

StringStream() : p_pos( &*buffer ), buffer() {}

void Append( char const c )
{
if( p_pos != buffer + (buflen - 2) ) *p_pos++ = c;
}

void Print() const
{
std::cout << buffer << '\n';
}

};

template<class T>
void AdvanceObjectAndIncrementPointer( T * &p_obj )
{
std::memcpy( p_obj + 1, p_obj, sizeof(T) );

++p_obj;
}

int main()
{
unsigned char * const p_buf =
new unsigned char[ sizeof(StringStream) * 7 ];
StringStream *p_ss = new(p_buf) StringStream;

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('H');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('e');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('l');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('l');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('o');

AdvanceObjectAndIncrementPointer(p_ss);
p_ss->Append('!');

p_ss->Print();
std::system("PAUSE");
/* Time for clean up: */

p_ss->~StringStream();
delete [] p_buf;
}
As you can see, it wouldn't be too complicated for C++ to adopt a policy
of
"A class should be written in such a way that an object of it may be re-
located in memory without ill-effect".


You could achieve the same thing by using an int value as large as a
pointer.
Jun 28 '06 #31

P: n/a
Jim Langston posted:

You could achieve the same thing by using an int value as large as a
pointer.

Indeed.

But since I was going to be comparing the current "this" to the previous
"this", I decided to keep everything as pointers.

More than one way to skin a cat.
--

Frederick Gotham
Jun 28 '06 #32

P: n/a
I realize I'm coming late to the party but...

In article <e7**********@nntp.aioe.org>,
Tom Widmer <to********@hotmail.com> wrote:
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.
Two implementations (gcc versions 4 and up and CodeWarrior) have
non-memmovable implementations of:

list
map
multimap
set
multiset

gcc also has an experimental implementation of std::string (libstdc++v7)
which is not memmovable.

In article <fw*******************@news.indigo.ie>,
Frederick Gotham <fg*******@SPAM.com> wrote:
However, is it okay to move an object manually (i.e. by using memcpy or
memmove)?


I believe the OP will be very interested in this paper:

http://www.open-std.org/jtc1/sc22/wg...006/n2027.html

which, in a nutshell, is a proposal to standardize a procedure for doing
almost exactly (not quite but darn close) what the OP desires. This
proposal has been under development since mid 2001 and is in the late
stages of standardization for C++0X at this point. It is not yet
standard, or even in the working draft, but I have a reasonable hope
that it soon will be.

-Howard
Jun 28 '06 #33

P: n/a
Howard Hinnant wrote:
I realize I'm coming late to the party but...

In article <e7**********@nntp.aioe.org>,
Tom Widmer <to********@hotmail.com> wrote:

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.

Two implementations (gcc versions 4 and up and CodeWarrior) have
non-memmovable implementations of:

list
map
multimap
set
multiset

gcc also has an experimental implementation of std::string (libstdc++v7)
which is not memmovable.


Ahh, any implementation that stores the root or head node directly in
the container won't be memmoveable; I assume that's the issue here. For
std::string I can only assume that it would be down to an SSO
implementation where the m_begin pointer points either to dynamic
storage or to the internal buffer.

In article <fw*******************@news.indigo.ie>,
Frederick Gotham <fg*******@SPAM.com> wrote:

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

I believe the OP will be very interested in this paper:

http://www.open-std.org/jtc1/sc22/wg...006/n2027.html

which, in a nutshell, is a proposal to standardize a procedure for doing
almost exactly (not quite but darn close) what the OP desires. This
proposal has been under development since mid 2001 and is in the late
stages of standardization for C++0X at this point. It is not yet
standard, or even in the working draft, but I have a reasonable hope
that it soon will be.


Yes, this is of course the best solution for the future.

Tom
Jun 29 '06 #34

P: n/a
In article <e8**********@nntp.aioe.org>,
Tom Widmer <to********@hotmail.com> wrote:
Two implementations (gcc versions 4 and up and CodeWarrior) have
non-memmovable implementations of:

list
map
multimap
set
multiset

gcc also has an experimental implementation of std::string (libstdc++v7)
which is not memmovable.


Ahh, any implementation that stores the root or head node directly in
the container won't be memmoveable; I assume that's the issue here. For
std::string I can only assume that it would be down to an SSO
implementation where the m_begin pointer points either to dynamic
storage or to the internal buffer.


<nod> Right on both counts.

-Howard
Jun 29 '06 #35

P: n/a
In article <yq*******************@news.indigo.ie>, fg*******@SPAM.com
says...

[ ... ]
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:
[ ... ]
(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.)
You don't really need to do any such thing. You could just write
things out in the order defined by the pointers and be done with it.

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
template <class T>
class permutation {
std::vector<T const *> data;
typedef std::vector<T const *>::const_iterator it;
public:
// Warning: since this stores pointers to the data passed as its
// input, that data MUST remain accessible throughout the life of
// the permutation object.
permutation(T const *input) {
while (*input)
data.push_back(input++);
}

bool next() {
return std::next_permutation(data.begin(), data.end());
}

std::ostream &write(std::ostream &os) const {
for (it i=data.begin(); i!=data.end(); ++i)
os << **i;
return os;
}

friend std::ostream &
operator<<(std::ostream &os, permutation const &p) {
return p.write(os);
}
};

int main() {
char input[] = "rain";

permutation<char> p(input);

do {
std::cout << p << "\t";
} while (p.next());
return 0;
}

For the moment, I've used pointers, because that's what you mentioned
using. In reality, you probably want to use iterators instead, which
would (for example) make it relatively natural to pass start/end
iterators, instead of assuming something like a C-style string as
I've done above (that was just easy because I happened to be using it
with a C-style string).
This processing was elementary because I was dealing with char's, and so
I could copy and move them around willy-nilly.
Which you're also pretty much free to do as long as you're just
copying pointers or iterators. Though it's never explicitly stated in
the standard, it pretty much takes for granted that playing with
iterators is cheap.
I then decided to expand on my algorithm. I wanted to turn it into a
template so it would work with objects too.
The code above requires that the objects define operator<<, but not
much beyond that.

[ ... ]
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.
Actually, if you were going to play with objects instead of pointers
(or iterators) to them, I think swap really would be the way to go.
In fact, it's exactly what next_permutation uses.
I've had another idea: Maybe document that the objects in question must
be movable, and I'll just go ahead and use memcpy...?


I've had a different idea: if you really want to use memcpy, start
with a template that works for all types, and then use memcpy in
specializations you know are safe to handle that way. If you do this,
be sure to profile a bit first though -- at least to me, it's not
immediately obvious that such a specialization will provide drastic
improvements for very many types.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 30 '06 #36

This discussion thread is closed

Replies have been disabled for this discussion.