Уловка, чтобы избежать необходимости инициализировать массив

В большинстве компиляторов/стандартных библиотек, о которых я знаю, большие calloc запросы (и malloc в этом отношении) реализуются с точки зрения логики запросов объемной памяти ОС. В Linux это означает копирование при записи mmap нулевой страницы, а в Windows это означает VirtualAlloc. В обоих случаях ОС дает вам уже нулевую память, и calloc распознает это; он явно обнуляет память только в том случае, если он делал небольшую calloc из небольшой кучи распределения. Так что, пока вы не напишете на любую заданную страницу в распределении, это ноль «бесплатно». Не нужно явно лениться; распределитель ленив для вас.

Для небольших выделений действительно необходимо memset очистить память, но тогда довольно дешево memset memset несколько тысяч байт (или десятков тысяч) байтов. Для действительно больших распределений, где обнуление было бы дорогостоящим, вы получаете предоставляемую ОС память, которая обнуляется бесплатно (отдельно от остальной части кучи); например для dlmalloc в типичной конфигурации выделения за пределами 256 КБ всегда будут заново mmap-ed и munmap-ed, что означает, что вы получаете свежесопоставленные сопоставления копирования при записи нулевой страницы (стоимость их обнуления откладывается до тех пор, пока вы не выполнить запись где-нибудь на странице и оплатить, получили ли вы 256 КБ через malloc или calloc).

Если вам нужны лучшие гарантии обнуления или бесплатное обнуление при меньших выделениях (хотя это более расточительно, чем ближе к одной странице вы получаете), вы можете просто явно сделать то, что malloc/calloc делают неявно, и использовать предоставленную ОС обнуленную память. , например заменять:

sometype *x = calloc(num, sizeof(*x)); // Or the similar malloc(num * sizeof(*x));
if (!x) { ... do error handling stuff ... }
...
free(x);

либо с:

sometype *x = mmap(NULL, num * sizeof(*x), PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (x == MAP_FAILED) {  ... do error handling stuff ... }
...
munmap(x, num * sizeof(*x));

или в Windows:

sometype *x = VirtualAlloc(NULL, num * sizeof(*x),  MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
if (!x) { ... do error handling stuff ... }
...
VirtualFree(x, 0, MEM_RELEASE); // VirtualFree with MEM_RELEASE only takes size of 0

Это дает вам ту же ленивую инициализацию (хотя в Windows это может означать, что страницы просто были лениво обнулены в фоновом режиме между запросами, поэтому они будут «настоящими» нулями, когда вы их получите, по сравнению с *NIX, где они будут обнулены с нулевой страницы, поэтому они будут обнулены в прямом эфире, когда вы им напишете).

Это можно сделать, хотя это зависит от неопределенного поведения. Он называется ленивым массивом.

Хитрость заключается в использовании таблицы обратного поиска. Каждый раз, когда вы сохраняете значение, вы сохраняете его индекс в ленивом массиве:

void store(int value)
{
   if (is_stored(value)) return;
   lazy_array[value] = next_index;
   table[next_index] = value;
   ++next_index;
}

int is_stored(int value)
{
  if (lazy_array[value]<0) return 0;
  if (lazy_array[value]>=next_index) return 0;
  if (table[lazy_array[value]]!=value) return 0;
  return 1;
}

Идея состоит в том, что если значение не было сохранено в ленивом массиве, то lazy_array[value] будет мусором. Его значение будет либо недопустимым индексом, либо допустимым индексом в вашей таблице обратного поиска. Если это недопустимый индекс, то вы сразу узнаете, что там ничего не сохранено. Если это действительный индекс, вы проверяете свою таблицу. Если у вас есть совпадение, значение было сохранено, в противном случае — нет.

Недостатком является то, что чтение из неинициализированной памяти является неопределенным поведением. Судя по моему опыту, это, вероятно, сработает, но гарантий нет.

Есть много возможных методов. Все зависит от вашей задачи. Например, вы можете запомнить максимальное количество инициализированных элементов max вашего массива. т.е. если ваш алгоритм может гарантировать, что все элементы от 0 до max ara инициализированы, вы можете использовать простую проверку if (0 <= i && i <= max) или что-то в этом роде.

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

Итак, добавьте больше деталей о своей задаче. Я ожидаю, что мы найдем лучшее решение для этого.