The fear of the misterious

To be human is to fear what's unknow or uncertain. It's not surprising that there is wide-spread fear about memcpy() on a class object, or its effect on v-table on different implementations. Because most people simply do not know what's going on underneath.

There is nothing misterious about v-table. They are merely class data member(s), in the form of function pointers, of the base class where the virtual function(s) is(are) declared. They are part of the base class, just like the rest of class data members, although they are not quite as visible. So, yes, the v-table do gets copied over when you are copying or moving objects.

In doing object sorting, no object creation or destruction should be involved. We are just moving objects around from one memory location to another location.

It is highly likely that by merely shifting an object in the memory would not change the property of the object. The object should look just the same before and after the shift. In such case it is perfectly OK to just memcpy to swap objects or move them to a different location.

If in the rare case, the object's property DO depend on its memory location. Then such objects can not be copied, and no proper copy constructor can be written. Because you would have to copy the object into exactly the same memory location to make it look and behave exactly the same!!!

In such rare cases, qsort() would not work properly, but neither std::sort() would work. Since std::sort() requires an appropriate copy constructor, but I already said no proper copy constructor can be written since once the object is copied to a different location, it no longer behave the same even every thing else is the same!!!

Quote:

---

There is nothing misterious about v-table. They are merely class data member(s), in the form of function pointers, of the base class where the virtual function(s) is(are) declared. They are part of the base class, just like the rest of class data members, although they are not quite as visible. So, yes, the v-table do gets copied over when you are copying or moving objects.

---

There is nothing in the ANSI ISO Standard that says virtual functions are implemented this way. Given just that, the rest of what you say is moot.

Since myself and others have tried to relay to you that looking at underlying code is not how to determine the rules of ANSI C++, I will post your above claim about memcpy() and qsort() to comp.lang.c++ and comp.lang.c++.moderated newsgroup and post the responses to it here. If not for your knowledge, then for others to read.

For those who have access to these newsgroups, the thread is titled:

"memcpy() on objects is safe??"

Regards,

Paul McKenzie

Well. here is one response already.

Quote:

---

----------------------------------------------
> I have someone on another forum who has made the following claim about
> objects and usage of memcpy(), more importantly, usage of qsort() on
> objects.
> Here is the claim:
> ------------ CUT HERE -------------------------
> In doing object sorting, no object creation or destruction should be
> involved. We are just moving objects around from one memory location to
> another location.
>
> It is highly likely that by merely shifting an object in the memory
> would not change the property of the object. The object should look just
> the same before and after the shift. In such case it is perfectly OK to
> just memcpy to swap objects or move them to a different location.
>

Wrong.

Standard says:

"For any object (other than a base-class subobject) of POD
type T, whether or not the object holds a valid value of type T,
the underlying bytes (1.7) making up the object can be copied
into an array of char or unsigned char.
If the content of the array of char or unsigned char is copied
back into the object, the object shall subsequently hold its
original value." (3.9/2)

There are defect reports on this wording, particulary regarding
PODs with non-static "const" members (proposed resolution is to
remove the above guarantee from such PODs), but the intent
remains the same:

Standard does not give such guarantees for non-POD types.

Furthermore, Standard says:

"An object of POD type shall occupy contiguous bytes
of storage" (1.8/5)

There is no such guarantee for non-POD types.

And the last (but not the least): Standard says:

"A pointer to a POD-struct objects, suitably converted using
a reinterpret_cast, points to its initial member (or if that member is
a bit-field, then to the unit in which it resides) and vice versa.
[Note: there might therefore be unnamed padding within a POD-struct
object, but not at its beginning, as necessary to achieve appropriate
allignment.]" (9.2/17)

There is no such requirement for non-PODs.


> If in the rare case, the object's property DO depend on its memory
> location. Then such objects can not be copied, and no proper copy
> constructor can be written.

Wrong.

Consider so-called "base-pointers", like this one
(everything is snipped, but I hope that idea is clear):

// _not_ intended to compile, just a sketch

ptrdiff_t pointer_to_offset(const void* base, const void* p);

template<typename T>
T* offset_to_pointer(const void* base, ptrdiff_t offset);

template<typename T>
struct based_ptr
{
based_ptr( T* p_ )
: p( pointer_to_offset(this, p_) {}

based_ptr( const based_ptr& p_ )
: p( pointer_to_offset(this, (T*)p_ ) {}

based_ptr& operator= ( const based_ptr& p_ )
{ p= pointer_to_offset(this, (T*)p_ ); return *this; }

based_ptr& operator= ( T* p_ )
{ p= pointer_to_offset(this, p_ ); return *this; }

operator T* () const
{ return offset_to_pointer<T>(this,p); }

T* operator -> () const
{ return offset_to_pointer<T>(this,p); }

T& operator -> () const
{ return *offset_to_pointer<T>(this,p); }

private:
ptrdiff_t p;
};

Such "pointers" are helpful when doing some low-level tricks,
and they can be easily made "Assignable", "Comparable" etc.

Note that they _do_ have proper and correct copy constructor's
and assignment operator's semantics.

If you implement based pointers (or any other such classes)
properly, you can use them in containers, perform
std::sort or any other algorithms etc etc

(Indeed, offset_to_pointer<T> and pointer_to_offset cannot
be written portably, they are implementation/platform-specific
operations, and there might be platforms where these operations
is impossible to implement. But this is other issue.)

> Because you would have to copy the object
> into exactly the same memory location to make it look and behave exactly
> the same!!!
>

Nonsense.

> In such rare cases, qsort() would not work properly, but neither
> std::sort() would work.

Wrong.
std::sort() will work correctly with containers of the above pointers,
while qsort() will indeed corrupt everything.

> Since std::sort() requires an appropriate copy
> constructor, but I already said no proper copy constructor can be
> written since once the object is copied to a different location, it no
> longer behave the same even every thing else is the same!!!

Wrong.

> --------------- CUT HERE --------------------------------------
>
> Excusing the typos, can anyone here comment on the above? This all
> started with an argument over whether qsort() is safe to use on all
> objects, as opposed to always using std::sort().
>

qsort() is unsafe, it knows nothing of C++ objects, and it can be used
only with PODs without non-static const members.

memcpy() is unsafe, it knows nothing of C++ objects, and it can be used
only with PODs without non-static const members.

std::sort() is safe to use, as long as all C++ standard library requirements
are met.


Hope it make things clearer,

Sincerely,

Ruslan Abdikeev
Brainbench MVP for Visual C++
http://www.brainbench.com
------------------------------------------------------------------------

---

Regards,

Paul McKenzie

What does "POD" stand for?

POD --> Plain Old Data.

Examples are char, int, long, double, float.

Regards,

Paul McKenzie

Thanks, I'd never seen that before (but as non english,...)

Let's first clarify the POD (Plain Old Data) and none-POD myth.

First there is no distinction between "POD" and "none-POD". For any complicated class you can think about, they can be boiled down to base classes, "none-POD" data object members and POD data members. And each of the base class or "none-POD" member can be further taken apart into smaller components. Continue this process down, eventually every thing is composed of just POD data members.

All classes can be boiled down to just POD data members and nothing else

We have already seen that qsort() works on array of classes with std::string or std::vector and other class members. Is such class POD or none-POD?

I made the assertion that if an object's state or property depends on its own memory location, then such object can not be properly copied. Some one cited the base_pointer example. Unfortunately this example exactly shows why such object can not be copied. You think your copy constructor works. But it doesn't!

Let's say your class contains a direct pointer pointing to the n'th char of a char array within the class. And there is a function call to get that pointer. The caller can use that pointer to do some low level data manipulation efficiently. And when you copy objects of this class around, you adjust that pointer so it still points to the correct char in the char array of the new object. Does it seem to be OK?

It's NOT OK. Let's say a piece of code calls to get that pointer, and decides to store the pointer for later usage. And let's say the class object is the first object stored in a vector. And now you push one more object into the vector, and it finds it needs to do a memory reallocation to be able to contain more objects, and so all objects are "properly" copied to their new location. Every thing works so far. But when the code who stored the previous pointer comes back to manipulate the data of the first object. Bom! Access violation! The first object of the vector was copied from the original first object of the vector. But unfortunately the location is changed so the old pointer no longer works.

What does that tell you? It tells you what I already told you. If an object's property or behavior depends on its own location in any way at all, such object simply can not be copied over. No copy constructor can be written for such animal.

Back to v-table, granted the standard doesn't say any thing how it should be implemented. But v-table is part of the property of a class object, right? Each instance of the class object will have its OWN copy of the v-table. And I do not see any practical and sensible way of implementing it, other than put the v-table together with the rest of class members to form a chunk of continuous memory block which is the class object. Try to do a sizeof() of the class, you will see that it counts in the size of the v-table, in addition to all other none-static and none-cost data members.

Now when it comes to none-static const class members. Its implementation is not specified. It could be implemented in one of three ways. 1.No storage is allocated for it and it is used directly where ever it is referenced. 2.Implemented like a const static member. 3.Implement just like a regular data member but modification of this value is prohibited.

When copying object using memcpy(), in the above case 1 or 2, it will not be copied, nor will it needs to, so it is not an issue.

In the above case 3.We are some how violating the definition of const by writting a value over a const variable. In principle we could be doomed if the const value is allocated in a write-protected memory location. In practice, the only sensible way of implementation would be allocate regular memory for the variable, together with the rest of class members. There simply is no feasible way to put this variable away in a different memory location. Remember we are talking about case 3, where each instance of the class has a separate copy of the const data member.

In summary, the widespread fear of applying qsort() on none-POD object arrays is un-warranted. I am not saying it always works. As I pointed out already, for objects which depends on its own location, qsort() would not work, But neither std::sort in such case.

Again, standard says nothing about what you stated. The ANSI standard talks about language rules, not low-level details. If it were the case then why doesn't it include all the cases of implementation that you mentioned? There isn't even a suggestion of how something is implemented low-level. POD and non-POD type is a myth? Now the ANSI standard is wrong?

The ANSI ISO standard is over 700 pages, you would think they would have room for your speculative ideas on how something is implemented, but they didn't.

It's amazing how to you every single C++ expert that can be named is wrong, every one from the inventor of the language (Stroustrup) to the chair of the ANSI C++ standardization committee, to even the ANSI standard itself. I'd stick to what the experts in the language have to say (and hopefully others will to).

I posted your follow-up. I would suggest you take at least a peek there.

Regards,

Paul McKenzie

Paul:
Do you accept the fact that there exists none-copyable classes. Do you agree that such animal exists at all? Do you agree that it is impossible to write copy constructor for such classes and hence std::sort() would not work?

Who said vtable must be implemented in the form of continous memory, it can be implemented in the form of link list. Because Standard doesnt say anything about this. Why not you at least take a look at C++ Standard to clear lots of your problems.

Quote:

---

Originally posted by Zeeshan
Who said vtable must be implemented in the form of continous memory, it can be implemented in the form of link list. Because Standard doesnt say anything about this. Why not you at least take a look at C++ Standard to clear lots of your problems.

---

Zeeshan, why fork over $18 US for a document that's wrong ;)

Regards,

Paul McKenzie

For objects that compiler knows at compiler time, a plain function pointer array of N elements (N be the count of virtual functions) as class member will be the simplest implementation of the v-table. Because the compiler just knows for each virtual function call, which (1st, 2nd or 3rd) function pointer out of the v-table it should use. It's all resolved at compiler time.

For objects that is unknown to application at compiler time, for example COM objects, the implementation v-table is more complicated. However in this case we are talking about objects that the application simply doesn't know. All it knows is the interface. The underneath object is hidden from application. Hence it is impossible for the application to copy, move, store or sort such objects. Such objects are simply inaccessible to application except for its interface(s), So it is out of the topic of this discussion.

Hmm, now plan to start discussion on COM.

Quote:

---

for example COM objects, the implementation v-table is more complicated

---

I think i have little bit knowleldge of this and wrote couple of articals on codeguru and codeproject. In which i discuss the memory layout and virtual function in detail. Take a look at that.

ATL Under the Hood Part 1
http://www.codeguru.com/atl/ATL_UnderTheHood_1.html

ATL Under the Hook Part 2
http://www.codeguru.com/atl/ATL_UndertheHood_2.html

I will post two more replies, and that's it. Other CodeGuru participants can check the thread on comp.lang.c++, but I'll give them a taste of what to expect:

Quote:

---

> Let's first clarify the POD (Plain Old Data) and none-POD myth.
>
> First there is no distinction between "POD" and "none-POD". For any
> complicated class you can think about, they can be boiled down to base
> classes, "none-POD" data object members and POD data members. And each
> of the base class or "none-POD" member can be further taken apart into
> smaller components. Continue this process down, eventually every thing
> is composed of just POD data members.
>
> All classes can be boiled down to just POD data members and nothing else
>

First, let's speak one language.
Standard clearly specifies what is a POD:
"A POD-struct is an aggregate class that has no non-static data
members of type pointer to member, non-POD-struct, non-POD-union
(or array of such types) or reference, and has no user-defined copy
assignment operator and no user-defined destructor." (9/4)

Standard clearly specifies what is an aggregate:

"An aggregate is an array of a class with no user-declared constructors,
no private or protected non-static data members, no base classes, and
no virtual functions." (8.5.1/1)

There are defect reports on these definitions regarding PODs with
user-defined "address-of" operators, non-static "const" members etc,
but the intent is clear.

Second, _nothing_ is guaranteed about memory layout of non-POD objects.
It is _not_ guaranteed that it is contiguous.
It is _not_ guaranteed that address of object is the address of its initial element.
It is _not_ guaranteed that there are not traps inside.

Third, I want my copy assignment operators and copy constructors
work as intended.
Not blindly copied.
I want members of my class assigned and copied as it were intended
by their authors.
Not blindly copied.

The fourth.
Please take a courage to compile and run the following snippet
(IIRC it was posted by Francis Glassborow or James Kanze):

#include <iostream>

struct A { char ia; };
struct B : virtual A { char ib; };
struct C : virtual A { char ic; };
struct D : B, C { char id; };

void print( const B& b )
{
std::cout << " sizeof(b) = " << sizeof(b) << '\n';
std::cout << " &ia-&ib = " << ( &b.ia - &b.ib ) << '\n';
}

int main()
{
std::cout << "complete object B:\n";
print( B() );
std::cout << "B subobject of D:\n";
print( D() );
}



Output (VC.NET):

complete object B:
sizeof(b) = 9
&ia-&ib = 4
B subobject of D:
sizeof(b) = 9
&ia-&ib = 16

I think it would say you a lot about contiguous objects and sizeof.


And the fifth.

When Standard says "it is an undefined behaviour",
it is an undefined behaviour.

End of the statement.


> We have already seen that qsort() works on array of classes with
> std::string or std::vector and other class members.
>


What you have seen was an undefined behaviour.
An undefined behaviour works exactly in this way:
you _might_ see something you expected to see.
However, undefined behaviour _might_ also cause formatting
of your harddrive (please use Google to find out all the
possible consequences of undefined behaviour posted here
on comp.lang.c++ either by John Harrison or Neil Butterworth, iirc).


> Is such class POD or none-POD?


Such class might be an aggregate, but it is certainly non-POD.



>
> I made the assertion that if an object's state or property depends on
> its own memory location, then such object can not be properly copied.
> Some one cited the base_pointer example. Unfortunately this example
> exactly shows why such object can not be copied. You think your copy
> constructor works. But it doesn't!


Thank you for your inspiration.
Unfortunately, it does work.

Would you be so kind to elaborate?
Indeed, code I posted was not intended to compile.
If you are interested I can post a real code.

Nobody is assured against mistakes, but I don't think this is the case.
The only thing about based_ptr is that it uses non-standard and non-portable
functions offset_to_pointer<> and pointer_to_offset.
But it isn't related to the topic.


>
> Let's say your class contains a direct pointer pointing to the n'th char
> of a char array within the class. And there is a function call to get
> that pointer. The caller can use that pointer to do some low level data
> manipulation efficiently. And when you copy objects of this class
> around, you adjust that pointer so it still points to the correct char
> in the char array of the new object. Does it seem to be OK?


Yes, it is strange design, but it works:

#include <iostream>
#include <vector>

struct foo
{
char c[10];
char* p;

static const int N= 2;
// enum { N= 2 };
// just in case your compiler doesn't accept const int

foo() : p( &c[N] ) { strcpy(c, "A test"); }
foo( const foo& f ) : p( &c[N] ) { memcpy(c, f.c, sizeof(c) ); }
foo& operator= ( const foo& f ) { memcpy(c, f.c, sizeof(c) ); return *this; }

// Function get_pointer() is intended to allow clients of class
// to perform low-level data manipulations efficiently.
// The pointer returned may be invalidated by the following uses
// of foo object:
// - calling non-const member functions, including copy assignment operator
char* get_pointer() const { return p; }
};

int main()
{
foo f;
std::cout << f.get_pointer() << '\n';
foo other_f= f;
std::cout << other_f.get_pointer() << '\n';
foo yet_another_f( other_f );
std::cout << yet_another_f.get_pointer() << '\n';
std::vector<foo> vector_of_f;
vector_of_f.push_back( f );
vector_of_f.push_back( other_f );
std::cout << vector_of_f[ 0 ].get_pointer() << '\n'
<< vector_of_f[ 1 ].get_pointer() << std::endl;
}

Output:
test
test
test
test
test


>
> It's NOT OK.


??


> Let's say a piece of code calls to get that pointer, and
> decides to store the pointer for later usage.


Ok.


> And let's say the class object is the first object stored in a vector.
> And now you push one more
> object into the vector, and it finds it needs to do a memory
> reallocation to be able to contain more objects, and so all objects are
> "properly" copied to their new location.
> Every thing works so far.


Agree.


> But when the code who stored the previous
> pointer comes back to manipulate
> the data of the first object.
> Bom! Access violation!


Nope.

First, it isn't an access violation, it is an undefined behaviour.

Second, if user is stupid and/or never reads documentation,
everything might happen even with std::vector<int>.
Even with std::string.

You can protect stupid user from himself by removing
dangerous get_pointer().

Does the following snipped suprise you?

#include <string>
#include <iostream>
int main()
{
std::string s( "Hello, world" ), s2;
const char* p= s.c_str();
s.swap( s2 );
std::cout << p << std::endl; // Boom! Access violation!
}

No, it doesn't suprise you.
Standard says:

"References, pointers, and iterators referring to the elements
of a basic_string sequence may be invalidated by the following
uses of that basic_string object:
- [...] As an argument to basic_string::swap()." (21.3/5)

So the user _is_ warned about consequences.
Writing such a code the _user_ (not you, and not library vendors)
gets all the responsibility.

---

This is the first part of the response. To be continued...

Regards,

Paul McKenzie

Here is the second part of the response:

Quote:

---

> The first object of
> the vector was copied from the original first object of the vector. But
> unfortunately the location is changed so the old pointer no longer works.
>


Ouch.
We do NOT speak about stupid users, do we?
We speak about poor little users of non-POD aggregates.
They call your function (which in turn calls memcpy and qsort)
and see their data corrupted, boomed and access violationed.


> What does that tell you? It tells you what I already told you.


Nope. It tells me that a stupid user is a stupid user.

It tells me that get_pointer function needs to be
carefully documented.
Also it tells me that it is a bad design idea to give such
function to the user.

Note that everything is fine with
std::vector<foo>
from the sample you gave.


> If an
> object's property or behavior depends on its own location in any way at
> all, such object simply can not be copied over. No copy constructor can
> be written for such animal.


Take a look to based_ptr from my previous post, or to the foo definition above.
They both _are_ such animals.
They both _do_ work.


>
> Back to v-table, granted the standard doesn't say any thing how it
> should be implemented. But v-table is part of the property of a class
> object, right?


Neither v-tables nor implementation of virtual function calls
nor implementation of virtual inheritance is described by Standard.
All these things are implementation defined.


> Each instance of the class object will have its OWN copy
> of the v-table.


Wrong.
All implementations using v-tables I've seen so far
placed a _pointer_ to v-table into the instance.


> And I do not see any practical and sensible way of
> implementing it, other than put the v-table together with the rest of
> class members to form a chunk of continuous memory block which is the
> class object.


See above.


> Try to do a sizeof() of the class, you will see that it
> counts in the size of the v-table, in addition to all other none-static
> and none-cost data members.


See above.


>
> Now when it comes to none-static const class members.
> Its implementation is not specified.
> It could be implemented in one of three ways. 1.No
> storage is allocated for it and it is used directly where ever it is
> referenced. 2.Implemented like a const static member. 3.Implement just
> like a regular data member but modification of this value is prohibited.


First of all, I shall admit that you are still speaking about PODs.


>
> When copying object using memcpy(), in the above case 1 or 2, it will
> not be copied, nor will it needs to, so it is not an issue.
>
> In the above case 3.We are some how violating the definition of const by
> writting a value over a const variable. In principle we could be doomed
> if the const value is allocated in a write-protected memory location. In
> practice, the only sensible way of implementation would be allocate
> regular memory for the variable, together with the rest of class
> members. There simply is no feasible way to put this variable away in a
> different memory location. Remember we are talking about case 3, where
> each instance of the class has a separate copy of the const data member.


On a constness, C standard says:
"If an attempt is made to modify an object defined with a const-qualified
type through use of an lvalue with non-const-qualified type,
the behaviour is undefined." (C Standard, 6.7.3/5)

C Standard Rationale (WG14/N897 J11/99-032) says:
"const is specified in such a way that an implementation is at liberty to
put const objects in read-only storage [...]" (p67 line 18)


>
> In summary, the widespread fear of applying qsort() on none-POD object
> arrays is un-warranted. I am not saying it always works. As I pointed
> out already, for objects which depends on its own location, qsort()
> would not work, But neither std::sort in such case.


Please look on based_ptr and the above foo example.

Please read the long thread about C++ objects here
(if URL is split, just merge it)

http://groups.google.com/groups?th=7...rnsc51.ops.asp
.att.net

or search a Google on "virtual inheritance contiguous sizeof".

Hope at least this would make things a little bit clearer,

Sincerely,

Ruslan Abdikeev
Brainbench MVP for Visual C++
http://www.brainbench.com

---

Regards,

Paul McKenzie