Векторная структура в C
Я хочу создать ArrayList или Vector на C. Возможно, я смогу узнать, на правильном ли я пути или совсем не в основе
Итак, если у меня есть структура ArrayList, которая содержит массив, изначально установленный на 10, и счетчик, чтобы отслеживать, сколько элементов было заполнено в arrayylist, например
typedef struct ArrayList
{
int counter;
int arr[10];
}
Можно ли заменить массив arr другим массивом, который в два раза превышает размер исходного массива? Если да, то как мне это сделать?
У меня есть следующий фрагмент кода в функции add ()
if ( arrList->counter == (sizeof(arrList->arr)/sizeof(int)) )
{
int tempArray[((arrList->counter + 1) * 2)];
for (int i = 0; i < arrList->counter; i++)
{
tempArray[i] = arrList->arr[i];
}
strcpy( arrList->arr, tempArray );
}
На правильном ли я пути или есть лучший способ создать растущий массив?
Или рассмотрите возможность использования гибкого элемента массива: typedef struct ArrayList { size_t capacity; size_t counter; int arr[]; } ArrayList;, который позволяет вам вести учет того, сколько места выделено в capacity, сколько используется в counter (как и раньше), и вы можете ссылаться на vector->arr[i], как и раньше. Это почти эквивалентно использованию int *arr; в структуре. У обоих есть свои плюсы и минусы. (Вы можете использовать realloc() для расширения или сжатия FAM; требуется некоторая осторожность.)
strcpy некорректно работает с массивами типа int. Вместо этого используйте memcpy.
@JonathanLeffler Вы не можете вырастить гибкий член массива, вам нужно перераспределить саму структуру.
@Barmar: извиняюсь за небрежность - я имел в виду именно это (отчасти говоря "некоторая осторожность"), но то, что я написал, слишком легко может быть неправильно понято.
У обоих потенциальных представлений векторных элементов действительно есть как плюсы, так и минусы, но я думаю, что неопытному программисту на C будет сложно оценить те из FAM, как, похоже, OP. Я определенно рекомендую не использовать FAM для тех, кто не очень хорошо понимает все компромиссы, связанные с этим выбором.
Ответы 1
Ваш подход не так хорош, поскольку он включает в себя копирование структуры во временный примитивный массив.
Очень хорошее решение возникшего у вас вопроса - это так называемый гибкий массив. Google для получения дополнительной информации. По сути это выглядит так.
struct my_fam_array_t {
int arr_size;
int arr[];
};
Чтобы использовать его, вы всегда объявляете его как указатель следующим образом
struct my_fam_array_t *arr5;
И затем вы инициализируете его следующим образом:
arr5 = malloc(sizeof(struct my_fam_array_t) + fam_size));
Где fam_size должен быть размером, который вам нужен для массива.
Еще две вещи, не забудьте установить размер массива в структуре, а также проверить статус выделения памяти и обработать любые ошибки.
Не забудьте освободить его после использования.
Теперь вы можете использовать массив как обычно, например
arr5->arr[3] = some_value;
Теперь вы можете создать функцию для изменения размера массива. Я не собираюсь писать это, но сделаю следующее:
malloc новая структура с новым размером
Скопируйте старый массив в новую структуру
Не забудьте освободить старый массив
Это может быть новым для вас, учитывая, что вы новичок, однако гибкие массивы - это инструмент, который вам нужен.
Кстати, вы также можете использовать realloc, прочтите об этом, это может быть полезно, но будьте очень осторожны, чтобы правильно обрабатывать сбой нехватки памяти. Google о перераспределении и стандартах SEI CERT C
Редактировать:
Убедитесь, что вы используете C99 или выше. Напротив, вам придется использовать структуру с размером массива 1, и вы должны вычесть 1 из размера malloc. Вы можете использовать массив с размером 0, если ваш компилятор поддерживает это расширение.
int arr[0] не действителен в C; это старый хак struct, используемый для достижения гибкий элемент массива. Формально FAM были добавлены в C99.
@David Bowling: Это правда, однако я считаю, что автор уже использует C99 или выше. Если это не так, массив можно изменить на arr [1]. Это будет совместимо со всеми версиями C. Также не забудьте вычесть 1 из размера malloc, чтобы учесть 1 элемент.
Нет. int arr[0] не является допустимым для C даже в C99. Способ объявить FAM в C99 и выше - с int arr[]. Старый хак structint arr[0] использовался до C99 для достижения того же самого, но он не поддерживался стандартом и полагался на детали реализации.
@DavidBowling, я плохой, ты снова прав. Массив размера 0 является расширением, а не частью стандарта. C99 FAM не должен иметь указанного размера, чтобы стать неполным типом.
Предложения: вы можете заменить LENGTH на что-то вроде fam_sz, чтобы прояснить, что это размер, а не длина. Рассмотрим arr5 = malloc(sizeof *arr5 + fam_sz);: нет необходимости приводить результат malloc() в C, а использование выражения вместо явного типа с sizeof менее подвержено ошибкам и проще в обслуживании. Это более идиоматический способ использования malloc() в C. Кроме того, не забывайте, что перед использованием arr5 вам необходимо проверить успешное выделение.
@DavidBowling Если честно, я считаю, что в отношении размера комментария верно обратное. Я пошел на все, запретив моей команде использовать выражение sizeof, а лучше использовать тип. У вас могут возникнуть проблемы, указав выражение, а что если оно выйдет за пределы? Что, если по ошибке будет передан указатель? Возможно, мне что-то не хватает, но, по крайней мере, стандарты SEI CERT AC и японские стандарты кодирования C со мной согласны.
он не может переполняться в выражении sizeof, поскольку sizeof (обычно) не оценивает свой операнд (используется только тип выражения). В остальной части оценки выражения может произойти переполнение, но это не имеет ничего общего с sizeof *arr5 и sizeof some_type_I_have_to_get_right. Не знаю, что вы имеете в виду под «указатель передан». Где CERT с вами согласен (мне была бы интересна ссылка)?
@DavidBowling Вот стандартная ссылка SEI Cert: wiki.sei.cmu.edu/confluence/display/c/…. Там перейдите в раздел «Совместимое решение (ручное кодирование)» и прочтите до «Исключений» (или, по крайней мере, до первой половины этого выбора). Из японских стандартов кодирования см. Правило R3.6.3 (здесь PDF ipa.go.jp/files/000040508.pdf). См. Следующий комментарий
@DavidBowling По сути, мои замечания о том, что вы можете по ошибке использовать sizeof (some_type *) вместо sizeof (some_type). Кроме того, sizeof (some_big_value + some_big_value) может переполняться, что, в свою очередь, может отображать неправильный тип из-за изменения ранга преобразования. Я понимаю преимущества использования sizeof (* arr5), поскольку вам не нужно повторно указывать тип при изменении arr5, однако это опасно, и в этом случае надежность предшествует ремонтопригодности.
sizeof(some_big_value + some_big_value) может переполнить никогда: sizeof не оценивает свой операнд, за исключением случая, когда операнд имеет тип VLA. Пример sizeof(some_type *) использует тип, а не выражение, и это именно то, чего избегает идиоматический подход. Вместо этого int *arr = malloc(sizeof *arr); использует тип только выражения *arr, то есть int. Более поздние изменения в long *arr = malloc(sizeof *arr); требуют изменения типа только в одном месте: проще в обслуживании и менее подвержено ошибкам при запуске.
Мне и многим другим это кажется более надежным и простым в обслуживании, но спасибо за ссылки; Я их проверю. Я отмечаю, что ваша первая ссылка, похоже, связана с приведением результата malloc(), а не с использованием выражения, как я описал. Есть законные разногласия по поводу этого кастинга среди программистов. Но это всего лишь рекомендация CERT, а не правило, и притом маловажное.
@DavidBowling Я подумал, что добавлю пример того, что я имел в виду под sizeof overflow: #include <stdio.h> int main (void) {unsigned char a = 200; беззнаковый символ b = 200; printf ("a + b ->% u \ n", sizeof (a + b)); printf ("a ->% u \ n", sizeof (a)); printf ("b ->% u \ n", sizeof (b)); printf ("символ без знака ->% u \ n", sizeof (символ без знака)); возврат 0; } sizeof (a + b) больше 1, что (возможно) не является намерением. Такие переполнения вызывают проблемы, и их довольно сложно обнаружить. В первую очередь из-за этого мне не рекомендуется использовать sizeof (выражение).
В этом коде нет переполнения (у него есть UB, поскольку значения size_t должны быть напечатаны с помощью %zu, а не %u). sizeof(a+b) правильно сообщает размер int в целевой системе, который является типом выражения a + b из-за правил целочисленного продвижения. Конечно, делать sizeof(a+b) в таком случае - плохая идея, да и зачем вам это нужно? Но это никак не связано с примером sizeof *arr. Целочисленное продвижение может укусить вас в самых разных обстоятельствах, но это не причина избегать чистого кода.
@DavidBowling Я согласен с тем, чтобы у вас был чистый код (и использование sizeof (* arr) довольно аккуратно). Но с точки зрения QA (по крайней мере, из моего опыта написания стандартов) он избегает обстоятельств целочисленного продвижения. Опять же, исходя из опыта обзора кодовых баз, есть разработчики, к сожалению, которые инкапсулируют большие выражения с побочными эффектами в sizeof, что вызывает внезапное перераспределение памяти, что в дальнейшем приводит к сбою (по крайней мере, встроенных) устройств. Кстати, некоторые из них говорят, что сделали это для того, чтобы сделать чистый код (благое намерение, однако, безуспешно).
Замените массив указателем и динамически выделяйте / увеличивайте / удаляйте массив с помощью
malloc,reallocиfree.