Как добавить элемент в динамический массив c
Перейти к содержимому

Как добавить элемент в динамический массив c

  • автор:

Dynamic Arrays in C Language

This post is about implementing dynamically growing arrays in C language. In other languages, this is implemented as std::vector in C++, ArrayList in Java, and list in Python and so on. Dynamic arrays also sometimes refer to dynamically allocated arrays which is not this post is about. Implementations more or less go from the simplest to the most complicated, the idea being you should stop whenever you find a good enough solution for your case.

There is also a complementary post «Generic Programming in C Language» which discusses two common techniques to do generic programming. These techniques can be combined with dynamic array and fat array implementations given here to overcome the single type limitation. Refer to the other post for the generic implementations along with some explanation.

Plain Arrays

Coming from a more advanced language, one might be tempted to look for a dynamic array right away. This may sound silly at first but good old plain arrays are the easiest choice for the job in many cases. This is possible when you can come up with a number for the maximum number of elements in the array.

A common example is reading a line of text from a well formed standard input or file. For most applications, you can assume lines have at most a thousand characters or some other fixed value so you can allocate that much beforehand:

In this example, standard fgets function reads until a \n occurs or the buffer is filled. Therefore, it is always safe against buffer overflows, however splitting a line is possible if a line is too long. You can optionally check the existence of a trailing \n in the end of line to see if a line is split or not. Also note that, above example allocates on the stack but you can also allocate on the heap if you need.

Character arrays can be null terminated but this is not always possible for other types of arrays. For example, it is not possible to distinguish null termination and the number zero in integer arrays. For this reason, you might need to store an additional length parameter in the same scope, whether it is a struct, function, or a global scope. Finally, if you need a dynamically growing array, you can store a capacity parameter in addition to length and reallocate space when necessary:

In this example, a new number is read into an integer named num using a get() function until the values of read numbers exceed the limit value. Since it may not be possible to determine the number of elements beforehand, we increase the array capacity dynamically. The rest of the code is just an arbitrary use case to demonstrate various operations on the array.

Plain arrays can be used dynamically relatively easily but it can sometimes be error prone. You need to pass an extra length parameter to functions and check the capacity when adding new elements. Also you need to hold these parameters in the current scope which can make things complicated.

Dynamic Arrays

In order to create an abstraction, one might decide to implement a specific data structure to be used as dynamic arrays. For this purpose, we pack the buffer, length, and capacity parameters within a struct:

We also provide allocation and freeing functions with the new structure. In this example, arrnew creates an array with a default capacity, arrnewcap creates an array with a specified capacity, and arrdelete frees the array:

Similarly adding and removing elements is handled by arrappend and arrremove respectively. Reserving extra space or shrinking existing one is accomplished using arrresize :

Array indexing is done by directly accessing the buf field of the structure. Separate indexing functions can be provided but they don’t provide much advantage over this. Similarly len and cap fields are considered public and can be accessed directly. The previous scenario can now be accomplished as follows:

This code is pretty straightforward and idiomatic for C programmers, but it has a major problem. Code is not generic and you can only implement this for a single type since there is no function overloading in C. Therefore, this is only acceptable if you only need it for a single type in a small codebase.

Void Pointer Arrays

Void pointers can be used as an alternative when more than one type is needed. To define a void pointer array, we simply change the type in our previous code to a void pointer:

Void pointer is a generic pointer type that can point to any type. We can use this implementation for any type we need. Our previous scenario now looks almost the same as before:

In this code, num is an int but it is implicitly casted to void * when we pass it to arrappend . We could also make this more explicit by putting (void *) before num . Similarly arr->buf[i] is a void * but it is casted to int when we pass it to process_int . We change the previous name process to process_int to make it more explicit what type it accepts, otherwise it is the same code.

Now this code should compile and most likely run as before. However, depending on the warning level you may see a warning as such:

This is the implicit cast we talked about before. When we try to make the cast explicit, this time we get a warning as such:

This warning is more informative than the previous one. It basically states that int and void * have different sizes. We can check the sizes of types with the following code:

Depending on your machine, you may or may not get the following output:

This means we are actually trying to store 4 byte integers in 8 byte fields. Memory layout of an array having three elements with values 8, 13, and 21 should look like this:

This is not an efficient way to store integers but it works without a problem. However, this is not true in general. If we were to store a type that is more than 8 bytes in size, then the elements would overwrite each other. This is the case for most structures consisting of multiple members.

Therefore, the right way to use void pointer arrays is by using them with pointer types instead of value types. Void pointers are guaranteed to have a size that can hold pointers to any other data type. Our code looks like this when using integer pointers:

In the above code, we allocate new integers on the heap. If we use the memory address of the num variable, all added elements would point to the same element on the stack and they would all change when we read a new element.

We have already checked the size of integer pointers before. Memory layout of an array with integer pointers having values 8, 13, and 21 now looks like this:

This works without a problem but since values are spread around the memory, performance may suffer. This may not be what you want depending on your needs. Also, since we are allocating on the heap, we also need to free memory when we remove an element.

Note that for some types this implementation is simple to use. Consider the use case with strings as below:

Strings in this code are allocated statically so we don’t need to allocate space or free them after the use.

Fat Pointer Arrays

A frequent complaint about C language is that arrays do not store their lenghts. Fat pointers have been proposed to solve this problem by holding more than just the address of elements in a pointer. This was considered as an addition to the language specification. However, it turns out that you can also simply offset pointers to simulate fat pointers without a language change.

We can use fat pointers to simplify our dynamic array implementation. The idea behind is to allocate a little extra space in the beginning of the array when it is created. This extra space is used to hold length and capacity parameters of the array. Beginning address of elements is returned to the users instead of the actual beginning of allocated space. Thus, users are able to use the fat pointer as a regular pointer to access its elements.

Memory layout of an array having three elements with values 8, 13, and 21 with a capacity of 4 should look like this:

In above example, length and capacity parameters are stored as 4 byte integers. Array is also an integer array with 4 byte elements, but these two do not actually need to be the same. We define our fat pointer array as a simple pointer for an integer type using a macro:

We implement allocation and freeing functions to simplify the management of fat pointer arrays. Similar to previous implementations, arrnew and arrnewcap allocates an array with a little extra space and returns the offset pointer as described before. For freeing, we implement arrdelete function which calculates the actual allocation address of the array and frees it properly:

We also need to provide functions for operations that may change the array. Appending an element is implemented as arrappend which returns a possibly new address. Adjusting the capacity of the array is implemented as arrresize which reallocates memory. Lastly, removing an element is implemented as arrremove which reduces the length of the array and returns the removed element:

Unlike previous implementations, we also provide arrlen and arrcap functions to return the length and capacity of the array:

We can now use fat pointers in our previous scenario as such:

Note that we assign the result of arrappend call to the current pointer. We choose this design to make it more explicit in the code that the value of the pointer may have changed after appending an element. However, it is also possible to abstract this detail by using an extra macro depending on your taste.

Поштучное добавление элементов в динамический массив

Как постепенно выделять по одной ячейке памяти для массива?

Arhadthedev's user avatar

Вы имеете ввиду обычные динамические массивы в C? Если да, то примерно так:

Но стоит отметить, что этот способ очень неэффективный, т.к. при каждой реалокации происходит копирование всего массива на новое место. Поэтому для создания массива размера N таким способом потребуется порядка N^2 операций, т.е. стоимость добавления одного элемента составит порядка N. Намного эффективнее по мере надобности (в моменты, когда свобоного места в массиве не осталось) увеличивать массив на величину a * N, где a — некоторая константа, а N — текущий размер массива. В таком случае средняя стоимость добавления одного элемента будет константной. Именно такая стратегия реализована в стандартном классе vector. Поэтому я рекомендую воспользоваться им:

Как вставить элемент в динамический массив?

Как в динамический массив вставить элемент?
Задание: Дан массив целых чисел размера n. Вставить в массив заданное число перед последним.

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

Как добавить элемент в динамический массив?
Всем привет. У меня такая проблема: Написал класс avto, в нем данные об автомобиле.Моя задача.

Массив: Не знаю, как упорядоченно вставить элемент в массив.
Есть массив a= <5,4,2,1>и массив b Нужно вставить число r=3 в b, и все элементы вектора а, чтобы.

Динамический массив

Массив — это набор однотипных переменных, доступ к которым осуществляется по индексу.

Динамический или расширяющийся массив — это массив, который может изменять свой размер в зависимости от количества элементов в нём.

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

  1. Добавить в конец массива элемент $x$.
  2. Удалить последний элемент массива.
  3. Узнать размер массива.

При этом все операции должны выполняться за $O(1)$ — необязательно в худшем случае, но амортизировано.

#Реализация

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

Если обычные массивы — это просто последовательные области в памяти, то динамический массив обычно реализуют как структуру, которая содержит:

  • указатель на массив $t$,
  • размер этого массива,
  • текущее число элементов (меньшее размера массива $t$).

При этом внутренний массив $t$ расширяют (деаллоцируют и заново аллоцируют с большим размером), когда он становится полностью заполненным, и требуется добавить ещё один элемент. Также опционально можно сжимать массив, когда доля заполненных элементов станет малой — это позволит вернуть не использующуюся память.

#Время работы

В худшем случае операции добавления и удаления работают за линейное время, потому что нам нужно пересоздавать весь массив размера $O(n)$. Однако амортизировано все операции будут работать за $O(1)$. Применим метод предоплаты чтобы это показать.

Пусть единицей стоимости операции является одна монетка. Тогда при каждой операции add , при которой нам не требуется копирование, мы будем платить три монетки: одна из них пойдёт на стоимость самой этой операции, а две будут в резерве — если мы добавили $k$-ый элемент, мы будем класть по одной монетке к элементам с номерами $k$ и $(k−\frac<2>)$.

К тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которой мы и сможем оплатить его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add — 3, и среднее время её работы — $O(1)$.

При каждой обычной операции del будем платить две монетки. Одну из них потратим на непосредственно удаление последнего ($k$-того) элемента, другую положим рядом с элементом, стоящим на позиции $(k \bmod \frac<4>)$. Тогда даже в худшем случае — если мы только что расширились, а потом удалили $\frac<4>$ элементов с конца — у каждого элемента из первых $\frac<4>$ будет по монете, которые мы и потратим на их перемещение.

#В языках программирования

#std::vector

В С++ динамический массив реализован в структуре vector из стандартной библиотеки.

При попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера — в 2 раза при компиляции через GCC и в 1.5 при компиляции через MSVC. При удалении элементов уменьшение размера массива не происходит.

Получить capacity у vector можно с помощью одноимённой функции:

При инициализации vector по-умолчанию начальный размер (который capacity ) равен 0, однако многие использующие его внутри структуры часто резервируют какой-то начальный размер — например, 16 или 32 элементов — чтобы сэкономить время из предположения, что там будет храниться не один элемент.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *