Как распределить структуры переменного размера в памяти?

Question

Я использую C ++, и у меня есть следующие структуры:

struct ArrayOfThese {
  int a;
  int b;
};

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

В памяти я хочу иметь 1 или несколько элементов ArrayOfThese в конце каждой DataPoint. В DataPoint не всегда одинаковое количество элементов ArrayOfThese.

Поскольку у меня смешное количество точек DataPoints, которые нужно собрать и затем передать по сети, я хочу, чтобы все мои точки DataPoints и их элементы ArrayOfThese были смежными. Потеря места для фиксированного числа элементов ArrayOfThese недопустима.

В C я бы сделал элемент в конце DataPoint, который был объявлен как ArrayOfThese d[0];, выделил DataPoint плюс достаточно дополнительных байтов для любого количества элементов ArrayOfThese, которые у меня были, и использовал бы фиктивный массив для индексации в них. (Конечно, количество элементов ArrayOfThese должно быть в поле DataPoint.)

В C ++ использование размещения новых и того же массива 0 длины взламывает правильный подход? Если это так, гарантирует ли размещение новых, что последующие вызовы новых из того же пула памяти будут распределяться непрерывно?

Answer 1

Поскольку вы имеете дело с простыми структурами, у которых нет конструкторов, вы можете вернуться к управлению памятью на C:

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));

Answer 2

Поскольку ваши структуры - это PODы, вы можете делать это так же, как в C. Единственное, что вам нужно, это приведение. Предполагая, что n - это количество вещей, которые нужно выделить:

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

Размещение новых действительно входит в такого рода вещи, если ваши объекты имеют нетривиальный конструктор. Он ничего не гарантирует ни о каких выделениях, поскольку не выделяет себя сам и требует, чтобы память уже была каким-то образом распределена. Вместо этого он обрабатывает блок памяти, переданный как пространство для еще не построенного объекта, а затем вызывает правильный конструктор для его создания. Если бы вы использовали его, код мог бы пойти так. Предположим, у DataPoint есть ArrayOfThese arr[0] член, которого вы предлагаете:

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;

То, что создается, должно быть разрушено, поэтому, если вы сделаете это, вы должны также разобраться с вызовом деструктора.

(Лично я рекомендую использовать POD в такой ситуации, потому что это устраняет необходимость вызывать конструкторы и деструкторы, но такого рода вещи можно сделать достаточно безопасно, если вы будете осторожны.)

Answer 3

Как сказал Адриан в своем ответе , то, что вы делаете в памяти, не должно совпадать с тем, что вы делаете по сети. На самом деле, было бы даже неплохо четко разделить это, потому что наличие протокола связи, основанного на том, что ваши данные разрабатываются особым образом, создает огромную проблему, если впоследствии вам потребуется рефакторинг данных.

C ++ способ хранить произвольное количество элементов непрерывно, конечно, std::vector. Поскольку вы даже не рассматривали это, я предполагаю, что есть что-то, что делает это нежелательным. (У вас есть только небольшое количество ArrayOfThese и вы боитесь пространства, связанного с std::vector?)

Хотя хитрость с перераспределением массива нулевой длины, вероятно, не гарантированно работает и может технически вызвать ужасное неопределенное поведение, оно широко распространено. На какой ты платформе? В Windows это делается в Windows API, поэтому сложно представить поставщика, поставляющего компилятор C ++, который бы не поддерживал это.

Если число элементов ArrayOfThese ограничено, вы также можете использовать трюк fnieto , чтобы указать эти несколько чисел, а затем new один из результирующих экземпляров шаблона, в зависимости от выполнения. номер времени:

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;
}

Answer 4

Почему бы DataPoint не содержать массив переменной длины ArrayOfThese элементов? Это будет работать на C или C ++. Есть некоторые опасения, если какая-либо структура содержит не примитивные типы

Но используйте free () вместо delete для результата:

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;
}

Затем вы можете использовать его «обычно» в цикле, когда DataPoint знает его длину:

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

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

Answer 5

не путайте организацию данных внутри вашей программы и организацию данных для сериализации: они не имеют одной и той же цели.

для потоковой передачи по сети необходимо учитывать обе стороны канала, отправляющую и принимающую стороны: как принимающая сторона различает DataPoint и ArrayOfThese? как принимающая сторона узнает, сколько ArrayOfThese добавлено после DataPoint? (также для рассмотрения: каков порядок байтов каждой стороны? типы данных имеют одинаковый размер в памяти?)

лично я думаю, что вам нужна другая структура для потоковой передачи ваших данных, в которой вы добавляете количество отправляемых вами DataPoint, а также число ArrayOfThese после каждого DataPoint. я также не буду заботиться о том, как данные уже организованы в моей программе, и реорганизовать / переформатировать в соответствии с моим протоколом, а не моей программой. после этого написание функции для отправки и другой для получения не имеет большого значения.

Answer 6

Похоже, было бы проще выделить массив указателей и работать с этим, а не использовать размещение new. Таким образом, вы можете просто перераспределить весь массив на новый размер с небольшими затратами времени выполнения. Также, если вы используете размещение new, вы должны явно вызывать деструкторы, что означает, что смешивать не размещение и размещение в одном массиве опасно. Прочитайте http://www.parashift.com/c++-faq-lite/dtors.html, прежде чем что-либо делать.

Answer 7

Я думаю, boost::variant может сделать это. У меня не было возможности использовать его, но я считаю, что это обертка вокруг профсоюзов, и поэтому std::vector из них должны быть смежными, но, конечно, каждый элемент будет занимать больший из двух размеров, вы можете ' вектор с элементами разного размера.

Взгляните на сравнение надстройки :: варианта и наддува :: любой .

Если вы хотите, чтобы смещение каждого элемента зависело от композиции предыдущих элементов, вам придется написать свой собственный распределитель и методы доступа.

Answer 8

До C ++ 0X язык имел модель памяти нет . А с новым стандартом я не припоминаю никаких разговоров о гарантиях смежности.

Что касается этого конкретного вопроса, то звучит так, как будто вы хотите, чтобы это был распределитель пулов, существует множество примеров. Рассмотрим, например, Modern C ++ Design , автор Alexandrescu. Обращаем внимание на обсуждение распределителя небольших объектов.

Answer 9

Вот код, который я написал в итоге:

#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;
}

Answer 10

Два вопроса:

1. Является ли сходство между ArrayOfThese и DataPoint реальным или упрощением для публикации? То есть реальная разница - только одно целое (или произвольное число предметов одного типа)?
2. Известно ли число ArrayOfThese, связанных с конкретным объектом DataPoint, во время компиляции?

Если первое верно, я бы подумал о том, чтобы просто выделить массив из столько элементов, сколько необходимо для одного DataPoint + N ArrayOfThese. Затем я бы быстро создал код для перегрузки оператора [], чтобы он возвращал элемент N + 3, и перегрузки a (), b () и c () для возврата первых трех элементов.

Если второе верно, я собирался по существу предложить то, что, как я вижу, только что опубликовал fnieto, поэтому я не буду вдаваться в подробности.

Что касается размещения new, то на самом деле это ничего не гарантирует о выделении ресурсов - фактически, вся идея размещения новых заключается в том, что это совершенно не связано с выделением памяти. Скорее, он позволяет вам создать объект по произвольному адресу (с учетом ограничений выравнивания) в блоке памяти, который уже выделен.