Wie weise ich variabler Größe Strukturen zusammenhängend im Speicher?

https://stackoverflow.com/questions/1626846

06-07-2019
|

Frage

Ich bin mit C ++, und ich habe die folgenden Strukturen:

struct ArrayOfThese {
  int a;
  int b;
};

struct DataPoint {
  int a;
  int b;
  int c;
};

In Erinnerung mag ich habe 1 oder mehr ArrayOfThese Elemente am Ende eines jeden Datapoint. Es ist nicht immer die gleiche Anzahl von ArrayOfThese Elementen pro Datapoint.

Weil ich eine lächerliche Anzahl von Datenpunkten zu montieren und dann über ein Netzwerk zu streamen, ich will alle meine Datapoints und ihre ArrayOfThese Elemente zusammenhängend sein. Wasting Raum für eine feste Anzahl der ArrayOfThese Elemente ist nicht akzeptabel.

C, würde ich am Ende des Datapoint, ein Element gemacht haben, das als ArrayOfThese d[0]; erklärt wurde, zugeteilt ein Datapoint zuzüglich genug zusätzliche Bytes für wie viele Elemente ArrayOfThese ich hatte, und verwendet, um die Dummy-Array-Index in sie hinein. (Natürlich ist die Anzahl der ArrayOfThese Elemente würden in einem Feld von Datapoint sein.)

In C ++ wird mit Platzierung neuer und derselben 0-Array mit der Länge der richtige Ansatz hacken? Wenn ja, ist die Platzierung neue Garantie, dass nachfolgende Aufrufe neu aus dem gleichen Speicherpool wird zuteilen aneinander angrenzend?

Lösung

Da Ihr structs PODs sind könnten Sie tun es auch so wie man es in C. Das einzige, was Sie brauchen, ist eine Besetzung. Unter der Annahme, n wird die Anzahl der Dinge zuzuordnen:

DataPoint *p=static_cast<DataPoint *>(malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese)));

Placement neu in diese Art der Sache kommt, wenn Ihre Objekte einen einen nicht-trivialen Konstruktor haben. Es garantiert nichts über irgendwelche Zuweisungen aber für sie nicht selbst die Zuweisung tut und erfordert die Speicher bereits irgendwie zugeordnet wurden. Stattdessen behandelt es den Block des Speichers als Raum für die bis jetzt noch unconstructed Objekt übergeben, ruft dann die richtige Konstruktor es zu konstruieren. Wenn Sie es verwenden, so könnte der Code wie folgt gehen. Angenommen, DataPoint hat das ArrayOfThese arr[0] Mitglied Sie vorschlagen:

void *p=malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese));
DataPoint *dp=new(p) DataPoint;
for(size_t i=0;i<n;++i)
    new(&dp->arr[i]) ArrayOfThese;

Was aufgebaut wird muss zerstört erhalten, also, wenn Sie dies tun, sollten Sie auch den Ruf des destructor auszusortieren.

(Ich persönlich empfehle PODs in einer solchen Situation zu verwenden, da es keine Notwendigkeit beseitigt Konstruktoren und Destruktoren zu nennen, aber diese Art der Sache kann vernünftigerweise sicher erfolgen, wenn Sie vorsichtig sind.)

Andere Tipps

Da Sie mit einfachen Strukturen handeln, die keine Konstrukteure haben, Sie zu C Speicherverwaltung zurückkehren könnten:

void *ptr = malloc(sizeof(DataPoint) + n * sizeof(ArrayOfThese));
DataPoint *dp = reinterpret_cast<DataPoint *>(ptr));
ArrayOfThese *aotp = reinterpet_cast<ArrayOfThese *>(reintepret_cast<char *>(ptr) + sizeof(DataPoint));

Wie Adrian sagte in seine Antwort , was Sie im Speicher tun nicht das gleiche sein wie was Sie das Netzwerk streamen. In der Tat könnte es sogar gut sein, dies zu deutlich unterteilt, weil ein Kommunikationsprotokoll mit Berufung auf Ihren Daten in einer bestimmten Art und Weise ausgebildet sind, sehr großes Problem macht, wenn Sie später Ihre Daten Refactoring müssen.

Die C ++ Art und Weise eine beliebige Anzahl von Elementen zusammenhängend zu speichern ist natürlich std::vector. Da Sie dies nicht einmal in Betracht ziehen haben, gehe ich davon aus, dass es etwas ist, das dies nicht wünschenswert macht. (Haben Sie haben nur eine kleine Anzahl von ArrayOfThese und fürchten den Raum Overhead mit std::vector verbunden?)

Während der Trick mit über Zuweisung ein Null-Länge-Array wahrscheinlich nicht zur Arbeit ist garantiert und vielleicht, technisch gesehen, das gefürchtete undefinierte Verhalten aufrufe, ist es eine weit verbreitet ein. Welche Plattform sind Sie? Unter Windows wird dies in der Windows-API durchgeführt, so ist es schwer, einen Anbieter Versand ein C ++ Compiler, sich vorzustellen, die dies nicht unterstützen würde.

Wenn es nur eine begrenzte Anzahl von möglichen ArrayOfThese Elementzählwerte ist, können Sie auch benutzen fnieto Trick die wenigen spezifizieren Zahlen und new eine der resultierenden Template-Instanzen, in Abhängigkeit von der Laufzeit Zahl dann:

struct DataPoint {
  int a;
  int b;
  int c;
};

template <std::size_t sz>
struct DataPointWithArray : DataPoint {
  ArrayOfThese array[sz];
};

DataPoint* create(std::size_t n)
{
  switch(n) {
    case 1: return new DataPointWithArray[1];
    case 2: return new DataPointWithArray[2];
    case 5: return new DataPointWithArray[5];
    case 7: return new DataPointWithArray[7];
    case 27: return new DataPointWithArray[27];
    default: assert(false);
  }
  return NULL;
}

Vor dem C ++ 0X hatte die Sprache nicht Speichermodell zu sprechen. Und mit dem neuen Standard, ich erinnere mich nicht die Rede von Garantien der Kontiguität.

In Bezug auf diese besondere Frage, es klingt, als ob das, was Sie wollen ein Pool Allocator ist, gibt es viele Beispiele, von denen. Betrachten wir zum Beispiel, Modern C ++ Entwurf , von Alexandrescu. Das kleine Objekt allocator Diskussion ist, was Sie betrachten sollten.

Ich denke, boost::variant dies erreichen könnte. Ich habe nicht die Möglichkeit, es zu benutzen hatte, aber ich glaube, es ist ein Wrapper um die Gewerkschaften, und so ein std::vector von ihnen sollte zusammenhängend sein, aber natürlich jedes Element wird die größere der beiden Größen nehmen, können Sie nicht haben ein Vektor mit unterschiedlich großen Elementen.

Werfen Sie einen Blick auf die

Scheint, wie es einfacher wäre, ein Array von Zeigern zu verteilen und eher mit der Arbeit als mit Platzierung neu. Auf diese Weise könnten Sie einfach das gesamte Array auf die neue Größe mit wenig Laufzeit Kosten umverteilen. Auch wenn Sie die Platzierung verwenden, um neue, müssen Sie explizit auf Destruktoren aufrufen, die nicht-Platzierung und die Platzierung in einem einzigen Array Mischmittel gefährlich ist. Lesen Sie http://www.parashift.com/c++-faq-lite/dtors .html bevor Sie etwas tun.

keine Datenorganisation in Ihrem Programm und Datenorganisation für die Serialisierung verwechseln. Sie nicht das gleiche Ziel haben

für über eine Netzwerk-Streaming, haben Sie beiden Seiten des Kanals zu betrachten, das Senden und die Empfangsseite: wie kann die Empfangsseite zwischen einem Datapoint und einer ArrayOfThese unterscheiden? wie weiß die Empfangsseite, wie viele ArrayOfThese werden nach einer Datapoint angehängt? (Auch zu berücksichtigen:? Was ist die Byte-Reihenfolge von jeder Seite haben Datentypen die gleiche Größe im Speicher haben)

persönlich, ich glaube, Sie brauchen eine andere Struktur für die Daten-Streaming, bei dem Sie die Anzahl der Datapoint fügen Sie sowie die Anzahl der ArrayOfThese nach jedem Datapoint senden. Ich würde auch über die Art und Weise Daten nicht kümmere bereits in meinem Programm organisiert und reorganisiert / Neuformatierung meines Protokoll zu entsprechen und nicht mein Programm. danach eine Funktion zum Senden und eine andere für den Empfang zu schreiben ist keine große Sache.

Warum nicht Datapoint enthalten eine variable Länge Reihe von ArrayOfThese Artikel? Dies wird in C oder C ++ arbeiten. Es gibt einige Bedenken, wenn eine Struktur enthält nicht-primitive Typen

Aber mit free () statt löschen auf das Ergebnis:

struct ArrayOfThese {
  int a;
  int b;
};


struct DataPoint {
  int a;
  int b;
  int c;
  int length;
  ArrayOfThese those[0];
};

DataPoint* allocDP(int a, int b, int c, size_t length)
{
    // There might be alignment issues, but not for most compilers:
    size_t sz = sizeof(DataPoint) + length * sizeof(ArrayOfThese);
    DataPoint dp = (DataPoint*)calloc( sz );
    // (Check for out of memory)
    dp->a = a; dp->b = b; tp->c = c; dp->length = length;
}

Dann können Sie es „normal“ in einer Schleife verwenden, wenn die Datapoint seine Länge kennt:

DataPoint *dp = allocDP( 5, 8, 3, 20 );

for(int i=0; i < dp->length; ++i)
{
    // Initialize or access: dp->those[i]
}

Könnten Sie diese in Klassen mit dem gleichen Ober machen und dann Ihre Lieblinge stl Behälter der Wahl verwenden, die übergeordnete Klasse als Vorlage verwenden?

Zwei Fragen:

Ist die Ähnlichkeit zwischen ArrayOfThese und Datapoint real, oder eine Vereinfachung für die Buchung? D. h der wirkliche Unterschied ist nur ein int (oder eine beliebige Anzahl von der gleichen Art von Artikel)?
Ist die Anzahl der ArrayOfThese mit einem bestimmten Datapoint zum Zeitpunkt der Kompilierung bekannt verbunden?

Wenn das erste wahr ist, würde ich ernsthaft darüber nachdenken, einfach eine Reihe von so viele Punkte wie nötig für ein Datapoint + N ArrayOfThese zuordnet. Ich würde dann ein schnelles Stück Code baut Betreiber zu Überlastung [] für die Rückkehr Artikel N + 3, und überlasten a (), b () und c (), um die ersten drei Punkte zurück.

Wenn die zweiten wahr ist, wollte ich im Wesentlichen vorschlagen, was ich sehe fnieto hat gerade geschrieben, so dass ich nicht mehr ins Detail gehen.

Was die Platzierung neuer geht, ist es nicht wirklich etwas über Zuordnung garantieren - in der Tat, die ganze Idee über die Platzierung neu ist, dass es auf der Speicherzuordnung völlig unabhängig ist. Vielmehr ermöglicht es Ihnen, ein Objekt an einer beliebigen Adresse (je nach Ausrichtung Beschränkungen) in einem Speicherblock zu erstellen, die bereits zugewiesen wird.

Hier ist der Code, den ich am Ende schriftlich:

#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;

struct ArrayOfThese {
  int e;
  int f;
};

struct DataPoint {
  int a;
  int b;
  int c;
  int numDPars;
  ArrayOfThese d[0];

  DataPoint(int numDPars) : numDPars(numDPars) {}

  DataPoint* next() {
    return reinterpret_cast<DataPoint*>(reinterpret_cast<char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese));
  }

  const DataPoint* next() const {
    return reinterpret_cast<const DataPoint*>(reinterpret_cast<const char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese));
  }
};

int main() {
  const size_t BUF_SIZE = 1024*1024*200;

  char* const buffer = new char[BUF_SIZE];
  char* bufPtr = buffer;

  const int numDataPoints = 1024*1024*2;
  for (int i = 0; i < numDataPoints; ++i) {
    // This wouldn't really be random.
    const int numArrayOfTheses = random() % 10 + 1;

    DataPoint* dp = new(bufPtr) DataPoint(numArrayOfTheses);

    // Here, do some stuff to fill in the fields.
    dp->a = i;

    bufPtr += sizeof(DataPoint) + numArrayOfTheses * sizeof(ArrayOfThese);
  }

  DataPoint* dp = reinterpret_cast<DataPoint*>(buffer);
  for (int i = 0; i < numDataPoints; ++i) {
    assert(dp->a == i);
    dp = dp->next();
  }

  // Here, send it out.

  delete[] buffer;

  return 0;
}

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow