Providing a no-overhead way for a contained class to access its container?

[Jerry Coffin]

[ ... ]

What about the case where the contained class must store its data in
its container?

I'm afraid I don't understand what you're asking.

 

[Puppet_Sock]

What about the case where the contained class must store its data in
its container?

It's not even a little clear what you mean.

Do you mean: The objects in the container stick copies
of themselves into the same container? If so, then you
have a pathological design that should be refactored.

Do you mean: Actual copies of the objects are stored in
the container, as opposed to pointers to the objects?
If that's the issue, and you are concerned about such
things as excess effort involved in swapping copies
instead of pointers, there are many ways of proceeding.

Or do you mean something else?
Socks

 

[PeteOlcott]

It's not even a little clear what you mean.

Do you mean: The objects in the container stick copies
of themselves into the same container? If so, then you
have a pathological design that should be refactored.

Do you mean: Actual copies of the objects are stored in
the container, as opposed to pointers to the objects?
If that's the issue, and you are concerned about such
things as excess effort involved in swapping copies
instead of pointers, there are many ways of proceeding.

Or do you mean something else?
Socks

Here is what I mean. For this specific use it is about the highest
performance (space and time) possible. A Large number of Contained
elements can be read in and written to disk as a single block read or
block write. Also all of the extra memory allocation overhead that
would normally be associated with the individual Contained elements
has been reduced to making two large allocations.

#define uint8 unsigned char
#define uint32 unsigned int


ContainedClass {
uint32 Offset;
bool operator<(const ContainedClass& CC);
}


ContainerClass {
uint32 Length; // All ContainedClass elements are the same Length
std::vector<uint8> Bytes;
std::vector<ContainedClass> Contained;
uint8& operator[](uint32 N){ return Bytes[N]; };
void sort(){ std::sort(Contained.begin(), Contained.end()) };
} Container;


bool ContainedClass:perator<(const ContainedClass& CC)
{
uint32 Last = this->Offset + Container.Length;
for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
if (Container[N] < Container[M])
return true;
else if (Container[N] > Container[M])
return false;
return false; // They must be Equal, thus Not(LessThan)
}

 

[Puppet_Sock]

[snips]

What about the case where the contained class must store its data in
its container?

It's not even a little clear what you mean.

Do you mean: The objects in the container stick copies
of themselves into the same container? If so, then you
have a pathological design that should be refactored.

Do you mean: Actual copies of the objects are stored in
the container, as opposed to pointers to the objects?
If that's the issue, and you are concerned about such
things as excess effort involved in swapping copies
instead of pointers, there are many ways of proceeding.

Or do you mean something else?
Socks

Here is what I mean. For this specific use it is about the highest
performance (space and time) possible. A Large number of Contained
elements can be read in and written to disk as a single block read or
block write. Also all of the extra memory allocation overhead that
would normally be associated with the individual Contained elements
has been reduced to making two large allocations.

Ok, I have to say your response had a lot of words in it,
but didn't come near to answering the question. And, after
nearly 30 posts in this thread, we finally illicit some
part of the actual spec. You seem to be talking about
writing stuff to disk, and reading it back, in an efficient
manner, when you have a bunch of objects stored in a
container class of some kind.

#define uint8  unsigned char
#define uint32 unsigned int

ContainedClass {
  uint32 Offset;
  bool operator<(const ContainedClass& CC);

}

ContainerClass {
   uint32 Length;  // All ContainedClass elements are the same Length
   std::vector<uint8> Bytes;
   std::vector<ContainedClass> Contained;
   uint8& operator[](uint32 N){ return Bytes[N]; };
   void sort(){ std::sort(Contained.begin(), Contained.end()) };

} Container;

bool ContainedClass:perator<(const ContainedClass& CC)
{
  uint32 Last = this->Offset + Container.Length;
  for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
    if (Container[N] < Container[M])
      return true;
    else if (Container[N] > Container[M])
      return false;
return false;  // They must be Equal, thus Not(LessThan)


}

Though your sample code does not seem to be related to the
issue of reading from or writing to disk. Plus, what you
posted sure won't compile.

If what you want to do is an efficient read/write of a large
block of data, there are a variety of approaches. None of
them need the object to know it is contained in a container.

Is that what you are on about? Storing and reading back
a std container of objects?
Socks

 

[Peter Olcott]

[...]

I have a solution that allows the existence of multiple
instances of the container class, the number of such
instances can be specified at run-time. These multiple
instances would be stored in a single global
std::vector<ContainerClass>. Another single instance
global integer would be used as the current subscript
into this std::vector<ContainerClass>, specifying which
ContainerClass is being used. There would be no extra
overhead in the use of either the ContainerClass, nor its
ContainedClass.

Your diverting the overhead to another area. In order for
a `ContainedClass' to get at its `ContainerClass' it needs
to look-up the index of the `ContainerClass' in order to
perform a lookup in the global vector. This has a cost
associates with it. AFAICT, your claim that its somehow
"zero-overhead" is not entirely true. BTW, give some
pseudo-code to demonstrate your current solution. I am
probably missing something here... So your saying that you
have something like:


Lets assume that your `ContainerClass' is a `std::list',
and your `ContainedClass' is a `short'.


typedef short ContainedClass;
typedef std::list<ContainedClass> ContainerClass;


You say that your keeping a global container of said
`ContainerClass':


static std::vector<ContainerClass> g_containers;


and a global integer:


static int g_index = 0;



How do you dynamically add new `ContainedClass' objects to
new `ContainerClass' objects? Where am I going wrong?

I said there is no extra cost for the contained class to
access its container, there might be a very slight extra
cost to change from one container to another. In the case of
my actual implementation there is not even this extra cost
because I only need a single container.

 

[PeteOlcott]

[snips]
What about the case where the contained class must store its data in
its container?
It's not even a little clear what you mean.
Do you mean: The objects in the container stick copies
of themselves into the same container? If so, then you
have a pathological design that should be refactored.
Do you mean: Actual copies of the objects are stored in
the container, as opposed to pointers to the objects?
If that's the issue, and you are concerned about such
things as excess effort involved in swapping copies
instead of pointers, there are many ways of proceeding.
Or do you mean something else?
Socks

Here is what I mean. For this specific use it is about the highest
performance (space and time) possible. A Large number of Contained
elements can be read in and written to disk as a single block read or
block write. Also all of the extra memory allocation overhead that
would normally be associated with the individual Contained elements
has been reduced to making two large allocations.

Ok, I have to say your response had a lot of words in it,
but didn't come near to answering the question. And, after
nearly 30 posts in this thread, we finally illicit some
part of the actual spec. You seem to be talking about
writing stuff to disk, and reading it back, in an efficient
manner, when you have a bunch of objects stored in a
container class of some kind.

#define uint8  unsigned char
#define uint32 unsigned int

ContainedClass {
  uint32 Offset;
  bool operator<(const ContainedClass& CC);

}

ContainerClass {
   uint32 Length;  // All ContainedClass elements are the same Length
   std::vector<uint8> Bytes;
   std::vector<ContainedClass> Contained;
   uint8& operator[](uint32 N){ return Bytes[N]; };
   void sort(){ std::sort(Contained.begin(), Contained.end()) };

} Container;

bool ContainedClass:perator<(const ContainedClass& CC)
{
  uint32 Last = this->Offset + Container.Length;
  for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
    if (Container[N] < Container[M])
      return true;
    else if (Container[N] > Container[M])
      return false;
return false;  // They must be Equal, thus Not(LessThan)

}

Though your sample code does not seem to be related to the
issue of reading from or writing to disk. Plus, what you
posted sure won't compile.

If what you want to do is an efficient read/write of a large
block of data, there are a variety of approaches. None of
them need the object to know it is contained in a container.

Is that what you are on about? Storing and reading back
a std container of objects?
Socks- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -

Think about it as storage, retrieval, allocation, access, and
manipulation of strings such that the space and time requirements are
at the current edge of hardware capability. Multiple GB of data stored
in RAM and retrieved from disk. A slight modification to the provided
code, and these strings could vary in length.

 

[Thomas J. Gritzan]

Here is what I mean. For this specific use it is about the highest
performance (space and time) possible. A Large number of Contained
elements can be read in and written to disk as a single block read or
block write. Also all of the extra memory allocation overhead that
would normally be associated with the individual Contained elements
has been reduced to making two large allocations.

#define uint8 unsigned char
#define uint32 unsigned int

typedef unsigned char uint8;
typedef unsigned int uint32;

ContainedClass {
uint32 Offset;
bool operator<(const ContainedClass& CC);
}


ContainerClass {
uint32 Length; // All ContainedClass elements are the same Length
std::vector<uint8> Bytes;
std::vector<ContainedClass> Contained;
uint8& operator[](uint32 N){ return Bytes[N]; };
void sort(){ std::sort(Contained.begin(), Contained.end()) };
} Container;

This code doesn't compile, but assuming a working version of this code,
you could use std::sort with a functor with a pointer to its contained
class (untested! code):

struct ContainedLess
{
ContainedLess(const ContainerClass* container_) :
container(container_) {}

bool operator()(const ContainedClass& c1, const ContainedClass& c2)
const
{
// compare c1 and c2, use member 'container'
// to access container class
const uint8* p1 = &container->Bytes[c1.Offset];
const uint8* p2 = &container->Bytes[c2.Offset];
const uint8* end = p1 + container->Length;
for (; p1 != end; ++p1, ++p2)
{
// ...
}
}

private:
const ContainerClass* container;
};

void ContainerClass::sort()
{
std::sort(Contained.begin(), Contained.end(), ContainedLess(this));
}

It also would be a good idea to make some members of the classes private.

bool ContainedClass:perator<(const ContainedClass& CC)
{
uint32 Last = this->Offset + Container.Length;
for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
if (Container[N] < Container[M])
return true;
else if (Container[N] > Container[M])
return false;
return false; // They must be Equal, thus Not(LessThan)
}

 

[Peter Olcott]

Here is what I mean. For this specific use it is about
the highest
performance (space and time) possible. A Large number of
Contained
elements can be read in and written to disk as a single
block read or
block write. Also all of the extra memory allocation
overhead that
would normally be associated with the individual
Contained elements
has been reduced to making two large allocations.

#define uint8 unsigned char
#define uint32 unsigned int

typedef unsigned char uint8;
typedef unsigned int uint32;

ContainedClass {
uint32 Offset;
bool operator<(const ContainedClass& CC);
}


ContainerClass {
uint32 Length; // All ContainedClass elements are the
same Length
std::vector<uint8> Bytes;
std::vector<ContainedClass> Contained;
uint8& operator[](uint32 N){ return Bytes[N]; };
void sort(){ std::sort(Contained.begin(),
Contained.end()) };
} Container;

This code doesn't compile, but assuming a working version
of this code, you could use std::sort with a functor with
a pointer to its contained class (untested! code):

struct ContainedLess
{
ContainedLess(const ContainerClass* container_) :
container(container_) {}

bool operator()(const ContainedClass& c1, const
ContainedClass& c2) const
{
// compare c1 and c2, use member 'container'
// to access container class
const uint8* p1 = &container->Bytes[c1.Offset];
const uint8* p2 = &container->Bytes[c2.Offset]; const
uint8* end = p1 + container->Length;
for (; p1 != end; ++p1, ++p2)
{
// ...
}
}

private:
const ContainerClass* container;
};

void ContainerClass::sort()
{
std::sort(Contained.begin(), Contained.end(),
ContainedLess(this));
}

It also would be a good idea to make some members of the
classes private.

That would be the first attempt at actually answering my
original question. I was guessing that the answer might have
something to do with functors. The solution does look pretty
clean, far cleaner than the solution that I derived.

My only question would be whether or not it avoided the
overhead of initializing the pointer to the container upon
every comparison. I would estimate that you would already
know this answer, knowing more clearly the underlying
semantics of the syntax that you specified.

bool ContainedClass:perator<(const ContainedClass& CC)
{
uint32 Last = this->Offset + Container.Length;
for (int N = this->Offset, M = CC.Offset; N < Last;
N++, M++)
if (Container[N] < Container[M])
return true;
else if (Container[N] > Container[M])
return false;
return false; // They must be Equal, thus Not(LessThan)
}

 

[PeteOlcott]

That's correct


That's incorrect.  

First, one would need to define "cost".  Typical in software are
memory, execution and development.  Most of the time, the correct
solution is a compromise between the three.   Even looking purely at
memory cost, the optimal solution would depend on lifetime of the
objects and the way they are used.  For two short lived objects a
pointer to the other would be the optimal memory minimising solution.


I am sorry but you are ignoring your overhead.

Case 1 that you classify as overhead:

A pointer to the container is passed to the contained class.
- Memory overhead: 1 pointer per contained object
Note that this memory overhead only exist for the lifetime of the
contained object.
- Access overhead: Access contained pointer and dereference it

Case 2: What you classify as no overhead

a global container of containers of class with global integer
- Memory overhead: the global container of containers and a global integer  
These exist for the lifetime of the program.  The global std::vector
will only ever grow unless you use the swap idiom to shrink it at
appropriate time.  If you do, then there a computation overhead for
doing so.  The global integer is also memory overhead.
- Access overhead: Access the global container, access the global
integer, call global container.at(global integer), access the
contained class.  Much more expensive than dereferencing a "pointer to
parent".  
- Development overhead: it is generally agreed that global introduce
development risk and maintenance overhead over well encapsulated
solutions.  IME, generally speaking, a solution using globals is quick
and efficient (from a development point of view) for a simple problem
but as the scope of the problem grows, globals become a liability.
Regardless of the scope of the problem, globals tend to be a
maintenance liability.

Look, I am not saying that your solution is wrong.  I am saying that
it is wrong to ignore the costs of your solution and only highlight
the memory cost of the pointer-to-parent solution.  In fact, both
approaches have pros and cons.  One needs to fairly evaluate them in
order to make the correct choice.

Yannick- Hide quoted text -

- Show quoted text -

My basic singleton solution has no extra cost over-and-above the cost
of one class accessing another, because this solution IS simply one
class accessing another using the typical ways for one class to access
another.

 

[PeteOlcott]

That's correct


That's incorrect.  

First, one would need to define "cost".  Typical in software are
memory, execution and development.  Most of the time, the correct
solution is a compromise between the three.   Even looking purely at
memory cost, the optimal solution would depend on lifetime of the
objects and the way they are used.  For two short lived objects a
pointer to the other would be the optimal memory minimising solution.


I am sorry but you are ignoring your overhead.

Case 1 that you classify as overhead:

A pointer to the container is passed to the contained class.
- Memory overhead: 1 pointer per contained object
Note that this memory overhead only exist for the lifetime of the
contained object.
- Access overhead: Access contained pointer and dereference it

Case 2: What you classify as no overhead

a global container of containers of class with global integer
- Memory overhead: the global container of containers and a global integer  
These exist for the lifetime of the program.  The global std::vector
will only ever grow unless you use the swap idiom to shrink it at
appropriate time.  If you do, then there a computation overhead for
doing so.  The global integer is also memory overhead.
- Access overhead: Access the global container, access the global
integer, call global container.at(global integer), access the
contained class.  Much more expensive than dereferencing a "pointer to
parent".  
- Development overhead: it is generally agreed that global introduce
development risk and maintenance overhead over well encapsulated
solutions.  IME, generally speaking, a solution using globals is quick
and efficient (from a development point of view) for a simple problem
but as the scope of the problem grows, globals become a liability.
Regardless of the scope of the problem, globals tend to be a
maintenance liability.

Look, I am not saying that your solution is wrong.  I am saying that
it is wrong to ignore the costs of your solution and only highlight
the memory cost of the pointer-to-parent solution.  In fact, both
approaches have pros and cons.  One needs to fairly evaluate them in
order to make the correct choice.

Yannick- Hide quoted text -

- Show quoted text -

Also my solution for multiple instances of ContainerClasses providing
access to themselves to their ContainedClasses has no additional space
or time cost involved in the specific instance of this provided
access. There is a slight additional space and time cost in providing
multiple instances of the ContainerClass, but, this additional cost
does not directly pertain to providing this access. Instead this
additional cost only pertains to the provision of multiple instances
of the ContainerClass. The singleton case of this ContainerClass has
no additional costs of any kind what-so-ever.

 

[PeteOlcott]

[deleted attempts at explaining that everything has a cost that has
been totally ignored]

Also my solution for multiple instances of ContainerClasses providing
access to themselves to their ContainedClasses has no additional space
or time cost involved in the specific instance of this provided
access. There is a slight additional space and time cost in providing
multiple instances of the ContainerClass, but, this additional cost
does not directly pertain to providing this access. Instead this
additional cost only pertains to the provision of multiple instances
of the ContainerClass. The singleton case of this ContainerClass has
no additional costs of any kind what-so-ever.

Sorry Pete but this come forward as: "my solution is perfect in all
ways" and sadly even as: "I am perfect in all ways"

So I am afraid that all we can conclude is that although your solution
has a cost, you think it has none and it is perfect.   Despite several
peoples attempting to show you otherwise, you refuse to see any cost
to it.  

An alternative approach has been suggested when you finally posted
some example code and clarified your requirements to something
realistic.   IMO, the proposed solution with an external comparison
function is an improvement which at least from a maintenance point of
view demonstrate that your original solution was not perfect.
However, since it is your code and your project, you are perfectly
free to use the solution of your choice.

Cheers,

Yannick

I agree that the alternative solution is superior to my solution form
the maintenance point of view, and that my solution is quite clumsy
from this point of view. It is an objective fact that my solution has
no ADDTIONAL

 

[test0r]

[deleted attempts at explaining that everything has a cost that has
been totally ignored]

Also my solution for multiple instances of ContainerClasses providing
access to themselves to their ContainedClasses has no additional space
or time cost involved in the specific instance of this provided
access. There is a slight additional space and time cost in providing
multiple instances of the ContainerClass, but, this additional cost
does not directly pertain to providing this access. Instead this
additional cost only pertains to the provision of multiple instances
of the ContainerClass. The singleton case of this ContainerClass has
no additional costs of any kind what-so-ever.

Sorry Pete but this come forward as: "my solution is perfect in all
ways" and sadly even as: "I am perfect in all ways"

So I am afraid that all we can conclude is that although your solution
has a cost, you think it has none and it is perfect. Despite several
peoples attempting to show you otherwise, you refuse to see any cost
to it.

An alternative approach has been suggested when you finally posted
some example code and clarified your requirements to something
realistic. IMO, the proposed solution with an external comparison
function is an improvement which at least from a maintenance point of
view demonstrate that your original solution was not perfect.
However, since it is your code and your project, you are perfectly
free to use the solution of your choice.

Cheers,

Yannick

I agree that the alternative solution is superior to my solution form
the maintenance point of view, and that my solution is quite clumsy
from this point of view. It is an objective fact that my solution has
no ADDTIONAL

test

 

[PeteOlcott]

[deleted attempts at explaining that everything has a cost that has
been totally ignored]

Also my solution for multiple instances of ContainerClasses providing
access to themselves to their ContainedClasses has no additional space
or time cost involved in the specific instance of this provided
access. There is a slight additional space and time cost in providing
multiple instances of the ContainerClass, but, this additional cost
does not directly pertain to providing this access. Instead this
additional cost only pertains to the provision of multiple instances
of the ContainerClass. The singleton case of this ContainerClass has
no additional costs of any kind what-so-ever.

Sorry Pete but this come forward as: "my solution is perfect in all
ways" and sadly even as: "I am perfect in all ways"

So I am afraid that all we can conclude is that although your solution
has a cost, you think it has none and it is perfect.   Despite several
peoples attempting to show you otherwise, you refuse to see any cost
to it.  

An alternative approach has been suggested when you finally posted
some example code and clarified your requirements to something
realistic.   IMO, the proposed solution with an external comparison
function is an improvement which at least from a maintenance point of
view demonstrate that your original solution was not perfect.
However, since it is your code and your project, you are perfectly
free to use the solution of your choice.

Cheers,

Yannick

Google Groups posting screwed up and posted my last message before I
had finsihed typing it.

I agree that the alternative solution is far superior to the clumsy
solution that I derived from a code maintenance point of view, yet it
is also an objective fact that the singleton solution that I proposed
has no ADDTIONAL space or time cost over-and-above the typical case of
one class accessing another, because it is exactly this same typical
case of one class accessing another, nothing more and nothing less.

The only issue left to resolve is whether or not this proposed
solution also has zero (or negligible) ADDITIONAL cost.
In either case this solution would be greatly superior to the solution
that I derived. If the proposed solution must copy a pointer to the
container for every single comparision, then the proposed solution
would be superior from a code maintenance point of view, and inferior
from a time cost point of view.

 

[Peter Olcott]

[deleted attempts at explaining that everything has a
cost that has
been totally ignored]

Also my solution for multiple instances of
ContainerClasses providing
access to themselves to their ContainedClasses has no
additional space
or time cost involved in the specific instance of this
provided
access. There is a slight additional space and time
cost in providing
multiple instances of the ContainerClass, but, this
additional cost
does not directly pertain to providing this access.
Instead this
additional cost only pertains to the provision of
multiple instances
of the ContainerClass. The singleton case of this
ContainerClass has
no additional costs of any kind what-so-ever.
Sorry Pete but this come forward as: "my solution is
perfect in all
ways" and sadly even as: "I am perfect in all ways"

So I am afraid that all we can conclude is that although
your solution
has a cost, you think it has none and it is perfect.
Despite several
peoples attempting to show you otherwise, you refuse to
see any cost
to it.
An alternative approach has been suggested when you
finally posted
some example code and clarified your requirements to
something
realistic. IMO, the proposed solution with an external
comparison
function is an improvement which at least from a
maintenance point of
view demonstrate that your original solution was not
perfect.
However, since it is your code and your project, you are
perfectly
free to use the solution of your choice.

Cheers,

Yannick

I agree that the alternative solution is superior to my
solution form
the maintenance point of view, and that my solution is
quite clumsy
from this point of view. It is an objective fact that my
solution has
no ADDTIONAL

test

Test results, the ContainedLess constructor is called only
once, thus the proposed is the solution is the one that I
have been looking for, it is a superb solution in every
aspect.

 

[Peter Olcott]

If you are lucky :-(


Sorry, slightly switching topic but although the typedef
are an
improvement over the #define, neither are quite safe.
Most safe to
rely on the platform standard headers to have it right:

The whole purpose of this convention is to provide a
cross-platform single standard, so your suggestion would
defeat this purpose. Besides what could be unsafe about the
above constructs?

 

[PeteOlcott]

If you are lucky :-(

Sorry, slightly switching topic but although the typedef are an
improvement over the #define, neither are quite safe.  Most safe to
rely on the platform standard headers to have it right:

#include <stdint.h>  // might be optional on your platform
uint32_t aSafe32bitsIntegerThatWillNotSuddentlyBecome64bitsOr16Or8;

I forgot that I was talking in a generic C++ forum, I rarely do this.
I almost always talk in the MFC forum. Of cource my #define statements
would be redefined for each of the differing platforms. The idea is
the uint32 is always an unsigned 32-bit integer no matter what
platform you may be on.

 

[Daniel Pitts]

The whole purpose of this convention is to provide a
cross-platform single standard, so your suggestion would
defeat this purpose. Besides what could be unsafe about the
above constructs?

Platform *standard* headers. Meaning if the platform implements the
standard, the file stdint.h should exist. In this file, it will define
uint32_t appropriately, whether it is a system that needs to use
"unsigned long int", or "unsigned long long", or "unsigned short" to do
so.

Both the #define and typedefs above may change the size if you change
compilers, but the stdint.h definitions will be consistent, since they
are managed by the platform developers.