469,898 Members | 2,360 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,898 developers. It's quick & easy.

Dynamically created structures ???

I want to be able to efficiently build data structures at run-time.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.
(2) union of the desired pointers.
(3) An Inheritance hierarchy
(4) Possibly a union of the desired data types.

I need to be able to construct arbitrary data structures
that have as close to the same speed as those build at
compiler-time, yet I need to do this at run-time.

Does anyone have any good ideas ???
Jul 19 '05 #1
14 3310
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Oh*********************@bgtnsc04-news.ops.worldnet.att.net...
I want to be able to efficiently build data structures at run-time.
It helps to know what you are trying to do, the bigger picture. Is this a
language runtime?

How many "dynamic structures" are there? I've been playing with stack
allocated objects in my language so I kind of have a feeling of what you
want.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.
(2) union of the desired pointers.
(3) An Inheritance hierarchy
(4) Possibly a union of the desired data types.

I need to be able to construct arbitrary data structures
that have as close to the same speed as those build at
compiler-time, yet I need to do this at run-time.

Does anyone have any good ideas ???


Depends on what you really want to do.

Mike

Jul 19 '05 #2
> I want to be able to efficiently build data structures at run-time.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.
Are the "desired types" known before you allocate memory or after?
Can the dynamically allocated array contain different types or not? In
short, is it polymorphic or not?
Are these "desired types" POD's or non-POD's?
Does anyone have any good ideas ???


State your problem more accurately.

Stephen Howe
Jul 19 '05 #3
I need to be able to create records of pre-existing types. In some
cases these records would need to hold other aggregations, such
as vectors, and these records themselves need to be contained in
a vector.

struct Test {
std::vector<double> Test1;
float Test2;
std::string Test3[3];
};

std::vector<Test> Test4;

The struct can be any combination of types, including user defined
types. The struct is what needs to be dynamically created at run-time.
The simplest way might be to merely create a std::vector of void,
and then cast these into the desired types at run-time, based on
an integer type field stored in the record. I am assuming that this
cast costs me run-time, which I want to avoid if possible.

"Vis Mike" <visionary25@_nospam_hotmail.com> wrote in message news:be**********@bob.news.rcn.net...
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Oh*********************@bgtnsc04-news.ops.worldnet.att.net...
I want to be able to efficiently build data structures at run-time.


It helps to know what you are trying to do, the bigger picture. Is this a
language runtime?

How many "dynamic structures" are there? I've been playing with stack
allocated objects in my language so I kind of have a feeling of what you
want.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.
(2) union of the desired pointers.
(3) An Inheritance hierarchy
(4) Possibly a union of the desired data types.

I need to be able to construct arbitrary data structures
that have as close to the same speed as those build at
compiler-time, yet I need to do this at run-time.

Does anyone have any good ideas ???


Depends on what you really want to do.

Mike

Jul 19 '05 #4
I stated this to the prior respondent. Basically to create a std::vector of
records of differing types (including aggregations) at run-time.

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message
news:3f***********************@news.dial.pipex.com ...
I want to be able to efficiently build data structures at run-time.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.


Are the "desired types" known before you allocate memory or after?
Can the dynamically allocated array contain different types or not? In
short, is it polymorphic or not?
Are these "desired types" POD's or non-POD's?
Does anyone have any good ideas ???


State your problem more accurately.

Stephen Howe

Jul 19 '05 #5
"Stephen Howe" <NO**********@dial.pipex.com> wrote in message news:<3f***********************@news.dial.pipex.co m>...
I want to be able to efficiently build data structures at run-time.
These data structures need to be accessed with minimal time.
The only a few ways that come immediately to mind would be
some sort of dynamically allocated array of :

(1) void pointers, that must be cast into the desired types.


Are the "desired types" known before you allocate memory or after?
Can the dynamically allocated array contain different types or not? In
short, is it polymorphic or not?
Are these "desired types" POD's or non-POD's?
Does anyone have any good ideas ???


State your problem more accurately.


Agreed. The problem is not well-specified.

It is also a little confusing. Accessing a structure is not really an
issue. If he meant allocating it, well that is a different story. In
that case, he probably needs a custom allocator that uses a memory
pool.

Dave
Jul 19 '05 #6
Raoul Gough <Ra********@yahoo.co.uk> wrote in message news:<u3***********@yahoo.co.uk>...
Hi Peter,

Please, could you organise your follow-ups inline, rather than
top-posting?

"Peter Olcott" <ol****@worldnet.att.net> writes:
I need to be able to create records of pre-existing types. In some
cases these records would need to hold other aggregations, such
as vectors, and these records themselves need to be contained in
a vector.

struct Test {
std::vector<double> Test1;
float Test2;
std::string Test3[3];
};

std::vector<Test> Test4;

The struct can be any combination of types, including user defined
types. The struct is what needs to be dynamically created at run-time.
The simplest way might be to merely create a std::vector of void,
and then cast these into the desired types at run-time, based on
an integer type field stored in the record. I am assuming that this
cast costs me run-time, which I want to avoid if possible.


The boost libraries have any "any" type that could do the job you want
(e.g. your struct Test could just be a std::vector<boost::any>), but
you will probably be disappointed to know that it uses dynamic
allocation and casting. I think this is a reasonable expense though,
for what you want to do. I guess the only other alternative is to
create a super-smart union type, with all the inherent alignment
problems and probably space overheads that go with it (ISTR a long
thread about the alignment issues about a year ago - maybe on clc++m).


I think you mean this one, back in November:
http://groups.google.com/groups?hl=e...26selm%3Dslrna
rbgb.3hc.news_comp.lang.c%252B%252B.moderated_expi res-2002-12-01%2540nightrunner.nmhq.net%26rnum%3D5

But, I think what kicked off that debate was Herb Sutter's GotW #85.
Here's that thread:
http://groups.google.com/groups?hl=e...f%2540nortelne
works.com%26rnum%3D4

And the solution:
http://groups.google.com/groups?q=An...4ax.com&rnum=3

Dave
Jul 19 '05 #7
Karl Heinz Buchegger <kb******@gascad.at> wrote in message news:<3F***************@gascad.at>...
David Cattarin wrote:

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message news:<3f***********************@news.dial.pipex.co m>...
> I want to be able to efficiently build data structures at run-time.
> These data structures need to be accessed with minimal time.
> The only a few ways that come immediately to mind would be
> some sort of dynamically allocated array of :
>
> (1) void pointers, that must be cast into the desired types.

Are the "desired types" known before you allocate memory or after?
Can the dynamically allocated array contain different types or not? In
short, is it polymorphic or not?
Are these "desired types" POD's or non-POD's?

> Does anyone have any good ideas ???

State your problem more accurately.
Agreed. The problem is not well-specified.

It is also a little confusing. Accessing a structure is not really an
issue. If he meant allocating it, well that is a different story. In
that case, he probably needs a custom allocator that uses a memory
pool.


I guess the thing Peter wants to do is this:

Imagine a relational data base system. At the moment you access a table
you don't know what fields are there in which order and what data type
each of this fields have. So Peter needs a way to construct such a
structure representing a record in the table during runtime.


I just read his post, and I agree that it does seem like he wants to
interface with a DB and wants to access the data through some form of
Variant, though he still hasn't precicely stated the problem.
But IMHO he makes the same mistake he did one and a half year ago:
premature optimization. Fiddeling with void pointers and casting
forth and back to save some nanoseconds in the middle of some rarely
used functions instead of starting with a rock solid approach which
involves a class hierarchy, where eg. there are classes which represent
different types of fields and collecting those fields in a vector in
a polymorphic way. If the rock solid approach turns out to be to slow,
one can always go back and change that (with the help of a profiler),
but starting with void pointers and knowing that lots of casts will be
needed, paired with flags and type identifiers is a safe bet, that lots
of programmer time will be wasted.


Not knowing the form of his data, I'm going to assume converting it
isn't going to be a performance problem. I also don't know how often
this occurs.

Preoptimizing his conversion routines does seem to be a misplaced
effort. I don't think he realizes that he'll need to allocate memory
in order to avoid allignment problems and that is (sort of) expensive.
I also think he needs to realize that if you need to do complicate
things, then you have to pay for it in terms of performance penalties
(i.e. nothing is free).

Dave
Jul 19 '05 #8
> I guess the thing Peter wants to do is this:

Imagine a relational data base system. At the moment you access a table
you don't know what fields are there in which order and what data type
each of this fields have. So Peter needs a way to construct such a
structure representing a record in the table during runtime.
Yes just like this...
But IMHO he makes the same mistake he did one and a half year ago:
premature optimization. Fiddeling with void pointers and casting
forth and back to save some nanoseconds in the middle of some rarely
used functions instead of starting with a rock solid approach which
involves a class hierarchy, where eg. there are classes which represent
different types of fields and collecting those fields in a vector in
a polymorphic way. If the rock solid approach turns out to be to slow,
one can always go back and change that (with the help of a profiler),
but starting with void pointers and knowing that lots of casts will be
needed, paired with flags and type identifiers is a safe bet, that lots
of programmer time will be wasted.

--
Karl Heinz Buchegger
kb******@gascad.at


Okay now you have said what not to do, what about what to do?
What are the options for dynamically creating structures to hold
arbitrary database records?
Jul 19 '05 #9
PO>I want to be able to efficiently build data structures at run-time.
PO>These data structures need to be accessed with minimal time.

I am working on something similar and have terrible problems
getting it right. I'll explain what I have, tell you where it goes
wrong and hope for someone to fix it.

I use two base classes for everything. The first
is called One, the other Some. One and Some
specialize in a symmetrical way. That is, for every
specialized One there is a corresponding specialized
Some that stores pointers to the specific One's.

The specializations that I made are the following

One <- Sailor
One<- Barrel
One <-Ship
One <- Sea
One <- World

Some <-Sailors
Some <-Barrels
Some <- Ships
Some <-Seas

(Some <-Sailors means class Sailors inherits from class Some)

The hierarchie I build up is petty but it reflects
a real system that I work on. When you
insert Some objects in specialized One objects,
you get a complicated and very dense pack of
interrelated object. Ship contains Sailors and
Barrels, for instance, and a Sea contains many
Ships.

For every Some (Sailors, Barrels, Ships, Seas)
there is the notion of a 'current'. So there is
allways one Sailor current, on the current Ship
in the current Sea. And there is one Barrel
current, on the same ship.

I am not sure if the implementation is right. The
destructor of Some causes problems. There
might be memory leaks. Perhaps someone can
point them out.

Also, I feel that I might slip in a template on this, but
I haven't gotten that far yet.

With a hierarchy similar to this I try to create menu
object dynamically. Four menu headings read
"Sea", "Ship", "Sailor" and "Barrel". They get filled
with data from "Seas", "Ships", "Sailors" and "Barrels"
depending on the current Sea and Ship.

If this code somewhat represents what you want to do, I'd
be honored if you hacked it and show me the weak spots.

-X

#include <iostream.h>
#include <list.h>
class One
{
public:
string name;
string type;
One(const string&a="One",const string&b="One"):name(a),type(b){}
virtual One*get(){return this;}
virtual void show(){cout<<"\n"<<type<<":\t"<<name;}
};
typedef list<One*> More;
class Some:public One
{
public:
More more;
size_t index;
Some(const string&a="Some"):One(a,"Some"),index(0){}
Some(const Some&a):One(a),index(a.index)
{
for(More::const_iterator b=a.more.begin();b!=a.more.end();++b)
more.push_back(*b);
}
Some&operator=(const Some&a)
{
index=a.index;
for(More::const_iterator b=a.more.begin();b!=a.more.end();++b)
more.push_back(*b);
return*this;
}
// virtual ~Some()
// {
// for(More::iterator a=more.begin();a!=more.end();++a)
// delete*a;
// }
void showAll()
{
for(More::const_iterator a=more.begin();a!=more.end();++a)
(*a)->show();
}
void add(One*a)
{
more.push_back(a);
}
One * get(){return*(more.begin())+index;}
void next(){if(size()>0)index=index==size()-1?0:index+1;}
void prev(){if(size()>0)index=index==0?size()-1:index-1;}
size_t size(){return more.size();}
void set(int a){index=a<0?index:a>size()-1?index:a;}
};
class Barrel:public One{public:Barrel(const string&a):One(a,"Barrel"){}};
class Barrels:public Some{};
class Sailor:public One{public:Sailor(const string&a):One(a,"Sailor"){}};
class Sailors:public Some{};
class Ship:public One
{
public:
Sailors sailors;
Barrels barrels;
Ship(const string&a):One(a,"Ship"){}
void show(){One::show();sailors.showAll();barrels.showA ll();}
};
class Ships:public Some{};
class Sea:public One
{
public:
Ships ships;
Sea(const string&a):One(a,"Sea"){}
void show(){One::show();ships.showAll();}
};
class Seas:public Some{};
class World:public One
{
public:
Seas _seas;
void add(Barrel*a){barrels()->add(a);}
void add(Sailor*a){sailors()->add(a);}
void add(Ship*a){ships()->add(a);}
void add(Sea*a){seas()->add(a);}
void show(){seas()->showAll();}
Barrel * barrel() {return static_cast<Barrel*>(barrels()->get());}
Sailor * sailor() {return static_cast<Sailor*>(sailors()->get());}
Ship * ship() {return static_cast<Ship*>(ships()->get());}
Sea * sea() {return static_cast<Sea*>(seas()->get());}
Barrels * barrels() {return &(ship()->barrels);}
Sailors * sailors() {return &(ship()->sailors);}
Ships * ships() {return &(sea()->ships);}
Seas * seas() {return &_seas;}
};
int main(int argc,char**argv)
{
World world;
Sea sea_1("North Sea");
Sea sea_2("Mare Nostrum");
Ship ship_1("Batavia");
Ship ship_2("New Highland Height");
Ship ship_3("Titanic");
ship_1.sailors.add(new Sailor("Michiel de Ruyter"));
ship_1.sailors.add(new Sailor("Piet Heyn"));
ship_1.barrels.add(new Barrel("Brandewijn"));
ship_1.barrels.add(new Barrel("Whiskey"));
ship_1.barrels.add(new Barrel("Rum"));
ship_2.sailors.add(new Sailor("Mr. Andersson"));
ship_2.sailors.add(new Sailor("Beavis"));
ship_2.sailors.add(new Sailor("Butt-Head"));
ship_2.barrels.add(new Barrel("Cola light"));
ship_2.barrels.add(new Barrel("Milkshake (empty)"));
ship_3.sailors.add(new Sailor("The Flying Dutchman"));
ship_3.barrels.add(new Barrel("Water"));
sea_1.ships.add(&ship_1);
sea_1.ships.add(&ship_2);
sea_2.ships.add(&ship_3);
world._seas.add(&sea_1);
world._seas.add(&sea_2);
world.show();
return 0;
}
_____________________________
Output:

Sea: North Sea
Ship: Batavia
Sailor: Michiel de Ruyter
Sailor: Piet Heyn
Barrel: Brandewijn
Barrel: Whiskey
Barrel: Rum
Ship: New Highland Height
Sailor: Mr. Andersson
Sailor: Beavis
Sailor: Butt-Head
Barrel: Cola light
Barrel: Milkshake (empty)
Sea: Mare Nostrum
Ship: Titanic
Sailor: The Flying Dutchman
Barrel: Water


Jul 19 '05 #10


Peter Olcott wrote:

I am not sure that I understand what you are saying.
There does not seem to be enbough detail to your
specification for me to infer exactly what you are proposing.


As I said: A base class and derived classes, which implement
the different data types you need to store.

Something like that (Warning: untested code)

class Value
{
public:
~Value() {}

virtual void PrintTo( std::ostream& To, int indent ) {}
};

class IntValue : public Value
{
public:
IntValue( int x ) : m_Value( x ) {}

virtual void PrintTo( std::ostream& To, int indent )
{ To << std::string( indent, ' ' )
<< "An int: " << m_Value << "\n"; }

protected:
int m_Value;
};

class DoubleValue : public Value
{
public:
DoubleValue( double x ) : m_Value( x ) {}

virtual void PrintTo( std::ostream& To, int indent )
{ To << std::string( indent, ' ' )
<< "A double: " << m_Value << "\n"; }

protected:
double m_Value;
};

class StringValue : public Value
{
public:
StringValue( std::string x ) : m_Value( x ) {}

virtual void PrintTo( std::ostream& To, int indent )
{ To << std::string( indent, ' ' )
<< "A string: " << m_Value << "\n"; }

protected:
std::string m_Value;
};

class ArrayValue : public Value
{
public:
~ArrayValue() { for( int i = 0; i < m_Value.size(); ++i )
delete m_Value[i]; }

virtual void PrintTo( std::ostream& To, int indent )
{ To << std::string( indent, ' ' )
<< "An array consisting of:\n";
for( int i = 0; i < m_Value.size(); ++i )
m_Value[i]->PrintTo( To, indent + 2 );
}

void Add( Value* Next ) { m_Value.push_back( Next ); }

protected:
std::vector< Value* > m_Value;
};

class Record : public ArrayValue
{
public:
void PrintTo( std::ostream& To )
{
To << "This record consists of:\n";
for( int i = 0; i < m_Value.size(); ++i )
m_Value[i]->PrintTo( To, 2 );
}
};

int main()
{
// Build up a structure

Record MyRecord;
MyRecord.Add( new IntValue( 5 ) );
MyRecord.Add( new DoubleValue( 2.0 ) );
MyRecord.Add( new StringValue( "Heureka" ) );

ArrayValue* pTemp = new ArrayValue;
pTemp->Add( new DoubleValue( 3.0 ) );
pTemp->Add( new DoubleValue( 1.0 ) );
pTemp->Add( new StringValue( "got it?" ) );

MyRecord.Add( pTemp );

MyRecord.PrintTo( std::cout );

return 0;
}

--
Karl Heinz Buchegger, GASCAD GmbH
Teichstrasse 2
A-4595 Waldneukirchen
Tel ++43/7258/7545-0 Fax ++43/7258/7545-99
email: kb******@gascad.at Web: www.gascad.com

Fuer sehr grosse Werte von 2 gilt: 2 + 2 = 5
Jul 19 '05 #11
"Peter Olcott" <ol****@worldnet.att.net> wrote in message news:<lB*********************@bgtnsc04-news.ops.worldnet.att.net>...
Not knowing the form of his data, I'm going to assume converting it
isn't going to be a performance problem. I also don't know how often
this occurs.


The database analogy was very good. It is a case just like this.
In some cases the record must also hold aggregations of other
records.
Preoptimizing his conversion routines does seem to be a misplaced
effort. I don't think he realizes that he'll need to allocate memory
in order to avoid allignment problems and that is (sort of) expensive.
I also think he needs to realize that if you need to do complicate
things, then you have to pay for it in terms of performance penalties
(i.e. nothing is free).

Dave


I don't think that allocating memory will be a problem. I can reasonably
assume that I will have much more memory than I need, thus I can
reduce the number of allocations to very few.


Then a vector of boost::any might be what you want. The vector would
contain elements in record order.

Dave
Jul 19 '05 #12
> But IMHO he makes the same mistake he did one and a half year ago:
premature optimization.


AFAIK, Peter does not make mistakes. He is a software God. Must be his human
face to have to ask for help.

Stephen Howe
Jul 19 '05 #13
"Stephen Howe" <SP*******************@tnsofres.com> wrote in message
news:3f***********************@reading.news.pipex. net...
But IMHO he makes the same mistake he did one and a half year ago:
premature optimization.


AFAIK, Peter does not make mistakes. He is a software God. Must be his human
face to have to ask for help.

Stephen Howe

If you see my
"What is wrong with the "for" loop?"
thread, you will see that I have already
answered this question myself, except
for the syntax of the for loop itself.

There is another answer that is very similar to mine
that has finally been posted to the moderated group.
(It took them three days to post my question, and
another day to get a response.)

I am hoping that a slight extention to my version
will provide much faster response time, in less space.
In other words eliminating the need for a TypeCode
field.
Jul 19 '05 #14
"Peter Olcott" <ol****@worldnet.att.net> wrote in message news:<ey*********************@bgtnsc04-news.ops.worldnet.att.net>...
I guess the thing Peter wants to do is this:

Imagine a relational data base system. At the moment you access a table
you don't know what fields are there in which order and what data type
each of this fields have. So Peter needs a way to construct such a
structure representing a record in the table during runtime.


Yes just like this...
But IMHO he makes the same mistake he did one and a half year ago:
premature optimization. Fiddeling with void pointers and casting
forth and back to save some nanoseconds in the middle of some rarely
used functions instead of starting with a rock solid approach which
involves a class hierarchy, where eg. there are classes which represent
different types of fields and collecting those fields in a vector in
a polymorphic way. If the rock solid approach turns out to be to slow,
one can always go back and change that (with the help of a profiler),
but starting with void pointers and knowing that lots of casts will be
needed, paired with flags and type identifiers is a safe bet, that lots
of programmer time will be wasted.

--
Karl Heinz Buchegger
kb******@gascad.at


Okay now you have said what not to do, what about what to do?
What are the options for dynamically creating structures to hold
arbitrary database records?


I guess you already did say what to do, when I skimmed what
you said, and realized that your solution would not apply to
my situation, I disregarded it as if you did not provide an
answer. Because I read through all of the messages in the
three minutes before I left for work, I did not give your
reply the attention that it deserved.

Anyway, I have my answer, and it is pretty simple. My earlier version
is under a thread named "What is wrong with the "for" loop?" The
final version has an additional "std::vector<AllType>* ListAll"
within its union. This answer is equivalent to the best answer on
the moderated group, except, I have figured out how to avoid the
type cast, and TypeCode field.

My goal is to produce an interpreter that runs as fast as compiled
code. I can get in the ballpark with these kinds of technologies.
I have benchmarked similar technology, and it has proven to be
quite fast.
Jul 19 '05 #15

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by pmclinn | last post: by
9 posts views Thread by Chris | last post: by
2 posts views Thread by Nathan Sokalski | last post: by
1 post views Thread by Waqarahmed | last post: by
reply views Thread by Salome Sato | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.