No, more like including a library with thousands of lines VS a struct with 3 pointers

C macro that declares and defines the array struct and functions using token paste operator. VS Stretchy buffers

@@srijanpaul why a macro if you can make a template or just use void pointers

@@igorswies5913 In C macros are the closest thing to templates and that's what people usually do for low budget std::vector

@@srijanpaul I dont care about what people usually do and I'm talking about C++

No it's still most efficient if you know how much memory you will use and just allocate upfront. Many games and engines still use these types of allocators ALL THE TIME.

@@captlazerhawk ok buddy

@@captlazerhawk "if you know how much memory you will use" Yes... Exactly

@@oivinf thats why you often just limit size and then cleverly reuse

@@oivinf Knowing how much memory you will use, as in knowing the max amount of memory. You don't need a dynamic array for some things if you know your memory use won't go over a certain amount. This is everywhere in the lower levels of game engines and rendering apis.

Hi Oliver, that is a great point and you're right that this is something I should have included in the video. Thanks for sharing!

He's using manim, that's why

@@jonasdaverio9369 oh word that's cool

Same! haha. I did when i started programming in C++, i didn't know it already had dynamic array libraries. :P I think most low-level programmers had, at least once.

@@rhodexa I did it in C - only after watching this video, based on what it said. It was pretty simple to do actually. :D

pretty sure every programmer that was banging keys in the 80s or 90s have written many dynamic array implementations, each having different strengths and weaknesses - hash tables, splay trees, hash tables of splay trees, and so on - the common misunderstanding folk have about all this is that its still fixed size at the end of the day - moving responsibility to a different allocator than your own doesnt change things

thank you kind stranger

You are a hero

hajahhrhahsha I had to use my own comment when I came back 2 years later

if it's for reconstructing a image then why didn't you just use a regular array?

@@phillipanselmo8540 Because C, and no way to determine the size of the final image ahead of time.

Assembly: you guys are able to declare variables?

Brainfuck: wtf

Stretchy buffers.

ever heard of malloc/realloc/free?

@@igorswies5913 : have you heard about efficiency ? have you needed to process 1 million operations in few milliseconds ?

@@ishdx9374 what library is this?

@@timkluge426 It's called Manim. It's on GitHub.

@@timkluge426 check description

Linked list as also the disadvantage of memory not being like an array and take a lot of time in that case

Linked lists can be kept in sorted order by using insertion sort when appending elements. Insertion sort is great for doubly linked lists because you can eliminate the bother of swapping each element between the unsorted element and its sorted place, just by rewiring some pointers.

On many computers, accessing many areas of memory that are close together can be much faster than accessing areas that are widely scattered. In the 1990s random accesses would often take between 100% and 300% as long as sequential accesses, but today that ratio has gone up by more than an order of magnitude. Even in cases where a linked-list approach would only use half as many total accesses as an array-list approach, performance may still be massively worse because all of its accesses would hit different rows of DRAM.

linked lists are horrible. period. doesnt matter wether they're forward linked, doubly linked or quadruple linked.

@@TheFlynCow Linked array-lists are useful for chain bucket hashing; I'm not sure what data structure would really be better for that purpose. Linear-probe hashing might offer better cache coherency, but at the expense of very bad behavior if hash table entries get clumped.

Different use cases can benefit from different strategies for growing depending on factors such as: - how constrained system/program memory is - how often arrays are expected to grow - how much arrays are expected to grow by The exponential growth strategy also doesn't always need to be strictly double. Sometimes growing by only a factor of 1.2, 1.5, 3, 4, etc. As for the memcpy point, not all data types are safe to straight up memcpy, at least in C++. memcpy also wouldn't really fit into the video, because the video is more about the conceptual idea behind dynamic arrays rather than implementation details.

@@mettaursp309 Extending by a fixed size, while I can probably come up with uses, is still SUPER niche. Doubling is indeed what is usually done. And as explained in the video, using a fixed size doesn't help the scaling any. I suspect the follow-up video that was mentioned at the end, is going to explain how doubling is used. As for memcpy and elementwise assignment... memcpy does nothing different. It's still just a loop copying over each word. That is assuming the assignment operator doesn't do anything crazy. I don't use C++, so it might well do that.

@@Yotanido I agree that the fixed amount increments has pretty limited use cases. I don't think I've ever personally run into a case where it would be the best option, but I've also only programmed for consumer grade PCs, not smaller devices like microprocessors. For C++'s std::vector growth factor, it seems to not be defined in the standard so it's implementation dependent. A lot of the compilers do a factor of 2, but Microsoft being Microsoft chose 1.5 for at least one of their versions. As for memcpy, yeah the relevant functions like assignment operator overload, copy constructor, move constructor, and so on can be changed to perform nontrivial operations. I believe that std::vector will use the move constructor if available and compatible, otherwise it will use the copy constructor. I'm not sure if it falls back on memcpy if the class is a plain old data type though.

It looks like it was made using 3Blue1Brown's manim library

Denominator or Numerator?

Only in non-strictly typed languages. In strict languages such as Haskell or Rust, a tuple is a fixed length sequence that can contain mixed data types, i.e., you can do (i32, String) to have a two element tuple with a number and a string. Arrays on the other hand must contain elements of the same type, mainly due to the fact that the size of each element must remain the same to be able to find elements. Also, it makes it really difficult to remember what is what in the array if you mix types.

Thanks for the comment! And yes, this is a great point. I added the a link to the code used to generate the animations in this video in the description.

Thank you and good luck.

can't say I'm surprised

i mean its using code from other classes

No. Java does not do this. The ArrayList.add method checks if there's enough capacity, and if not, it calls the ArrayList.grow method by indicating a MINIMUM GROWTH of 1 element. The call to grow will then delegate the calculation of the new size to the internal JDK method ArraysSupport.newLength with a preferred size of twice the length of the backing array. Then, the backing array is expanded with whatever newLength returns. This means that, most of the time, Java ArrayLists will grow by a factor of two once there's no more space. Please don't spread this kind of rumor about Java. They're part of the reason it has an undeserved bad reputation.

@@maruseron Good to know, last time I read through the code was a looong time ago, so I probably forgot this part

Oh, that is O(N), you put it nicely in the next one about dividing N into half repeatedly and adding. Technically 2N but we don't care about silly constants.

@@DFPercush Your growth factor is a common one. ArrayLists in Java and std::vector in C++ both use 1.5. Other languages like C# and Rust use a factor of 2. They have the same time complexity, but the rationale behind using larger growth factors is that memory is usually pretty cheap, so it's better to reduce the amount of resize operations. Going even deeper, a growth factor lower than 2 can be beneficial in languages that don't have managed memory. When a factor of 1.5 is used, the new larger array can fit into previously used blocks of memory. With a factor of 2, it will never fit. This is assuming that the previously used blocks are contiguous, which is often not the case in real world applications. Aforementioned managed languages complicate this even further, because they can shift things around in memory under the hood to reduce fragmentation.

@@DFPercush well technically it is O(N) big O notation just says it is something within a constant factor, so saying O(2N) is not technically correct:

For a linked list, insertions are more efficient, because you don't have to copy every element to a new list like you do with an array. You just point the pointer of the tail of the list to your new element. They're particularly efficient for inserting elements in the middle of your list. With an array, you'd have to make your new sized array, copy all elements above that index but moved over by one, then copy the insertion, then copy the rest. With a linked list, you just have to reassign some values to some pointers. The problem with linked lists is that to access any given element, you need to go through each element and follow the trail of pointers to get it, whereas for arrays, you can access any given element with no loss in efficiency; because array elements are stored contiguously in memory, the computer just has to add to a pointer to access them, as opposed to dereferencing a pointer, assigning it to the current node, then repeating until you find your element.

Why would you do that? Arrays can be of different types (char, int , short or anything else), each lf those different types has a different size (1, 2, 4 or anything else) a pointer is always 4 or 8 bytes (depending on if youre running on 32 or 64 bit). Not to mention it makes array access harder. Lets say i have an array of 3 items then append 3 more to it. Now lets say i want to get the 4th element of the array. With the standard implementation i can just array[3]. With ur implementation u fitst have to check if the element is in the original array, if not, do math and check if its in the next array, and so on. Also theres a 4/8 byte overhead for each time you append something. Also removing items becomes even trickier

@@c0smo709 on the first part you're right, but at least in c++ you can overload the [] operator for easy access. I made an implementation of it after I made this comment just to see how difficult it is. I'm pretty bad at c++ but I had pretty decent results (around a million appends + a collapse took 2.5 seconds iirc. It can definitely be optimized though. It does make insert operations quite a bit faster though.

@@thedudeguy242 post the code and i will benchmark it with mine

Because then youre wasting memory. Also whay if even the really big one is too small?

realloc is just alloc + copy + dealloc, it just does the copy step for you.

@@API-Beast oh damn really? I guess that explains the performance... I might have to implement my own version now lol

@@matthewrease2376 The Standard would allow realloc() to, at its leisure, either adjust the size in place or create a new allocation and copy the data, but provides no means of distinguishing which of those an implementation actually did. It would be useful if there were a variation of realloc() which would ask to make an allocation as large as possible, up to a specified limit, without moving it or affecting the validity of pointers to it (the function would need to be passed the address of a size_t to receive the new size), but as it is the Standard doesn't even provide a means of knowing whether pointers to a re-allocated region would need to be recomputed.

Or in C (scream!)