Hope you all enjoyed the video! Have a go at the exercises and implementing some of the features we didn't get to in this video (eg. copy/move constructor + operators for the Vector class). And finally don't forget that the first 1000 people who click the link will get 2 free months of Skillshare Premium: skl.sh/thecherno0820
I am really happy with this video! While you provided the solution, I wish you would have also highlighted the issue of the old allocation: it constructs! Imagine if your class had a Sleep in the constructor, or more realistically, a heap allocation. With out operator new, it would slow you down substantially whenever you wanted to resize your vector. Especially over thousands of items.
Hello! Thank you for the video and for your work! I found that the... outcome of this code depends strongly on the compiler. May I humbly suggest a topic for a video about compilers in more details, which one do you use with what flags and what are the pitfalls or gcc, g++, clang, calng++. I am working in Ubuntu and I found that the only compiler that works for this project is "rustc" that I've never heard of before :)
You still have a bug in ReAlloc function in line 95: newData[i] = std::move(...); - you can't use assignment operator here (either move or copy) because newData[i] is uninitialized memory - it is not the object of type T and by calling operator= (again move or not) you treat it as if it is object of type T. So instead of that you should use placement new once again so change that line to: new (&newData[i]) T(std::move(m_Data[i]));
Thank you man!!!! I am looking for exactly the fix for this issue! The code does not work for std::string, it crashes exactly at this line!! Thank you man I appreciate it!
Yes, I've noticed that too. I'm mostly going by myself but my ReAllocate function is very similar to this. My constructor for a class allocates some memory but the constructor is not called so when assigning (copy is called) the data is just leftover memory.
hey newBlock is of type T* so I replaced the code you gave, but now its showing Buffer overrun while writing to 'newBlock' error 'Vector3::Vector3(const Vector3 &)': attempting to reference a deleted function
It is initialized. When you create your array as "new T[size]" it initializes every element with default constructor. Which is a problem, because what if your value_type doesn't have default constructor? To create uninitialized array you need to use allocator. I also would suggest to use std::construct_at instead of placement new operator. It does the same thing, but more descriptive and easier for an eye.
Already figured out how. I have just write begin() and end() methods which returns something acts like iterator, but i done this in custom string class, in vector class it should work the same way.
@@sandeepkalluri Essentially, delete operator does 2 things: call dtor, and then free memory. delete[] call dtor of each of its elements, then free memory. The problem is, if we manually call dtor of some item, it will in fact delete its members memory(int* in our Vector3 example), but the Vector3 instance is still physically present in the contiguous array of our Vector instance. That means that if we call the Vector delete[] method, ie when the Vector instance is out of scope in this case, Destructor of each item may be called Twice ! The problematic items here are the one cleared or popped back. When delete[] iterates through items to call dtor and free, it will not stop at our m_Size defined value, but out Clear implem does. If you want to check stuff by yourself, just simply emplace and immediatly pop some object from Vector in debug mode. You can clearly see that in the memory our object is still living after pop. Destructor of an instance manages its member destruction, not the object itself. We have a similar concern with the new operator(although it doesn't cause crashes): it allocate memory, then call ctor. In case of re allocating resource (or "reserving"), we want to make sure we have enough space for our future item to be added. We do not want to actually create default objects waiting to be overwritten by future actual pushed back ones. That is why we use this syntax: ::operator new which only allocate UNINITIALIZED memory, ie memory we own but may contain unpredictable garbage. Hope this helps.
@@sandeepkalluri new calls the allocator to allocate memory, with size of the type you passed in, and then call the constructor to create an object on that memory allocated delete calls the destructor first, and then calls the deallocator to deallocate memory the ::operator new only allocates memory, and it does not construct anything, the memory is now yours, but it has nothing in it, to construct an object of type T in that memory, you have to do something called a placement new new(address) ctor(data) so the normal new operator that you would normally use, it does two things automatically, allocate, then construct in this video, what you're doing is you do those two things by your own the same goes with ::operator delete(ptr, size * sizeof(T)) it only deallocates, and does NOT call the destructor so what the normal delete would do is to call destructor, then call the ::operator delete behind the scenes, the deallocate since in this video, you have a lot of parts that you call the destructor explicitly, and then finally you call the normal delete, which calls the destructor again, despite that it has already been called at some other part of the code if you're sure about calling the destructor exactly where and when you wanted, then all you need is the deallocator And since you can't call ::operator delete on the normal new, you have to also do the two task: allocate by using ::operator new and placement new manually, just so the ::operator delete can work, deallocates what ::operator new has allocated
Wow, that gotcha moment at the end was so inconspicuous that I'm a bit shaky in writing efficient C++ code and debugging it. May this series never end for the good of me!
About 2 years ago I really became intrigued by stl. The vector class was the first one I tried recreating. And failed miserable. How ever I have redone this exercise about 20 times since. And I can write a vector class with the majority of the features one would want in about 1 day. I encourage everyone to do this exercise every once in a while. You always learn somethimg new.
This is a bug: newBlock[i] = std::move(m_Data[i]); "newBlock" is uninitialized memory - calling move assignment method will likely lead to a crash (depending on T). Do this instead, using the move-constructor: new (newBlock + i) T(std::move(m_Data[i]));
Yes I don't know about you but I get a runtime error with the original code and I ended up with the same conclusion. For some reason, The Cherno does not seem to have this issue...
@@arnaudgranier3045 Either the compiler is zeroing the memory for him (which would just happen to work for a lot of objects, if all zeros are a valid state), or he got lucky. A proper debug build would initialize that memory to 0xfefe to shine a light on this bug.
The vector3's constructor and move assign function have problems, "m_MemoryBlock"cannot simply assign value(m_MemoryBlock = other.m_MemoryBlock;), if we push back a vector3 value(Vector3 v3(1, 2, 3); vec.push_back(v3); ); it will double free(v3 free once, vec free second)
The vector3's constructor and move assign function have problems, "m_MemoryBlock"cannot simply assign value(m_MemoryBlock = other.m_MemoryBlock;), if we push back a vector3 value(Vector3 v3(1, 2, 3); vec.push_back(v3); ); it will double free(v3 free once, vec free second)
42:48 Is this assignment valid in 96 line (underlined by the way) ? newBlock[i] = std::move(m_Data[i]) It is assignment xvalue object to raw memory. Is it ok ? Shouldn't be placement new again something like that ? new(&newBlock[i]) T(std::move(m_Data[i])) If yes, then maybe your code has UB but did not crash.
I think it doesn't matter how the memory where the object gets copied looks like. It's just important that there is memory that can be written. The move constructors initialises the memory in the raw area how it needs. Every time a c++ class gets allocated the constructor writes data into raw memory. The member functions and stuff gets not stored in the allocated memory, if that was your doubt. The allocated memory just holds data and on construction the data is always raw. Hope this helps a bit.
you are correct. the implementation in the video can mess up if you create a vector of a class with virtual methods, since the vtable pointer of the object won't be initialized.
I hope very much that the std::vector is NOT written like that (17:20) because downsizing without deleting (calling destructors) of excessive vector elements is a direct path to a memory leak.
I'm getting a problem with PopBack. My editor/compiler isn't seeing 'T' as something valid within the scope of the function, and as such when I try to call the destructor on T, the next time that it tries to print the value from my Vector it's printing garbage (negative infinity). not sure what's wrong or how to fix this, I went back to the part in the video but couldn't figure out what I could have done wrong, and I'm not sure what to search for to figure out how to fix it my code, for reference: void PopBack() { if (m_Size > 0) { m_Size--; m_Data[m_Size].~T(); } }
It is cool content! Thank you very much, Cherno!!! Like pressed! One thing I wish the vid had is a link to a git repo with code. Though, I am coding the data structure along with you, some place to look up code would not hinder (for educational purposes) 🤠
Learning data structures in c++ makes it much easier to understand and do in other languages. C++ was the language used in my comp sci program for intro to computer sci and for data structures and algorithms and now I’m doing data structures and algorithms in JavaScript preparing for interviews and that foundation in c++ helps a ton. If anyone is a student and has to do c++ in school, don’t be overwhelmed. Trust the process, work hard, and you’ll do just find. Cherno clutch yet again with perfect quality content!
42:06 line 98-99 calling the destructor on m_Size works if newCapacity >= m_Size. But if newCapacity < m_Size, you might miss out destructing some objects in m_Data?
cant get the variadic emplaceBack function to work at all, with or without std::forward. its exactly how you have it in the video, too. might be because im using Clang instead of MSVC. it throws an error about "Excess elements", which i guess means its not going through more than one.
Anyone know why I am getting Copy Destroy twice before the 'Copy Copy Destroy Destroy Copy Destroy'? In debugging each time it pushes back a new object, Copy and Destroy get printed, so why is there only one showing in the video even though 2 objects are pushed back? Thanks.
I did my own implementation using std::move(), it works fine on reallocating, but only in the release mode, and crashes with "heap corrupted" error in the debug mode.
hmm, why would it? std::string is responsible for it's own allocations and deallocations, and as long as the vector doesn't call the destructor twice, then it wouldn't.
If anyone else is confused to why std::string isn't working, my understanding is that in the PushBack function or wherever you're setting values in m_Data you actually need to placement new the object into place not use the assignment operator here. Basically you'll wanna replace m_Data[INDEX] = newValue; TO new(&m_Data[INDEX]) newValue I'm fresh to this idea so if anyone has a better description of why, it'd be much appreciated. Thanks!
I have added more constructors which takes arguments as initializer_list : 1. Vector(const std::initializer_list&); 2. Vector(std::initializer_list&&); Then I have created a Student class and created three objects of it s1,s2,s3 And then I try to do following: Vectorstudents = { s1, s2, s3}; Vectornumbers = { 1,2,3,4,5,6,7,8,9 }; So as I am passing s1,s2,s3 as "lvalues" for students and 1,2,3,... as "rvalues" for numbers. But in both of cases it is calling 2nd constructor. So why Vectorstudents also calling 2nd constructor? Can you help me ?
I think it's because in both cases you're still initializing the vector with temporary instance of initializer_list (so r-value). If you want to call the l-value constructor, you'd have to do something like: std::initializer_list list = { s1,s2,s3 }; Vector students = list;
I think there is a bug in reallocate function. If we enter in that if statement : if (new_capacity < m_size) m_size = new_capacity; then I think in for loop when we call destructor of each element, then if old m_size is bigger then new m_size then I think we do not call destructors of all elements. Correct me if I'm wrong. Great job btw :)
Possible fix: At the start, save the current size. After the loop, enter in a new loop starting from the current size till the previous size. Then call destructors for those.
But what if you call Clear() on the object, and then when the object goes out of scope, its destructor calls Clear() too, leading to the same error again?
When calling "T* new_block = ::operator new(new_capacity * sizeof(T));", I get a "new_block" that is only 8 bytes in length, i.e. "sizeof(new_block) == 8". Since our "Vector3" type is 32 bytes in length, I even tried being explicit about it and doing "T* new_block = ::operator new(64);" (allocating space for 2 Vector3 elements on first reallocation) just to help me debug. But even for that call, I still get a "new_block" that is 8 bytes long. Am I doing something wrong when calling ::operator new()? Anyone have any idea why I'm getting the same size allocation regardless of what I pass to ::operator new()? Should we be using ::operator new[]() instead?
Hi @TheCherno, there is a slight issue in your Clear() function. You probably know about it, but i will mention is anyways because there is no mention in the video and it took me a couple of hours to solve it. (Yes i have watched Iterators video, but this issue was not solved (maybe im wrong) there). Clear function does not release memory allocated for m_Data, it only calls for destrustors. In order for Clear function to work properly, it need to look like this: void Clear() { for (size_t i = 0; i < m_Size; i++) { m_Data[i].~T(); //calling all the destructors. } ::operator delete(m_Data, m_Capacity * sizeof(T)); // releasing memory, also, wouldnt this call also call each destrustor? Im not sure, maybe you can check it. m_Data = nullptr; // this one is important, because if we call Clear second time right after first call, without allocating new block of memory, there will be a memory access violation m_Size = 0; m_Capacity = 0; //can be 2 if ReAlloc does not fix bug, where if capacity is 0 vector can not grow. }
Clear is not supposed to release the memory, it is just a function that's supposed to remove all elements from the vector. The m_Data buffer should be left like how it is because we may and will probably still work on the vector after calling Clear on it. We only release the memory whenever we want to destruct the vector object. This idea is the exact same with std::vector or many other vectors. EDIT: Also placement delete doesn't call destructors.
Great video! It looks to me that there is a potential memory leak in ReAlloc function if new capacity is smaller than size, Desctructors will be called only on first newCapacity elements, or am I missing something?
Thanks for your video, I really enjoy all your series. I have a question about T* newBlock = new T[newCapacity]. when it declared, why it shouldn't be deleted like the "delete[] newBlock" after "m_Capacity=newCapacity"?? Is that not leaking a memory ? if you do pushbacks 100 times, newBlock would stay 100 memory blocks in memory , am I incorrect? Please teach me.
m_Data gets set to newBlock, so if you delete newBlock, you essentially delete m_Data, which is a big no no. You only need to delete the old data (m_Data) before you set m_Data to newBlock. After that both newBlock and m_Data point to the same memory address.
" std::" to be written in every line and every word makes me confused and makes the code really complicated in how to read it. My eyes are literally on "std::" instead of looking on what the code does. When I try to understand my professor code, I literally delete the "std::" and put instead names space std;. Also, I organize the messy code because he also write the function like this Void Function{Data}cout
If you keep doing this on a large-scale project, essentially the compiler will get very mad at you. Another library you use may have a function like move. Imagine you did using namespace on both, the compiler wouldn't know which one to call. For little projects, it should be relatively OK to do using namespace std, but on medium to large scale projects, it is a big no no. And don't ever do "using namespace std" in header files, never ever.
This video inspired me to create a sort of a mish-mash of two data types together, basically a compromise b/w a linked-list and a vector. What if you have moderate-sized arrays that link to each other? Array[10]->Array[10]->Array[10]->... and so on? i) This way, you don't have to make as many hops for reaching an element. MishMash[35] is actually just two hops away, rather than 35 hops! ii) You still have to allocate a new buffer for every 10 inserts (this could also grow exponentially), but you don't need to copy the old buffer. I feel like this data type can be used for vectors that dramatically alter in size frequently.
very interesting video and series really! I have one comment though. In your Vector3 class implementation of the move assignment operator (line 41) I think you should call delete m_MemoryBlock before assigning other.m_MemoryBlock to it, otherwise a memory leak is created. Correct? But then, if you do so, each time you move a Vector3 element to the vector (PushBack of ReAlloc function) you get a memory access violation because you are moving the element to an uninitialized memory block and the delete m_MemoryBlock in Vector3 move assigment fails. To solve that I think it is necessary to initialize to 0 the memory allocated with ::operator new every time this is used, with something like std::memset(m_data, 0, m_capacity * sizeof(T)); In this way the delete is called on a nullptr and does not fail. Am I wrong? Thanks.
Yes, you're a lifesaver! I had this exact issue while trying this Vector class out with my own implementation of String, it would indeed crash when calling the move assignment operator was called on non-initialised memory. However I still found a case for a crash: when calling pop_back, my own String deleted its m_Data block but did not set it to nullptr; So when calling push_back again afterwards, the same memory access violation happens. The fix was to memset to zero also on pop_back() and on clear(). Another fix would be to edit my String destructor to set the m_Data to nullptr, but I find it a cleaner solution to do this within Vector. EDIT: he addresses this at the end of the "Writing an iterator in C++" video. The clean solution to fix this issue is with "placement new" construction (like used in emplace_back) instead of the assignment operator.
Can you make a video explaining your coding style and naming conventions? I think it would be cool to see a little video about why you prefer PascalCase and prefixes on variables (like m_ and s_) and what are your tips for choosing naming and coding conventions. It would also be cool if you could talk about your C# conventions as well (as far as I know, the m_ prefix isn't very popular in C#, so I think it would be cool to know if you stick to it and why).
He once said that he used to use camelCase back when we was doing java but that after sometime at EA he got so much used to PascaCase that he cant use camelCase anymore (sorry bout my english)
Choose what do you personally prefer (or make a consensus within the team you are working with). Some IDEs (e.g. CLion or VS w/ReSharper) allow to set preferred naming conventions in Settings and they will underline inconsistently named variables etc. Big companies have some variable naming (and code formatting) standards, you can find them easily, search "Mozilla C++ coding style", "Google C++ Style Guide" etc.
Is there a reason why C++ handles the new [] type inconsistent? If you have this: "new SomeClass[size]", the default constructor will be called. If you do this: "new int[size]" (buildin primitive type), there is no pre initializiation. But if you call new int[size]() you will get it. Consider this code: #include class Vector2 { public: float m_x, m_y; Vector2() : m_x(0), m_y(0) {} Vector2(float x, float y) : m_x(x), m_y(y) {} }; int main() { constexpr int size = 5; int* intArray = new int[size]; int* intArray2 = new int[size](); int* intArray3 = (int*)::operator new(size * sizeof(int)); std::cout
try implementing vector using the the specifications on cppreference, just by encountering custom allocators in a practical setting actually teaches you a whole lot about them (tip : look up std::allocator_traits first to see how c++17 and on handles allocators. )
I tried to figure out an function to do the doubling of the capacity initially, but heavily dampening as the capacity grows, but nothing was really that satisfying. Like it'd always still grow quite a lot once it reached like 500. Which is obviously quite unnecessary as you'll take forever to fill it even if you had that much more data. Or it wouldn't grow a lot in the beginning which is also the opposite of what you'd want to. Without doing if checks for the size, that'd also be the opposite of what we want, building processing cost trying to save it.
new(&m_Data[m_Size]) T(std::forward(args)...); how cools is that 😂 that's awesome 😎 I didn't know that I can invoke new operator like that, thx ✌ By the way, examples like this are the best how to learn and understand how underlying std library works. 👍
That's called "placement new", and it is indeed really powerful! Have a look at memory pooling and custom allocation, the whole subject is quite interesting.
How should I return a range of the vector? Vector getRange(size_t startIndex, size_t count) const { Vector tempVector= Vector(); for (size_t i = startIndex; i < startIndex + count; i++) tempVector.pushBack(std::move(this->itemsArray[i])); return tempVector; // This is wehre it calls "tempVector" destructor } Because it deletes tempVector via destructor and then returns empty vector.
You could only have size if you predefined the number of elements you will allocate (2, 4, 8, 16, ....) saving 1 size_t sacrificing performance, no?
2 года назад
1. std::construct_at instead of operator=(T&&) in emplace (Edit: after some research I discovered std::construct_at is introduced in c++20, for c++17 and below, new() must be used) 2. you violated rule of 0/3/5 implement those ctors/ops! (TIL I learned there was a malloc/free counterpart in c++ in the form of ::operetor new/delete)
Getting an segmentation violation signal in the push_back function and have no idea why. All i'm getting is that is is caused by a READ memory access, which is m_Data[m_size] = value;
After all the fame, the fact that you keep this C++ series for dummies like me going, is amazing! The game engine series is way over my head and the reaction videos are not really my thing.. but I do hope that you are getting all the compen$ation you want because you deserve it... kuddos mate
0:25 Okay I can't take 4 dimensions anymore. I need to see how it looks. So I'm going to challenge you to create a 4D renderer. (I think it's suitable because you like graphics programming the most, correct me if I'm wrong.)
yeah, its official- im too stupid for this. i just have to make peace with the fact that I belong in the broad category of people whose dreams dont come true.
40:13 Constructors are being called there if you do a cout in your constructors you will see them print. But I assume the point being that they don't need to be called so thats why we switch to an operator new.
an optimization that i use in my game engine array class, is using type traits to check if T is a POD, and if so using memcpy (not memmove for performance) to copy elements instead of using std move. compilers may notice this, but i added it just in case
Stack allocated vector that is actually just a single node in a linked list. Every so often you get a slower step, but I am so intrigued to try implementing it
I still don't understand how size can become greater than capacity. As soon as it becomes equal we are allocating new memory and hence it can be either less than capacity or equal to capacity in case of push back operation as we do not push more than one item. Does any one have any idea?
is this code available to check somewhere? I haven't quite understood the last part with delete with non trivial data types and variadic templates thing.
Very cool! I think I “know it all already” but usually learn something new in these! I’m writing my own containers now for my personal engine project and great to get some ideas from The Cherno 😀
Holy, C++ is complex as duck! Now I understand why Linus doesn't want it in the Linux kernel. Imagine debugging a code with this complexity that wasn't made by you. The implicit things you need to be aware of...
This is very strange timing because I just coded my own version of a vector class a few days ago. I'm curious how much different my implementation was from yours
Check out the time 22:32, Only four "copy" get printed to the console, which made me confused, I think there should be five "copy", three of them from the right value when creating those three Vector3 objs, the other two “copy” are from ReAlloc when the vector's size increase from 2 to 3, then I realized in Cherno's video, the information printed may not be complete, so indeed five copies should be printed, am I right?
Why, in ReAlloc function if we instead of this code line: T* newBlock = (T*) ::operator new(newCapacity*sizeof(T)); write this code line: T* newBlock = new T[newCapacity]; Then at this code line: ::operator delete(m_Data, newCapacity * sizeof(T)); We get error, exception throw.
