Практика работы с массивом структур на СИ

При чём тут Pure C, в котором невозможно изменить размер массива?

Его можно «менять» копированием — тогда empty array это тот array из которого получается singleton array при добавлении одного элемента. Пусть будет C++:

#include <array>
#include <iostream>

template <typename A, std::size_t n>
std::array<A, n + 1> add_back(const std::array<A, n> &arr, const A &el)
{
    std::array<A, n + 1> new_arr;
    for (std::size_t i = 0; i < n; ++i)
        new_arr[i] = arr[i];
    new_arr[n] = el;
    return new_arr;
}

int main()
{
    std::array<int, 0> zero;
    std::array<int, 1> one = add_back(zero, 1);
    std::array<int, 2> two = add_back(one, 2);
    std::array<int, 3> three = add_back(two, 3);

    for (int &x : three)
        std::cout << x << ' ';
    std::cout << std::endl;

    std::cout << zero.begin() << " - " << zero.end() << std::endl;
    std::cout << one.begin() << " - " << one.end() << std::endl;
    std::cout << two.begin() << " - " << two.end() << std::endl;
    std::cout << three.begin() << " - " << three.end() << std::endl;
}

/*

1 2 3 
0x7ff000108 - 0x7ff000108
0x7ff000100 - 0x7ff000104
0x7ff0000f0 - 0x7ff0000f8
0x7ff0000e0 - 0x7ff0000ec
==3933== 
==3933== HEAP SUMMARY:
==3933==     in use at exit: 0 bytes in 0 blocks
==3933==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated

 */

/*
 т.е.

 zero  -- 0  byte == 0 int
 one   -- 4  byte == 1 int
 two   -- 8  byte == 2 int
 three -- 12 byte == 3 int

 |....|....|....|    |....|....|    |    |....|    ||
 e0            ec    f0       f8         100       108
                                            104
 ----------------    -----------         ------    --
      three              two              one      zero

                 ----           ---------      ----
                   `----------------v-----------^
                                 layouts   

 */

Касательно примитивных типов — zero-length arrays не являются валидными в ISO C/C++, да, но они поддерживаются расширениями gcc/clang — http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html.

for (std::size_t i = 0; i < n; ++i) new_arr = arr;

Ну или std::copy(arr.begin(), arr.end(), new_arr.begin());

При чём тут Pure C

Пусть будет C++

да хоть пхп. При чём тут Pure C?

Это проблемы «Pure С» — просто по стандарту размер массивов должен быть строго больше нуля, иначе UB, ничего не знаем. Но пустые массивы от этого не становятся «багом ЯП», «НЁХ» или «делением на ноль» — с точки зрения системы типов они абсолютно нормальные вещи, в том числе в языках адекватных контролю за памятью со статическими массивами (непонятно, чего ты PHP всё время вспоминаешь), будь то std::array<Type, 0> в C++, Type[0] в D (http://dlang.org/arrays.html#static-arrays — «A static array with a dimension of 0 is allowed, but no space is allocated for it. It's useful as the last member of a variable length struct, or as the degenerate case of a template expansion.») или [Type * 0] в Rust (им бы ещё bottom type — в Rust он даже есть internal).

Иными словами, пустое множество — тоже множество, пустая коллекция — тоже упорядоченная коллекция, безотносительно специализации интерфейса такой упорядоченной коллекции (будь то списки, динамические или статические массивы, например).

Это проблемы «Pure С» — просто по стандарту размер массивов должен быть строго больше нуля, иначе UB, ничего не знаем.

просто ты не знаешь C. В нём «массив» - кусок памяти, такого размера M, в который может вместится N элементов. Размер эл-тов M/N. Если N равно нулю, то…

Иными словами, пустое множество — тоже множество

а с этим я и не спорил.

Если N равно нулю, то…

M тоже равно нулю, неопределённости 0/0 в школе изучают, вроде как (типа \lim_{x\to0} sin(x) / x = 1).

M тоже равно нулю, неопределённости 0/0 в школе изучают, вроде как (типа \lim_{x\to0} sin(x) / x = 1).

я - тупое быдло. Не понимаю, что такое «предел к нулю в ЦЕЛЫХ числах». Расскажешь? И откуда тут синус - тоже не понял.

И вообще - беги в школу, и учи матчасть. Спроси у своей учительницы, чему равно 0/0, если числа целые. Если оставят на второй год - я не виноват.

Реши уравнение N * x = M в целых числах при M = N = 0, то есть 0 * x = 0. Любое целое x _будет_ решением, но никакое _уникальное_ не будет. Вот у 0 * x = M при M > 0 не будет решений в целых числах вообще, да.

У нас x — размер элемента. Очевидно, что размер элемента из пустой коллекции не определён, так как в ней нет никаких элементов, тогда как сама пустая коллекция прекрасно определена — её минимальный тип это Array Bottom, как в Scala. Обратно, для любой вменяемой Seq (List, Array, ...) тип Seq Bottom населяет пустая коллекция и только она. В силу ковариантности имеем Bottom <: T => Array Bottom <: Array T для любого типа T, но относительно частичной операции [] предпочтителен, всё-таки, Array Bottom — если xs : Array Bottom, то xs[ i ] по любому индексу i сделать не получится в силу свойств Bottom (у него нет элементов с определёнными размерами это как минимум, нет элементов вообще — как максимум), тогда как при xs : Array Int и пустой коллекции для xs[ i ] с любым индексом частичная [] даст исключение или мусор.

Очевидно, что размер элемента из пустой коллекции не определён

То есть, по аналогии, какой размер ни возьми (что ни подставь в 0 * x = 0) — это ни на что не повлияет, у нас begin - end == 0, то есть памяти под массив никакой.

Ещё можно взять Array<ElementType, n> и определить два полинома ArraySize(n) = n * sizeof(ElementType) и ArrayElements(n) = n у которых есть общий корень n = 0, так что относительно него неопределённость 0/0 будет уникально разрешима (вообще, для двух полиномов она может быть уникально разрешима в ненулевой либо нулевой элемент поля относительно данного общего корня или неразрешима вообще относительно этого общего корня) и равна ArraySize(n) / ArrayElements(n) |_{n = 0} = n * sizeof(ElementType) / n |_{n = 0} = sizeof(ElementType) |_{n = 0} = sizeof(ElementType), то есть всё как и полагается — размер элемента = sizeof(ElementType).

Реши уравнение N * x = M в целых числах при M = N = 0, то есть 0 * x = 0. Любое целое x _будет_ решением, но никакое _уникальное_ не будет.

именно потому-то в коде C это невозможно реализовать. Там _любой_ элемент имеет тип, а следовательно размер. И потому ты не можешь объявить «массив целых из 0 целых». Вот в каком-то другом языке, где массив может что угодно вмещать - можешь. Можешь например класс в C++ написать, и помечать «ничто» с помощью NULL. Или ещё как-то. В C тоже можно, но не на уровне языка, а используя указатель, как я выше и предлагал. Для него тоже есть NULL, т.е. возможен указатель, который никуда не указывает. Также возможен void*, который указывает на что угодно.

То есть, по аналогии, какой размер ни возьми (что ни подставь в 0 * x = 0) — это ни на что не повлияет, у нас begin - end == 0, то есть памяти под массив никакой.

в принципе ты можешь_записать_ «0/0», как можешь и объявить массив в 0 эл-тов. Однако, такой массив невозможно никак использовать, по той же причине, почему нельзя делить на ноль. Это не имеет смысла.

Ты вообще понимаешь, что значит «выделение памяти для выделения пустоты»? Какой в этом сакральный смысл? Учитывая, что массив - это константа - сам массив изменить невозможно, можно менять лишь его содержимое. Как тебе авоська, в которую НИЧЕГО нельзя класть? Какой в такой авоське смысл?

именно потому-то в коде C это невозможно реализовать

В D и Rust же как-то реализовали на уровне примитивных типов. То есть, что мешает или что делает эту вещь багом в ЯП?

Там _любой_ элемент имеет тип, а следовательно размер

Элемент, то есть runtime значение, по определение имеет какой-то размер. Но тип != имеет элементы != имеет размер, он может существовать исключительно в compile-time и не иметь runtime представления (по крайней мере в виде каких-то данных в памяти).

Какой в такой авоське смысл?

Как ты и говоришь:

авоська, в которую НИЧЕГО нельзя класть

Аналогично можно спросить зачем в C++ std::tuple<>, когда для него даже std::get нельзя сделать.

Я выпишу некоторые функторы:

-- Указатели (предполагаю, что для населённых t с элементами всегда связаны адреса и размеры), Maybe/Option.
ptr : type -> type
ptr(t) = 1 + t -- или сразу + addr(t) * size(t) для указателей.

-- Связные списки.
list : type -> type
list(t) = 1 + t * list(t)

-- Целые числа.
nat : 1 -> type
nat() = 1 + nat()

-- Кортежи.
tuple0 : 1 -> type
tuple0() = 1

tuple1 : type -> type
tuple1(a) = a

tuple2 : type * type -> type
tuple2(a, b) = a * b

tuple3 : type * type * type -> type
tuple3(a, b, c) = a * b * c

...

-- Объединение всех кортежей.
1 + a + a * b + a * b * c + ...

-- Статические массивы.
arr : size -> (type -> type)
arr(n, t) = t * t * t + ... n-times

arr(0, t) = 1
arr(1, t) = t
arr(2, t) = t * t
arr(3, t) = t * t * t
...

-- Объединение всех статических массивов.
1 + t + t * t + t * t * t + ...

То есть этот первый 1 в функторах и их индексированных семействах играет роль нуля для целых чисел, NULL для указателей, Nothing/None для Maybe/Option, пустого списка, пустого кортежа (0-tuple), пустого массива и т.п. — везде он имеет вполне определённый смысл терминальной ветви данных без дополнительной информации или «degenerate case» как выразились выше по ссылке про D.

В D и Rust же как-то реализовали на уровне примитивных типов. То есть, что мешает или что делает эту вещь багом в ЯП?

я не знаю как в ди, но в C это не баг, а фича by design. Вот простой пример: тебе нужен массив из 5и эл-тов. И ты не знаешь, как её быстрее реализовать, по китайской методе, т.е.

int a0, a1, a2,a3, a4;

int a[5];

Элемент, то есть runtime значение, по определение имеет какой-то размер. Но тип != имеет элементы != имеет размер, он может существовать исключительно в compile-time и не иметь runtime представления (по крайней мере в виде каких-то данных в памяти).

в принципе верно, но не для сишных массивов.

Аналогично можно спросить зачем в C++ std::tuple<>, когда для него даже std::get нельзя сделать.

откуда мне знать, зачем тебе пустые картежи? Во всяком случае, ты можешь сделать tuple_size, и получить 0 в результате. В pure C это невозможно, ибо для этого надо взять array[0], который не существует (UB по стандарту).

Я выпишу некоторые функторы:

ну ОК. Это у тебя получился аналог сишного NULL. Фишка в том, что NULL можно засунуть в указатель, но уж никак не в массив. Ибо массив в C это разименованный указатель. Т.е. запись a[j] эквивалентна *(a+j), а разименовывать NULL (даже(тем более) сдвинутый на любое j) нельзя по стандарту.

Повторю ещё раз: если тебе это нужно, то либо меняй ЯП, либо используй указатель, который в C может (в т.ч.) никуда не указывать.

Так вот только в pure C компилятор может выбрать самый лучший вариант для конкретного CPU, т.к. ему точно известен размер ещё ДО компиляции

Да, в D и Rust тоже есть статические массивы, в первом они выглядят как

int[5] a;
int[0] e;

во втором как

let a: [int * 5];
let e: [int * 0];

со всеми вытекающими (размещение на стеке). Правда Rust непонятные портянки пишет в --emit-llvm, но это уже другой вопрос :)

Во всяком случае, ты можешь сделать tuple_size, и получить 0 в результате.

Так это же compile-time вычисление, нигде в памяти этот 0 не будет записан, аналогично array_size = sizeof(arr) / sizeof(elem_t) — будь zero-length массивы, дало бы тот же 0 и тоже в compile-time (оно так и есть в gcc / clang, просто это нестандартное расширение).

Это у тебя получился аналог сишного NULL

Скорее я говорю, что пустой массив по отношению к типу «массив» это как NULL по отношению к типу «указатель», 0 по отношению к типу целых чисел, пустой список по отношению с типу списков, tuple<> и т.п. — они изоморфны друг другу и изоморфны std::nullptr типа std::nullptr_t, нет смысла что-то выкидывать — в случае указателей будет диспетчеризация в рантайме (проверки на NULL), в случае статических массивов — во время компиляции с zero-overhead.

если тебе это нужно, то либо меняй ЯП, либо используй указатель, который в C может (в т.ч.) никуда не указывать.

В Си — согласен, так исторически сложилось. Кстати, в C++ есть ещё валидный int *p = new int[0]; так что этот p нельзя никак читать *(p + i) для любых i.

У нас x — размер элемента. Очевидно, что размер элемента из пустой коллекции не определён, так как в ней нет никаких элементов

Это не применимо к си-массивам, так как в семантике си размер элемента массива всегда определён - это размер того типа, массив элементов которого. Более того - не возможно создать массив, размер элементов которого не известен на этот момент.

Массив нулевой размерности - это синтаксический хак.

в C++ есть ещё валидный int *p = new int[0];

Это не фича языка, а требование совместимости с конкретными реализациями malloc.

это размер того типа, массив элементов которого

Практика работы с массивом структур на СИ (комментарий)

А в случае Array[Nothing] нужно (резонно) считать sizeof(Nothing) == 0, но в си нет Nothing.

И, да, система типов — синтаксический хак, чего уж там :)

в си нет Nothing.

Вот «T array[0];» - как раз оно и есть. ;)

nothing_t это такой тип, что nothing_t x; нельзя инициализировать и вообще у x нет «нормального» смыла и такая переменная не должна появляться и должна быть запрещена в compile-time, то есть это универсальный подтип — оно подтип и bool и int и вообще чего угодно, поэтому нельзя сказать что существуют какие-то нормальные элементы у типа nothing_t, так как тогда они должны принадлежать _всем_ типам (а вот у T array[0] есть один хороший элемент и его можно инициализировать пустым списком инициализации, как и создать переменную такого типа — не nothing_t), у него могут быть «ненормальные» элементы если у _всех_ других типов они есть (функции возвращающие int, bool и т.п. могут падать и зависать, например, — это ненормальные значения, в отличии от хороших false, true, 0, ...) и нужен он для того чтобы быть критерием такой «ненормальности». Например, если есть завершающаяся функция nothing_t foo(some_t), то some_t такой же ненормальный как и nothing_t (аналогично — отображение из множества A в пустое множество существует тогда и только тогда, когда A само пусто), или — для нормального array<nothing_t, 0> xs; xs[j] имеет тип nothing_t то есть ненормален и недопустим прямо в compile-time, или так — функция из нормальных типов в ненормальный вида nothing_t! loop(ok_t, ...) будет вменяемой только если она никогда не вернёт управление — так можно типизировать функции для которых нужно в compile-time запретить завершаемость и получение результата (где ! это оговорка про необходимость ввести effect types коиндукцию/корекурсию для таких вещей).

Теория типов: нормальный ~ населённый тип, ненормальный — ненаселённый.

Логика: нормальный тип ~ истинное утверждение, ненормальный — ложное, nothing_t — ⊥ (arbitrary contradiction), foo — отрицание (¬ φ = φ → ⊥).

В C++ есть велосипед для универсального супертипа в виде boost::any, в динамических языках в нём вообще вся соль, но универсальный подтип bottom явно никому не нужен :)

Но вот в скалу он уже попал — http://www.scala-lang.org/node/128.

alloc тоже не быстро. Причём malloc(100500×9000) куда как медленнее, чем 100500×malloc(9000). Т.е. непрерывный кусок памяти выделять _дольше_, чем множество маленьких кусков. И страницы тебе не помогут. Подумай - почему. Если лень думать - попробуй, и потом подумай (только не забудь заюзать память, а то виртуальной можно хоть 100500гигов навыделять, току-то?).

С чего это вдруг? malloc(100500×9000) - это _один_ сисколл

со всеми вытекающими (размещение на стеке).

такие и в новом C есть, ЕМНИП (или пока только в C++ ?), это другое, совсем не то, о чём я говорил. Синтаксис похожий, на деле - совсем другая конструкция.

Так это же compile-time вычисление, нигде в памяти этот 0 не будет записан

это ни на что не влияет. sizeof(a)/sizeof(a[0]) тоже нигде в памяти не пишется, и тем не менее, оно должно быть рассчитано. Но когда-бы ты не рассчитывал, это всё равно UB в pure C.

Скорее я говорю, что пустой массив по отношению к типу «массив» это как NULL по отношению к типу «указатель»

да, но в синтаксисе C такого хитрого «NULL» для массивов нет. И он не нужен, потому-же, почему не нужно разименовывать NULL. В этом нет смысла.

Кстати, в C++ есть ещё валидный int *p = new int[0];

ну и что? man 3 malloc: «If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().»

В C++ есть велосипед для универсального супертипа в виде boost::any

а в чистых C/C++ есть void* для этого. boost::any это его более безопасный костыль.

С чего это вдруг? malloc(100500×9000) - это _один_ сисколл

по твоему все вызовы выполняются одинаковое время что-ли? См. выше - malloc(100500×9000) должен найти нужный большой кусок, а если его нет - его сделать, например отправив в своп маленькие кусочки. (имелось ввиду выделение нормальной памяти, т.е. выделение+использование, что выше подчёркивалось).

Синтаксис похожий, на деле - совсем другая конструкция.

Ты про int a[5] из си? Я написал его же в ди и русте.

sizeof(a)/sizeof(a[0])

А если делить на sizeof(elem_t) для elem_t a[...] — UB уже не будет, так?

он не нужен, потому-же, почему не нужно разименовывать NULL

Не могу уследить за твоей мыслью :) Разыменовывать NULL не надо, да, но сам NULL нужен. Пустой массив имеет право на существование, но доставать из него элементы не нужно, так же как не нужно доставать элементы за границами любого массива вообще.

Подожди-ка! С чего это вдруг кусок должен быть сплошным? malloc же просто выделяет кучу страниц памяти, необходимую для размещения нужного количества данных, ведро хранит адреса этих страниц, а процесс — да, думает, что кусок сплошной.

Ты про int a[5] из си? Я написал его же в ди и русте.

ну вот это разные вещи, на самом деле. В си это имеет совсем иной смысл.

А если делить на sizeof(elem_t) для elem_t a[...] — UB уже не будет, так?

так. Как я понял последний стандарт, sizeof(a) будет равен 4, если a - это массив 4х символьных int размера 0. Как и sizeof(int). В итоге, всё выражение будет равно 1, что значит, что в пустом массиве имеется ровно один эл-т. Противоречие, как и в многочисленных софизмах о делении на ноль.

Да, это проблема C.

Не могу уследить за твоей мыслью :) Разыменовывать NULL не надо, да, но сам NULL нужен. Пустой массив имеет право на существование, но доставать из него элементы не нужно, так же как не нужно доставать элементы за границами любого массива вообще.

ты не привык работать с НЁХ. Но всё просто - указатель в C может указывать на конкретную память, а может никуда не указывать (==NULL). Если указатель куда-то указывает, И если это «куда-то» определено, то можно разименовать указатель, т.е. выяснить «куда». Если указатель никуда не указывает(NULL), то и выяснить куда он указывает невозможно. Если ты таки это сделал, то получаешь UB, или в русском переводе - НЁХ. Массив - это уже такой «разименованный указатель», т.е. в сишном синтаксисе массив эквивалентен указателю, но _всегда_ на что-то указывает, причём на что-то конкретное, и мало того - константное, и известное во время компиляции. Потому массив всегда можно разименовать, кроме конечно случая выходы за пределы массива. Шаг влево, шак вправо карается НЁХ. Опасайся НЁХ.

Подожди-ка! С чего это вдруг кусок должен быть сплошным? malloc же просто выделяет кучу страниц памяти, необходимую для размещения нужного количества данных, ведро хранит адреса этих страниц, а процесс — да, думает, что кусок сплошной.

кусок и должен быть сплошным в адресном пространстве процесса. Проблема в том, что в этом пространстве может и не быть такого куска, а если даже такой кусок есть, то не факт, что ты его быстро и просто найдёшь. В принципе, страничная организация памяти позволяет ядру тупо выделить _новый_ кусок, не взирая на дыры, проблема только в том, что если ядро так будет делать, то память практически сразу кончится, и у тебя останется 100500 дыр и неиспользуемых фрагментов.

В си это имеет совсем иной смысл.

Чем отличается?

В итоге, всё выражение будет равно 1, что значит, что в пустом массиве имеется ровно один эл-т.

    int a[0]; // вот это стандарт(ы) просто называют UB, AFAIK
    int *b = a;
    printf("%ld %ld\n", sizeof(a), sizeof(b)); // вот тут gcc и clang пишут 0 и 8, 0 -- сильно implementation defined.

то есть, по логике вещей, sizeof(a) == 0 и в пустом массиве sizeof(a) / sizeof(int) == ноль элементов.

Потому массив всегда можно разименовать

Ну да, пустых массивов нет — можно разыменовать (a[0] == *(a + 0)), будут пустые массивы — именно их «нельзя» будет разыменовывать, аналогично NULL.

Чем отличается?

тем, что int a[5] в си - непрерывный кусок памяти размером в 20 байт. А вот что это в твоём D - зависит от того, как у автора D пятка зачесалась.

то есть, по логике вещей, sizeof(a) == 0 и в пустом массиве sizeof(a) / sizeof(int) == ноль элементов.

ага. Я же говорю - опасайся НЁХ - если ты её даже разок Ё, она от этого не станет послушной, белой и пушистой. Завтра она поведёт себя совсем иначе. sizeof(a[0]) у меня тоже получилось вроде как 4, и это несмотря на то, что никакого такого 0го элемента нет. Элемента нет, а размер мы его посчитали. Сегодня. Что будет завтра - я не знаю. Знаю, что надеяться на такое поведение могут только быдлокодеры.

Ну да, пустых массивов нет — можно разыменовать

НЕЛЬЗЯ. Точно также _можно_ _записать_, «0/0». Ну записал. Мир не сдвинулся с места. Так же я и в коде могу писать, и он(быдлокод) возможно будет работать. Но вот как он будет работать - я не знаю. Не факт, что вообще будет. В том-то и опасность НЁХ, что её можно записать, и она даже работает.

Проблема в том, что в этом пространстве может и не быть такого куска

И при чём тут своп?

А вот что это в твоём D - зависит от того, как у автора D пятка зачесалась

Не зависит, статические массивы там такие же как и в си.

Сегодня

Если используешь компилятор в котором это известное и документированное _расширение_, то и завтра.

А то что в стандартном си это UB мы вроде как договорились, я хотел донести что это UB именно в си != сами по себе zero-length arrays бессмысленны (даже в си + расширение компилятора или в си-like языке).

пустых массивов нет — можно разыменовать

НЕЛЬЗЯ

int x[N], N > 0, x[0] == *x — проблемы?