How to Resize an Array in C/C++? Is there a best way?
HTML-код
- Опубликовано: 14 ноя 2022
- Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]
![CENTRAL CEE - GEN Z LUV [VERTICAL VIDEO]](http://i.ytimg.com/vi/VIbidJm9q34/mqdefault.jpg)
A few comments I want to put up top. First, yes, there's a bug in the code (forgot an asterisk before "array" on line 9). Sorry about that. Second, many of you have predictably come at me for not using vectors-some even claimed that arrays are not "legal" in C++ (funny, but false). This is a video about arrays. Vectors are objects (and lovely objects at that), and they're perfectly fine to use for this purpose. But, I was talking about arrays and allocators. Also, if anyone is curious about my feelings about C++ as a language and C++ as a religion, I talk about it in a previous video (ruclips.net/video/Kq8m980JEeg/видео.html).
Just to add to the errata, when passing arguments to functions, the order of evaluation is implementation defined and should not be relied upon, and since realloc does not free the memory you are trying to resize if it can't allocate enough space, writing over the original pointer will cause a memory leak on an allocation failure.
@@anon_y_mousse u're right
You mentioned std::vector at the very end, even if just in passing, so I think you're covered. Still the best way to resize an array in C++ is (often) by using std::vector, so the title remains semantically confusing.
Hi sir good information about the array
I came across this attribute in my code
Can you pls explain why and when we use this in coding " __attribute__((aligned(4))) in c "
Thank you sir..
@@ramakrishna4092 It tells the compiler to align the memory on 4 byte boundaries. It makes reads and writes faster at the possible expense of a few extra bytes per element in a struct, array, or via stack allocations in a function.
In the printf statement, I would not recommend the use of using the value of myarray as one argument, and changing the value by a function in a different argument. the C standard (and at least the older C++ standards) do not specify the order of evaluation for function arguments, so one cannot be sure that the first use will be the old value and the second use will be the new value. Hence, when trying on a different compiler, the results may be different.
A general rule is to avoid chaning the value of a variable and using the value of same variable in a different place within the same statement
That's one of the failings of the standard IMO. But definitely he should be aware of it all the same.
Hi, Jacob. Congratulations for the 100k subscribers! Keep up doing the great work. You're awesome
I have been waiting for a video like this for so long! Thank you!
C++ does not have a garbage collector, but you can get pauses, similar to garbage collection pauses, if you push_back lots of data to vectors. When a vector exceeds its capacity, it multiplies its capacity by 2 (gcc and clang) or 1.5 (msvc) and moves everything to the new location. Some items, such as mutexes, cannot be moved, so cannot be put in vectors. For these, use maps or deques. Deques do not have the overhead of maps, but their indices have to be contiguous, like vectors.
If you know how much data the vector will need to contain ahead of time you can also just call the .reserve() member function on your vector right after it is declared which will skip the amortized constant time reallocations altogether during the push_back() loop by doing them up front just once
@@metal571If you know the total size ahead of time isn't it better to just use an std::array?
(Genuine question. I had never heard of reserve(). And I'm curious about it's use cases)
@@sebastiangudino9377 yes you can do that, as long as the size isn't so large that you would run out of stack space. Also std::array conveniently can be constexpr. It's really just a very thin wrapper around a C array.
I haven't seen reserve used that much except where performance is extremely critical and you're using a very large vector size, so you want to make just one heap allocation if possible.
@@metal571 I see now, that makes sense! You get the benefits of std vector without the performance hurdles of moving your data arround
That's not true, CPython uses C Language structs to store all variables in text form so everything is garbage collected automatically. To do this in C or C++ simply use only struct array variables to program all your applications.
Not only are they auto garbage collected but they are also pre sized according to your programs requirements. They can also replace all globals or static variables to.
Nothing wrong with adding several structs for these purposes.
When using "realloc()", do *not* call it like so: "ptr = realloc(ptr, newSize)".
"realloc()" can fail, in which case it will return NULL and *not* free the original pointer, it will become a memory leak. When "new" fails, by default it throws an exception.
Instead do the following:
int *newPtr = realloc(ptr, newSize);
if (newPtr == NULL) {
/* report failed reallocation */
}
else {
ptr = newPtr;
}
Also, it's a bad idea to do "sizeof(int)" because the type may change, instead do "sizeof (*ptr)", which will use the type the pointer looks at, meaning it will work when the type changes.
In C++, the modern and standard way is to *never* use "new" and "delete". For a single object, use "std::unique_ptr" with "std::make_unique()", for a run-time array use "std::vector".
Hi, can I connect with you on LinkedIn?
@@yashwantht5407 no.
@@monochromeart7311 okay 👍
malloc() can fail too, so if for some reason, at our own risk, we decided not to check malloc(), then there is no point in checking realloc() for NULL too. In both cases, on failure there will probably be a segmentation fault.
@@simonmaracine4721 I think the point with realloc is that you already have data which is now in limbo, while on malloc supposedly the pointer you're assigning the output to is not "holding" anything.
So it's not quite the same, you can "for a while" have leaked memory without segfaulting (no idea how likely that is to actually be a problem)
At minute 6:22 you're incorrectly assuming an exact evaluation order of the arguments. But that order is not specified in the C++ specification, so it's implementation dependent, which means what you're doing is bad.
For C++, in general it's better to use std::copy rather than mempy, because the former calls the copy constructors for each of the elements, though in your case it doesn't matter because you are using ints.
Also in general, new has more overhead because it calls the constructors of each of the elements right at the outset.
std::copy and memcpy are WILDLY different things. And replacing one with the other will undoubtedly result in a segfault or undefined behavior in most cases.
std::copy iterates over 2 iterators. Copying the elements of one to the other calling the copy constructor for each. Memcpy takes a 2 pointers and moves the first N Bytes of one pointer to another. It also completely bypass any type checking in C++. Meaning that for example copying a float to an int32_t is perfectly valid (And the "correct" way to manipulate the bytes of a float in C++ prior to bit_cast. Using reinterpret_cast for this was UB)
Great! Thx Jacob!
very nice video!
Dr. Sorber is completely right with this example. For int (as well as pretty much every type which is also valid in C) the standard says that objects of these types and arrays of such type have a "implicit-lifetime" which can begin when functions like malloc and realloc are called, and as he notes a std::vector or std::unique_ptr probably implements what you actually want most times you would reach for malloc. I use malloc and realloc for these uses frequently because they more concisely express my intent and is as Dr. Sorber wrote legal C++.
However, where I see students get confused coming from C into C++ is where they try to use malloc and realloc with things that don't have implicit lifetime (like an array of std::vector or a std::string). In this case the memory of the vector or string needs to be initialized by its constructor so for example the pointers inside it point to valid memory on the heap which is what new/delete does.
The power of C++ is that it gives you powerful tools to concisely express your intent with powerful and performing abstractions. IMHO learning these is worth the effort.
You're able to use C++ approach and pass a reference to int* instead of int** in resize function.
P.S. from my perspective C and C++ are different languages and it's not good practice to mix them (of course it's possible but it's harder to read that code).
Its all about where you decide to mix and for what reason, never arbitrarily mix only do it when you are sure you will get a superior outcome. Sometimes that requires testing but its important to go through that when designing software.
@@Ryan-xq3kl where to mix is discussiable - if you think you mixes in appropriate way, your colleague may not think so (and that junior guy who you take recently on the project doesn't aware of C at all) - that's why the code should be readable for all (especially unskilled colleagues). C++ is full of pitfalls without using it in mix with C.
*If* an individual knows how to read the order in C (from right to left), it will be quite clear.
int *p = NULL;
int *(&ref) = p;
You read the variable declaration from right-to-left like so:
"ref is reference to pointer to int"
Imo it's a good idea, but an even better idea is to use "std::vector".
@@monochromeart7311 this is an exercise for students and a broad audience of beginners, nothing more.
@@MECHANISMUS using references when teaching beginners is a bad idea.
But the video already teaches horrible practice.
:) the outcome is nice, hooray to C feature!
I really would love for you to tackle generics inside C
You should use std::array and avoid using both malloc and new altogether, if you are using C++
What if your realloc fails? I've always realloc'd the original into a temporary pointer and then point the original to the temporary after checking that the realloc succeeded (!= NULL).
If the realloc() fails and you've overwritten the old address then you have a memory leak.
@@anon_y_mousse Yes, that's why I don't overwrite the original without checking that the reallocation DID NOT fail... like I stated.
Can you make a video on less used memory management techniques like memory arenas
Very odd comparison in my opinion. Dynamic arrays like this are in the standard library - they are called std::vector and they even have a function called resize, but you did not even mention them.
Vectors are objects, not arrays. I did mention them (briefly), but the point of the video was arrays.
@@JacobSorber Im sorry I overheard you mention them at the end of the video. Vectors are not arrays, but they are wrappers for arrays, with the .data() function you could even get the underlying pointer.
Reading your video title, I would still say std::vector is the easiest way for resizing an array using a container using the C++ language. What exactly means "best" in your context?
Of course some people may want to use raw pointers and can't use any high-level C++ features, but then I wonder why the title of the video is not "New vs malloc" or maybe "new, realloc" to make it less ambiguous what exactly you are trying to compare. I have a feeling many comments assume you are trying to compare "the C way" and "the C++ way" of resizing an array.
You make interesting videos keep it going!
Few more vectors advantages over arrays:
1. They are self-destructible and do not need the programmer to remember to delete.
2. Copy of the whole vector is simply done by using operator =.
3. If you do not know how many items will be in the vector, you do not need to worry about it. The vector will take care of the reallocation when needed (it does not reallocate for each insertion/deletion).
4. Vector keeps the length, so you do not need to pass the length as an extra parameter.
Hey, I've noticed that you haven't uploaded a video recently. I hope you and your family are doing well! I wanted to ask if you could make a video about tagged pointers, e.g. storing some data in the alignment bits of a pointer or in the upper 16bits which are not used by most current 64bit architectures.
Anyways, enjoy your break and merry christmas in advance :)
Thankyou
Hi Jacob. Thanks for this video. Could you please create a content on near/far pointers? Much appreciated.
You're welcome. Now, that request takes me back. Is anyone still using near and far pointers? I'll take a look and see what I can do.
Be careful with using malloc and realloc in cpp if you’re not dealing with PODs (may have been mentioned in the video, if so ignore me)
Could you make a video about circular buffers?
Use vectors in C++ as it has automatic memory management built-in
yeah i dont use regular c-style arrays in C++ anymore. I only use std::vector, and std::array if i need it to be fixed length.
It's already been mentioned that the order of evaluation of arguments to a function are undefined, so that method of printing the addresses is not a good idea as well as when realloc() fails that the old pointer being discarded like that will cause a memory leak.
So instead I'll address a positive of realloc(), that if there is more memory after your prior allocation that the allocator can merely increase the size by combining the memory after your prior allocation and just return the same pointer. So it won't just be on shrinking that you may not see a copy, it could be on growth as well.
Also, as far as allocation strategies are concerned, the usual method I see taught is to have some #define for a "block" size and grow by that each reallocation, but it's actually better performance-wise to double the allocation when growing.
Different allocation growth techniques exist.
Some multiply by 1.2, some by 2, some go up the Fibonacci sequence.
@@monochromeart7311 Different strategies do indeed exist, none of them better than doubling if you want efficient growth. It's a simple bit shift by 1 and you're off.
@@anon_y_mousse the difference is the amount of memory used, which is an important point.
If you have an array of 2048 items, and then need to realloc extra space, you will end up with 4096 items, when you may only need less than 3000. That's a lot of wasted space.
Reallocations don't happen often based on the strategy, so doing a simple calculation compared to a bit shift is a difference of nanoseconds that won't add up.
@@monochromeart7311 That's actually the point, using that strategy means fewer reallocations, which makes them faster. If you're doing it by a factor of 1.2 then you'll need to reallocate often enough that multiplying floats or even specially handling fixed point math will cause slowdowns.
@@anon_y_mousse I think it's one of those things which might depend on your application.
Like, you might use data in a way that regularly wasting, say, 30% of the size of your containers leads to cache misses or whatever. It's a trade of, there's no right answer with no context.
I think the point of the video was about reserving space. which is what realloc does. and so does std::vector, and even C# containers.
Line 9 there should be a * before array.
I really need to slow down. :) Thanks for pointing that out.
Most of the time, when I use realloc() to slightly SHRINK a block, it just seems to truncate it. Which is smart. I tend to use the same trick in my own memory allocators. BTW, there is a bug lurking in your code, since realloc() MAY return a NULL pointer if it fails. It won't happen very often - but then again: why test for NULL with ANY allocation..?
BTW, statistically the best way to resize an array with an unknown size (at runtime), is to DOUBLE its size each time. It may seem wasteful, but it is the best balance between resizing overhead and space usage. It's not too hard to make a function that quietly handles all the nitty gritty details in the background.
Hmm did you just describe STL vector?
@@Eknoma Idunno - never used C++. It's one of those languages that cherish the motto "Have we thrown in the kitchen sink yet?"
@@HansBezemer You don't need a kitchen sink if you have a fridge which is also a car and a vacuum cleaner that if combined with a rocket which is also a towel, makes a Rube Goldberg Machine that can clean your dishes for you faster than you can do yourself
@@Eknoma Swiss Army knifes - never cut at well as a true knife, never screws as well as a true screwdriver and never opens a can as well as a true can opener.
ArrayList is the best way to resize an array. If you need more space, just create a new array, save its pointer and handle a global index for all arrays inside the class. That way you don't need to move any values to a new array.
resize1 doesn't copy the contents of the array correctly. It needs an asterisk *array in the second argument of memcpy.
Source: use "g++ resizearray.cpp -fsanitize=address" and see how there's an invalid memory access. Or just test it with a debuger.
Good catch. Thanks.
This is a red herring comparison. The "C++" presented here is basically not C++. new + memcpy is not a valid way to create non-trivial objects in C++. Thus this approach is generally frowned upon and not "legal" C++. And to claim that realloc uses "less lines of code" misses the point that std::vector uses even less lines of code, has non of the pointer handling issues and also does the exponential growth automatically - while correctly handing object lifetime.
So no, it's not about "new vs realloc", C++ purists will not tell you to use "new", C++ purists will tell you DON'T use new - use a container and algorithms ;)
And, what does that container use?
And, in case you haven't seen my previous videos on this topic, I like the C++ language and tools, but have very little interest in the C++ religion.
@@JacobSorber tools like "new", "placement new" and others. That's however not important to the point I was making (see next reply).
@@JacobSorber I did not provide any religious arguments. As I have watched your previous videos I assumed you are interesting in teaching and educating. That's why I pointed out you're presenting a misleading false comparison and are presenting borderline invalid C++ as an inferior alternative (when using arbitrary metrics such as "less lines"). If you're not actually interested in the subtleties of object lifetimes, etc., a video only focusing on the subtleties of realloc() would have been interesting on it's own - without the false comparison. Hey, and maybe talk about the return value of realloc() and it's implications next ;)
Hi, nice video! I came up with a rather philosophical question: should we always check malloc and realloc for NULL? Do you think this can avoided in production code?
It’s the safest bet. It’s extremely unlikely they would return null, but if you tried working with that pointer assuming malloc succeeded (when it actually failed), it can crash your program.
In some cases I’ve been lazy, but I always check for NULL now
With malloc/calloc/realloc, I use a temporary void* and check if that’s null in case the realloc fails, otherwise you would lose that memory (unless it’s the very first time I’m allocating, then I will just check that)
Malloc for the win!
It works well for using a dynamic memory. What about to resizing a static array?
You can't resize static array
It would be interesting to see if the c++ compiler would also allocate 1 larger array wirh optimizations turned on. I suspect the c compiler optimized it since you are explicitly saying reallocate this while in c++ the realloc needs to be implied by the compiler which is unlikely in O0.
The compiler doesn't even know about the implementation of realloc, it just uses whatever the stdlib provides.
@@patryk_49 but reallocs implementation seems to notice (probably the os behind) that realloc got called multiple times shortly after another. The fact that it only stopped moving the array after 2 times support this theory. This also means that the os having no idea how much the next few reallocs will be, overalllocated on pure guess. I suspect both c and c++ will fold this to 1 allocation when optimized.
@@redcrafterlppa303 If realloc doubles the memory with each call internally, it would stop changing the memory position rather fast and not need to perform any allocation for a while. This is the most efficient way to implement it and would explain the changes in pointers. The compiler writer might very well know how realloc is implemented as they may be the ones who implemented it, but unless you have higher levels of optimization it's not likely they're going to change your code in that way, and even often if you do they won't.
Can you make a video comparing C, C++ vs Rust ?
We want how read mouse buffer and keyboard buffer adresses also screen buffer if exist
From what I understand, in modern C++ a more appropriate method would be to create a smart pointer of an array that has a resizing function. This means you wont be doing malloc and free manually every-time which is really the security element involved in this situation IMO.
std::vector
what text editor/sdk are you using?
It's Visual Code. It is free from Microsoft and pretty great for a slew of languages therefore you will see it often on tutorial videos.
Ps. It's not called a text editor or SDK but an IDE (Integrated Development Environment)
Where can I buy that T-Shirt? 😅
I find that if you plan proper design, you can avoid most array resizes. Most, but not all. And the more carefully you design for minimal memory reallocations, the fewer reallocations are required.
Did you deliberately use size_t fir amount in stead of ssize_t?
I think so because the copy can't handle shrinking rhe array.
What should be the C++ version of the memcpy()?
An STL function?
The reference in stead of double pointer in the C++ version is already mentioned in the comments.
I think the signed version of std::size_t is still planned for c++23.
in c++ you would use the copy ctor, std::copy, std::memcpy, or what not.
@@benjaminshinar9509 there is a ssize_t
Maybe C specific?
Of GNU specific?
@@maxaafbackname5562
ssize_t was added in POSIX.1-2001.
size_t was added in both C99 and POSIX.1.2001.
I must be doing something wrong. In 40 years of programming in C, I have NEVER resized an array, nor can I think of any situation that would have been improved by "resizing". That is not say that I don't use dynamic memory (malloc & free), but I just never needed or wanted to resize a declared array. Sounds like bad algorithm design to have a need to do that.
Must be nice never dealing with user data, never having to sanitize input. I'd guess you don't use too many hash tables either, or if you have they've never grown. Unless you think you have a better strategy for growing than to use realloc() and possibly not move your data when there's enough space behind it for the allocator to adjust the length instead.
You must have spent the last 40 years on a very specific use case, because the number of use cases, along with the solutions to those use cases, are infinite. If you can't even imagine any case at all, that could be improved by resizing, then I'd suggest = realloc(imagination, sizeof(imagination) * 2);
Rust's realloc would allocate some extra space for every realloc (if the item size is smaller than 1kB) to avoid rapid realloc (which not only does a system call but also has to wait for the OS to alloc the space), I'm not sure about C++'s vec
Yeah, plain arrays in C++ are not efficient, which is (one of) the reasons you have the STL vector, which is perfect for exactly this.
The only time you should *not* use a vector, is if you don't need resizing at all, and the size is a compile-time constant. And even then, you shouldn't use new, but a STL array.
something always is on my mind is how to resize an array on demand. like let's say that I am doing some kind of an app that takes input from the user during execution like a server or something. How do I write code that reallocate memory when the array becomes full? how can I write a function like input() in python, after all python interpreter is written in C. So is there a quick and easy way to essentially take input of increasing size on demand?
🌸 ᴘʀᴏᴍᴏsᴍ
You could've at least avoided teaching the newbs a bad habit of assuming size_t is an unsigned long by just using %zu instead, they can learn about that odd bit in another guide/video
Your first parameter is **array. But you are using *array in realloc function ??? Perhaps this is why C is an alien language for me.