Okay to move an object?

[Frederick Gotham]

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.

 

[Tom Widmer]

Jerry Coffin posted:






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

 

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

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

(snip)

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

 

[Frederick Gotham]

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]

=?ISO-8859-15?Q?Juli=E1n?= Albo posted:

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

 

[Tom Widmer]

Tom Widmer posted:






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/d...html/vcsampsamplenextpermutationstlsample.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

 

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

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.

 

[Frederick Gotham]

=?ISO-8859-15?Q?Juli=E1n?= Albo posted:

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

 

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

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.

 

[Howard]

Kaz Kylheku posted:




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

 

[Jim Langston]

=?ISO-8859-15?Q?Juli=E1n?= Albo posted:

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.

 

[Frederick Gotham]

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.

 

[Howard Hinnant]

I realize I'm coming late to the party but...

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.

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/wg21/docs/papers/2006/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

 

[Tom Widmer]

I realize I'm coming late to the party but...




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.

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

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/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

 

[Howard Hinnant]

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

<nod> Right on both counts.

-Howard

 

[Jerry Coffin]

[ ... ]

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:stream &write(std:stream &os) const {
for (it i=data.begin(); i!=data.end(); ++i)
os << **i;
return os;
}

friend std:stream &
operator<<(std:stream &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.