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

Я использую 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++ правильно ли использовать размещение нового и того же массива нулевой длины? Если это так, гарантирует ли размещение новых, что последующие вызовы новых из того же пула памяти будут распределяться непрерывно?

Источник

11 ответов

Решение

Так как ваши структуры - это 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 в такой ситуации, потому что это устраняет необходимость вызывать конструкторы и деструкторы, но такого рода вещи можно сделать достаточно безопасно, если вы будете осторожны.)

Источник

Поскольку вы имеете дело с простыми структурами, которые не имеют конструкторов, вы можете вернуться к управлению памятью на 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));
Источник

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

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;
}
Источник

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

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

Источник

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

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

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

Источник

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

Источник

Почему бы 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]
}
Источник

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

Взгляните на сравнение boost:: option и boost:: any.

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

Источник

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

#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;
}
Источник

Не могли бы вы превратить их в классы с тем же суперклассом, а затем использовать свой любимый контейнер stl по своему выбору, используя суперкласс в качестве шаблона?

Источник

Два вопроса:

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

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

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

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

Источник
Другие вопросы по тегам