Zur Laufzeit festgelegte Feldgrößen in komplexen Datentypen

Zsar

Das Problem stellt sich, wenn man einerseits zusammenhängende Daten wünscht, andererseits die Größe des Datentyps erst zur Laufzeit (z.B. aus einer Datei oder als Kommandozeilenparameter eingelesen) festlegen möchte.

In jeder Funktion ist etwas derartiges möglich:

int main()
{
  double wert;
  double koordinaten[<variable>];
[...]
}

Will man das Ganze aber verpacken, wird es komplizierter:

struct Nest
{
  double wert;
  double koordinaten[<variable>];
}

Geht nicht. Es muss eine Konstante sein, insbesonders: eine zur Kompilierzeit bekannte Konstante.

Will man das umgehen, kann man mit ein bisschen altbackenem C so etwas tun:

typedef struct Nest
{
  double wert;
  double koordinaten[];
} Nest;

Nest * LeeresNest(const unsigned int & dimension)
{
  return (Nest *)malloc((1 + dimension) * sizeof(double));
}

Aber natürlich gibt es dabei zwei Einschränkungen:

reserviert malloc nur auf dem Heap,
kann man unter dem Feld natürlich keine anderen Variablen mehr eintragen, weil der Compiler "koordinaten[]" als 0-elementiges Feld betrachtet.
Damit kann man diesen Trick natürlich nur einmal pro Struct anwenden.

Zu 1) - idealerweise sollte solch eine Datenstruktur in dem Speicherbereich zu liegen kommen können, in dem sich die sie enthaltende Datenstruktur befindet:

unsigned int dimension = 4;

void funktionA()
{
  Nest <Nest auf Stack>;
[...]
}

void funktionB()
{
  Nest * nest = LeeresNest(dimension);
}

class Nesthalter
{
  Nest nest;
}

void funktionC()
{
  Nesthalter n; // Nest auf Stack, weil Halter auf Stack
}

void funktionD()
{
  Nesthalter * n = new Nesthalter(); // Nest auf Heap, weil Halter auf Heap
}

Wie ist das zu realisieren?

Zu 2) - es ist selbstverständlich, dass dieses Vorgehen für große Felder ungeeignet ist; sind die Felder aber individuell klein, warum sollten sich nicht mehrere in einer Datenstruktur finden - tatsächlich ist dies doch der urtypischste Nutzen eines Structs: Heterogene Daten in einem Behältnis zusammenzufassen.
Technisch betrachtet sollte es möglich sein, die Definition des Structs zur Laufzeit durch Reflektion anzugleichen, ganz speziell dann, wenn sich die gewünschte Größe zur Laufzeit nicht mehr ändert, nachdem man sie einmal festgelegt hat. Aber das ist natürlich nicht mehr C++, das ist dann Hexeditiererei und wer weiß, ob es immernoch funktioniert, wenn man den Compiler optimieren lässt.

typedef struct Nest
{
  double wert;
  double koordinaten[];
  double wertigkeiten[];
} Nest;

Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
{
  return (Nest *)malloc((1 + dimension + bewohner) * sizeof(double));
}

int main()
{
  Nest * nest = LeeresNest(2, 3);
  nest->wert = 1.;
  nest->koordinaten[0] = 2.;
  nest->koordinaten[1] = 3.;
  nest->wertigkeiten[0] = 4.; // überschreibt koordinaten[0]
  nest->wertigkeiten[1] = 5.; // überschreibt koordinaten[1]
  nest->wertigkeiten[2] = 6.; // speichert an eigentlichem wertigkeiten[0]

  cout << nest->wert;
  cout << nest->koordinaten[0] << nest->koordinaten[1];
  cout << nest->wertigkeiten[0] << nest->wertigkeiten[1] << nest->wertigkeiten[2] << endl;
  // Ausgabe: 145456 Erwünscht: 123456

  return 0;
}

Gibt es eine elegante Möglichkeit, ohne selbst-Hacking mehrere zur Laufzeit festgelegte Felder in einen Strukt zu bekommen und dennoch jedes Element auf die übliche Weise (<struct>.<element>) ansteuern zu können?
Bzw. allgemeiner:
Wie realisiert man elegant die Ansteuerung von Elementen, die nach einem zur Laufzeit festgelegten Feld gelegen sind?

KN4CK3R

std::vector hilft bei deinem Array Problem

greetz KN4CK3R

Kellerautomat

Das ist auch bei lokalen Variablen derzeit nicht erlaubt.

DNKpp

jo, std::vector sollte das problem eigentlich lösen.
wenn du jetzt aber deine elemente nicht per ID ansprechen möchtest, sondern wie in z.B. php mit namen, dann empfiehlt es sich für dich, std::map auszuprobieren.
wenn deine einzelnen elemente dann auch noch unterschiedliche datentypen haben sollen (int, uint, float, bool, etc) gibt es die möglichkeit für ein variant als datentyp, oder eben eine selbsterstelle klasse mit einer union.

Nexus

LordZsar1 schrieb:

In jeder Funktion ist etwas derartiges möglich:
int main()
{
  double wert;
  double koordinaten[<variable>];
[...]
}

Nein, ist es nicht. Variable Length Arrays sind kein gültiges C++, sondern eine g++-Compilererweiterung.

Swordfish

Davon abgesehen, das KN4CK3R und anti-freak imo an der Frage des OPs vorbeigeschrieben haben...

anti-freak schrieb:

[...] wenn deine einzelnen elemente dann auch noch unterschiedliche datentypen haben sollen (int, uint, float, bool, etc) gibt es die möglichkeit für ein variant als datentyp (a), oder eben eine selbsterstelle klasse mit einer union (b).

Zeig' doch bitte a und b ...

DNKpp

Swordfish schrieb:

Davon abgesehen, das KN4CK3R und anti-freak imo an der Frage des OPs vorbeigeschrieben haben...

dann erklär DU es ihm doch richtig...

ich habe auf

Wie realisiert man elegant die Ansteuerung von Elementen, die nach einem zur Laufzeit festgelegten Feld gelegen sind?

geantwortet.

Swordfish schrieb:

anti-freak schrieb:

[...] wenn deine einzelnen elemente dann auch noch unterschiedliche datentypen haben sollen (int, uint, float, bool, etc) gibt es die möglichkeit für ein variant als datentyp (a), oder eben eine selbsterstelle klasse mit einer union (b).

Zeig' doch bitte a und b ...

a:

std::map<std::string, VARIANT>

ob ich jetzt für VARIANT QVariant, COMVariant oder sonst was nehme ist egal. sind lediglich imo ein wenig besser ausdefiniert.

b:

enum FooType
{
   TYPE_NONE,
   TYPE_TYP1,
   TYPE_TYP2
};
class Foo
{
   Foo() { memset(&m_Union, NULL, sizeof(m_Union)); }
   bool GetVarValue(Typ1 &value)
   {
      if (m_Type != TYPE_TYP1)
         return false;

      value = *m_Union.m_pTyp1;
      return true;
   }

   void SetVar(Typ1 *pPointer)
   {
      if (m_Type != TYPE_NONE)
         ReleaseVar();

      m_Union.m_pType1 = pPointer;
      m_Type = TYPE_TYP1;
   }

   void SetVar(Typ2 *pPointer)
   {
      if (m_Type != TYPE_NONE)
         ReleaseVar();

      m_Union.m_pType2 = pPointer;
      m_Type = TYPE_TYP2;
   }

   void ReleaseVar()
   {
      switch(m_Type)
      {
      case TYPE_TYP1: delete m_Union.m_pTyp1; break;
      ...
      }
   }
private:
   FooType m_Type;
   union
   {
      Typ1 *m_pTyp1;
      Typ2 *m_pTyp2;
   } m_Union;
};

std::map<std::string, Foo> Map;

ist lediglich ein gedankengang von mir. ob das jetzt tatsächlich so funktionieren wird, ist eine andere geschichte. getestet hab ichs nicht, da ich bei der arbeit bin.
Für Typ1 und Typ2 sind natürlich eigene klassen/structuren gemeint.

Zsar

Auf den ersten Blick sollte sich aus std::vector die Lösung ableiten lassen: Die Klasse garantiert, dass alle Elemente in einem zusammenhängenden Speicherblock abgelegt werden und es wird explizit darauf hingewiesen, dass bei Erschöpfung dieses Speicherblockes alle Elemente umgelagert werden.
... Nur leider sagt das nichts darüber aus, wo dieser zusammenhängende Speicherbereich angelegt wird - das Ziel ist aber gerade, denselben direkt anliegend an den übrigen Variablen des Structs zu haben.
Genauer nutzt std::vector einen std::allocator und derselbe diese Methode, also explizit den new-Operator, was bedeutet, dass der Speicherbereich irgendwo im Heap zu liegen kommt.

Kein Glück damit.

Dasselbe Spiel mit std::map - allokiert Schlüssel/Wert-Paare, aber dieselben irgendwo und sogar reichlich sicher nicht beieinander.

Diese Erkenntnisse lassen zumindest eine Generalisierung der Aufgabenstellung zu:

Wie reserviere ich einen arbiträr großen Speicherbereich auf dem Stack?
Wie strukturiere ich pseudo-Struct/Member-mäßig einen arbiträr großen Speicherbereich?

Damit ließen sich die ursprünglichen speziellen Probleme bequem lösen.

Zu 1) - Es gibt wohl eine nicht-standardisierte Funktion alloca, die genau das tut. Es gibt reichlich Grund, diese nicht zu benutzen... Aber ist das denn wirklich der einzige Weg? Kann doch nicht angehen!
Zu 2) - const Funktionen für die Offsets (gäben Zeiger zurück) sind eine mögliche Lösung. Einfacher?

@anti-freak b:
Tut diese Klasse nicht nichts anderes als die normale Eigenschaft einer Union zu kapseln? Ich sehe aber, wie Union vonnutzen sein kann:

typedef union Element
{
  <Elementtypen>
} Element;

vector<Element> Nest = new vector();
vector.resize(<Gesamtgröße>/sizeof(Element));

Damit hätte ich gegenüber meinem Struct-Beispiel nichts gewonnen - ich müsste immernoch die Offsets aufrechnen. Natürlich kann ich das tun, aber das konnte ich auch schon bei der "Oldschool"-Variante mit malloc.
... Vorteil ist natürlich, dass ich hier keine überlappenden Indizes mehr habe, also ist es zumindest schon einmal besser benutzbar als mein Entwurf
- lässt aber dafür Lücken, sobald die Elementtypen nicht mehr alle gleich groß sind!

Nachtrag:
Habe Folgendes versucht:

typedef struct Nest
{
  double wert;
  double koordinaten[];
  double * wertigkeiten;
} Nest;

Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
{
  Nest * ausgabe = (Nest *)malloc((1 + dimension + bewohner) * sizeof(double));

  ausgabe->wertigkeiten = ausgabe->koordinaten + dimension;

  return ausgabe;
}

Hätte gegenüber einer Funktion den Vorteil, dass man die Feld-Syntax beibehalten könnte.
- Funktioniert aber nicht. Wenn das nicht Ursache eines dummen Fehlers ist, den ich aufgrund der fortgeschrittenen Stunde gerade nicht erkenne, kann ich nicht einmal sagen, warum.

Nachtrag 2:

Upps, ich muss an den "Doof"-Knopf gekommen sein. Kann ja nicht gehen!
So funktioniert's:

typedef struct Nest
{
  double wert;
  double * koordinaten;
  double * wertigkeiten;
} Nest;

Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
{
  Nest * ausgabe = (Nest *)malloc(2 * sizeof(double *) + (1 + dimension + bewohner) * sizeof(double));

  ausgabe->koordinaten  = (double *)(&ausgabe->wertigkeiten + 1);
  ausgabe->wertigkeiten = ausgabe->koordinaten + dimension;

  return ausgabe;
}

int main()
{
  Nest * nest = LeeresNest(2, 3);
  nest->wert = 1.;
  nest->koordinaten[0] = 2.;
  nest->koordinaten[1] = 3.;
  nest->wertigkeiten[0] = 4.;
  nest->wertigkeiten[1] = 5.;
  nest->wertigkeiten[2] = 6.;

  cout << nest->wert;
  cout << nest->koordinaten[0] << nest->koordinaten[1];
  cout << nest->wertigkeiten[0] << nest->wertigkeiten[1] << nest->wertigkeiten[2] << endl;
  //Ausgabe: 123456; Wunderbar.

  return 0;
}

Overhead hält sich auch in Grenzen: Zwei Zeigerauflösungen statt einer pro Feldzugriff. Wenn das nun noch herauszugeizen wäre, wär's natürlich ideal!

Skym0sh0

wenn ich das bis hierhin richtig verstanden habe (da bin ich mir absolut nicht sicher), dann hättest du gerne ein struct, was folgendes kann:
- beliebig viele elemente aufnehmen (erst zur laufzeit bekannt)
- diese elemente haben teilweise beliebige datentypen
- der speicherbereich soll auf dem stack sein
- der speicherbereich soll komplett zusammenhängend sein

da drängt sich mir die frage auf, was hast du vor?
auf der anderen seite, warum stellst du deine frage im C++ forum, schreibst aber alles in C? Denn:
- zusammenhängenden speicher hast du bei std::vector (wie shcon jemand gesagt)
- die Indizierung geht per Index oder mit anderen Datenstrukturen per beliebigen Typen
- selbst die Typsicherheit kannst du mit boost::variant (heist das ding so?!) aushebeln/ausnutzen

aber interessanter Sprachstil den du verwendest

Eisflamme

boost::any heißt das, glaub ich.

Also ich glaube, dass das nicht geht, weil man einfach nichts dynamisch auf dem Stack anlegen kann. Wieso soll das so sein?

Du kannst ein großes Array auf den Stack legen und den Allocator von std::vector umschreiben, dass er dieses benutzt.
Alternativ selbst eine Klasse schreiben, die verschieden lange Arrays mit Operator [] unterstützt und ein statisches Array hat, das als Speicher dient. Das hat natürlich den Nachteil, dass du fast immer Speicher verschwendest oder dass der Speicher nicht reicht, weil es eben kein dynamischer Speicher ist.
Der Sinn, warum der Stack besser als der Heap ist erschließt sich mir auch nicht, der Speicher ist überall gleich schnell.

cooky451

50% der Leute hier scheinen nicht mal die Frage zu raffen.

@nwp3
Nicht unbedingt. 1. ist der Stack wohl meistens im Cache. 2. könnte man sich so eine Dereferenzierung sparen, weil alles am Stück liegt. Das kann durchaus (deutliche) Performancevorteile bringen. Das Ziel bzw. der Wunsch des TEs ist durchaus nachvollziebar.

Bleibt die Frage, wie man es sauber implementieren soll. Denn das Ganze bringt rein strukturell einige Probleme mit sich. Da die Größen nicht zur Compilezeit bekannt sind, sind alle dieser Dinger vom selben Typ. Niemand hindert einen also daran, einen std::vector<magic_type> anzulegen. Nur wird die Berechnung der Adresse von v[5] jetzt ziemlich aufwendig. Ich muss sagen, bei näherer Betrachtung macht es einfach nur mit Compiletime-Konstanten Sinn. Wenn man dann verschiedene haben will, nimmt man halt einfach Templates:

template <std::size_t Size1, std::size_t Size2>
struct foo
{
  double a;
  double b[Size1];
  double c;
  double d[Size2];
  double e;
};

cooky451 schrieb:

50% der Leute hier scheinen nicht mal die Frage zu raffen.

Du gehörst auch dazu.
Denn er will die Grössen eindeutig zur Laufzeit festgelegt haben.

Die einzige Möglichkeit, die ich sehe ist nonstandard mit alloca.

cooky451

Offensichtlich hast du nicht mal meinen Beitrag gelesen.

raffzahn schrieb:

cooky451 schrieb:

50% der Leute hier scheinen nicht mal die Frage zu raffen.

Du gehörst auch dazu.

cooky451 schrieb:

Ich muss sagen, bei näherer Betrachtung macht es einfach nur mit Compiletime-Konstanten Sinn.

Eisflamme

Könnt ihr Mal explizit werden? Ich verstehe Compiletime-Konstanten ebenfalls als nicht dem, was TE will, zugehörig.

Ich bleibe dabei, dass man zur Laufzeit eben nicht dynamisch auf dem Stack allokieren kann, ohne dass man mehr Speicher verwendet als meist nötig (oder wirklich das nicht-portable alloca verwendet, das ich aber nicht kenne). Wo ist in der Lösung mit CompileTime-Konstanten die Laufzeitdynamik enthalten?

Und wenn das so sinnvoll ist, wieso gibt es dann kein C++-Sprachmittel oder keine Variante mit boost? Ich kann auch nachvollziehen, dass der Stack bessere Cachelokalität bietet, aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.

cooky451

Eisflamme schrieb:

Ich kann auch nachvollziehen, dass der Stack bessere Cachelokalität bietet, aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.

Es geht nicht nur um den Stack, sondern auch um die "fehlende" Dereferenzierung. Das kann z.B. sowas:

for (auto& v : vv) 
  for (auto& e : v)

Wesentlich effizienter machen, wenn die e's verschiedener v's alle hintereinander liegen, und nicht kreuz und quer im Speicher verteilt sind. Und das gibt es nicht, weil verschiedene Variablen vom gleichen Typ dann unterschiedlich groß sind, und damit das funktioniert bräuchte man wieder Pointer (z.B. vector<magic_type*> oder magic_list<magic_type> o.Ä.) oder eine ziemlich aufwendige Index-Berechnung, und dann hätte man das gerade Gewonnene direkt wieder verloren.

Eisflamme

Neben dem zusätzlichen Argument für den Stack habe ich jetzt nicht ganz verstanden, worauf Dein Argument bezogen war. War das eine Begründung dafür, warum C++ von Haus aus nicht dynamische Stackvariablen anbietet?

cooky451

Das waren deine trifftigen Gründe:

aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.

Eisflamme

Ah, okay, das hätte ich jetzt auch geraten, wollte aber sichergehen. Danke