Dynamic Arrays in C++ (std::vector)

hey what's up guys my name is the chana and welcome back to my state boss boss series today we're going to be talking all about dynamic array since a boss boss specifically the standard vector class so now that we're finally beginning to write some courtesy bus boss is very important that we get accustomed to C++ a standard library or in this case something called a standard template library now the Santas template library is essentially a library filled with containers container types right things that contain certain daughter and is called a standard template library because you can template it into anything the whole average templated meaning that the underlying data type of the container so in other words the data type that the container contains that is actually up to you to decide the whole things made out of templates which reminds me we need to talk about templates and we will very soon templates are a huge topic so we'll kind of divide it from beginning to advanced kind of templates as we go along but essentially all you need to know to use that you don't need to know anything about templates to actually use the senate template library all you need to know is that you can provide the underlying data type that this data structure actually handles and that's pretty cool it makes it very versatile and it means that you don't have to resort to write in your own data structures or anything like that so a bus Clause provides us with a class called a vector and that vector is in the STD namespace now it's called better that's the first problem why is it called a vector well there's actually a story behind that I've linked as like an article or Wikipedia page in the description that will actually talk about that but it shouldn't be called vector it should be called something like ArrayList because that makes a lot more sense is essentially a dynamic or dynamic array but not vector vectors a very weird name for this and a lot of people who first kind of get into C++ really get confused about what honor this vector thing isn't is it a mathematical vector no no it's it's just it's kind of like a set it's a set that doesn't enforce any kind of uniqueness to its actual elements so in other words it's basically an array but unlike the normal array types in in C++ either just raw arrays or the standard array class which we might which we actually did mention in the arrays video if you guys haven't seen that click up there but we will probably have a dedicated video about that as well unlike array this can actually resize means that when you create this vector when you create this dynamic array it doesn't have a set size you can give it a set size and whatever if you want to initialize a with a certain size but you basically don't give it a size you just create this vector or this array and then you basically just put elements into it and every time you put an element into it the size grows so I can start off not knowing how many elements actually want in my array and then just push ten things into it and suddenly I have an array with ten items now two people who kind of are new to programming or new to computer science might be like well how does that work how could how is it possible to just have an array that resizes and we're actually going to over the course of this simple spice series we're actually going to be rewriting a lot of these data structures that because they're sensitive waswas ourselves and in a lot of cases we're actually gonna optimize them and make them a lot faster than the ones in the standard template library because this one's on the sentient template library aren't especially fast that's not really the priority of them and so in a lot of cases studios and teams end up actually creating their own container libraries in example I work at AAA so an example is we use something called EA STL there's a link to that in the description below it's on github you can look at the source code that's one example of something that is actually usually in most cases a lot faster than the stuff that's actually in a standard template library anyway I'm getting a little bit ahead of myself here um the point is that the way that Santa vectors actually work we'll talk about that more in more detail in a future video however the gist of it is that basically when you exceed the size that is allocated so when you make a vector it might allocate like ten elements for example or enough memory for ten elements when you exceed that it basically creates a new array in memory that's bigger than the first one copies everything to there and then deletes the old one and that way you suddenly just have basically a new array as somewhere else in memory that has a lot more storage and you can keep adding things to it like that in practice it actually tends to allocate quite often and isn't the best performance wise unless you set it up properly so this video is just going to be for beginners who don't know what what this vector thing is how you can use it and all that and then I think the next video after this one we're actually going to talk about specifically how we can use the standard vector in an optimal way and that will kind of get into some more advanced things so if you want to check that video out if you already know how back to works and you wanna waste your time watching this video click on the link right there and that will take you to the advanced I guess video and we'll talk about how we can optimize our usage of the vector class but for now let's create a dynamic array so what I've got over here is a basics dropped here there's the vertex this is specifically a vertex position I should add as you can see it's got x y&z this is just a dummy class it really could be anything I've also written an output operator over here just so that we can print this easily to the console if we want to make an actual static array of this we would kind of have two choices right ignoring the standard array class we could just create a static array which might have five elements in it but this way we're kind of getting tied to the size and even if we do allocated on the heap like sorry you can see that we're kind of still tied to this size and we've kind of allocated five vertices which means that we can access zero through four again if you're not sure how arrays work definitely check out that video first but we can access the index 0 through 4 and then if we try and go higher we get run into a problem and sometimes that's just not good enough because we want to keep adding vertices for example we might have a program where we allow the user to enter in data we don't really want to stop the user after I don't know maybe ten vertices or something I say sorry you can't enter any more if we want to keep that going we need a way to say that when you've reached them that max capacity resized get bigger so that you can store more data another solution to this problem is kind of allocating an absurd amount of vertices and then basically just saying that's the hard limit for the program anything above that is ridiculous we're never going to hit that anyway so basically this program does support unlimited vertices in a way but of course that's also not ideal because it means that you're using all of that memory whereas if if we only have five vertices that's a huge waste so what we can do instead is use the vector class I'm going to include vector over here and then I'm going to go ahead and make one so the way that we make one is we type in STD vector then we specify the type now this type is just a C++ type of what what is actually going to be in the array so in our case we want vertices so we'll type in a vertex now call this vertices just like that and that's it we're done now it's worth noting that unlike languages like Java where you cannot pass primitive types in here this is a C++ template so you can pass primitive types in here I can type int like this or float like that in Java we would actually have to use the integer class or something like that but this is very similar to C sharp as well where we don't actually have to specify the class type we can just specify the raw type the primitive type someone change this back to vertex now note that I'm not storing a bunch of pointers to the vertex to vertex structs right I'm actually to storing vertices just vertex U just in line and there's actually a big difference between that a lot of people tend to ask should I be storing pointers to heap allocated classes in my vector or should I be storing stack allocated basically in line allocated like vertex classes or vertex structs and the answer that is it depends it really does depend I think I'm gonna make a video in the future that will talk about this specific problem in more detail because for a lot of people it's it is hard to decide whether you should be using like vertex pointers in this case or just vertex objects right there's a big difference the primary consideration is that it is technically more optimal to store vertex objects instead of pointers because if you solve vertex objects your memory is going to be in line dynamic arrays are arrays in the sense that their memory is contiguous which means that it's not fragmented in in memory right it's all just in a row and if you store vertex objects in line like this you've literally got one in vertex XYZ XYZ XYZ XYZ one after the other and that's really really optimal if you actually want to iterate over them and set all the more changes that won't read all of them or whatever it is that you want to do with them because they're likely going to well they are all going to be on the same cache line in that sense I know I said beat you know I'm already talking about cache lines and stuff we're gonna get into this in the future but basically you want to try if it's at all possible try and allocate the main line like this the only problem with this is that if it comes time to actually resize the vector it needs to copy all that data and if you happen to have something like a vector of strings and you're going to be resizing that vector often and it does need to reallocate and recopy everything that could potentially be a very slow operation whereas with pointers the actual memory stays intact because you're just holding pointers to that memory right so the actual memory stays intact but then when it comes time to resize it just copies those integers which are the memory addresses to the actual data and the data is still stored just in various places in memory so it is it is a bit of a hard decision and I don't really want to get into it too much now but that should just give you kind of the gist of this try and keep the muscle objects if if possible pointers are kind of always as with stack allocation heap allocation pointers are always kind of your last resort if you really really need need to actually do it that way so now that I bought this how do I add stuff to it well it's very simple you just type in vertices don't push back and other languages is called a door and then C++ the same operation is called push back and then you basically push back at that text so in this case that I have a constructor but I could just use and initialize a list like this to specify my x y&z so I'll say 1 2 3 and then I'll push another one back and we'll write 4 5 6 ok pretty basic stuff now let's iterate through all these and print them so in an array we don't know in it oh I should say in the C style array we don't actually know the size of the array but in this case of course since vector as a full class and everything we actually do know the size and we can ask it so let's write a for loop and we'll ride eyes less than vertices dot size that's the function that we used to retrieving the size and then I'll just say sta C out vertices and then we can use the index operator to access in Java we have to use get because Java reports us to have operator overloading but it was very much like c-sharp has overloaded the index operator so that we can actually just type it in like that as if it was just any array which is which is nice so if we hit a five-round run our code you can see that we get 1 2 3 4 5 6 which is perfect we can also use range based for loops with this so instead of writing all this code we could rewrite this for loop like this which is going to look much simpler we'll just say for vertex V then column them the vector which is vertices we can just print V like this and if we hit at five you can see that we get the exact same result pretty twice now in this specific example because I've written vertex like this this is actually going to be copying each vertex into the scope of this for loop we don't want to do that we want to avoid copying wherever possible so if we just stick a simple ampersand over here like this or maybe even marketers Const it doesn't really matter as long as you've got the ampersand here to make it a reference it's not going to copy the data if we run this we will get the same result however we're not just needlessly copying vertices finally if we want to clear the list of vertices we just type in vertices clear that will set the array size back to zero we can also remove vertices individually just by doing the vertices dot arrays and then with this now now I just I love C++ because of this look at look at this to someone who's new to say boss boss looking at this actual function signature it's like what is going on and even me right now reading this after so many years it's like what's up I know this is why a lot of people hate it but what's not very beginner friendly but if we if we read this it does make sense arrays returns a vector iterator so we can kind of we're gonna kind of just ignore all that return type this is the erase function and over here you can see takes a constant iterative okay what that means is that we can't just right there raised to or something like that we actually have to take an iterator now if we want to specifically remove for example the second element which is an index one what we can actually do is take in the beginning of vertices by typing in vertices of begin and then just add one to it and then that will actually erase that second element so if we move this followed down here after the arrays to see what happens you can see in this case we do actually erase that second element and everything's great another thing that I'll mention is that when you are actually passing these vectors into into functions or into classes or whatever you really do want to make sure that you're passing them by reference okay if you're not going to be modifying it than by constants just like this because by doing that you're ensuring you're not copying that entire array into this function so make sure that when you do stuff like this you actually do pass it by reference like that okay very important stuff okay I think that's pretty much it for a basic overview of the vector class dynamic arrays in C++ and how you can use them in the next video we're going to really get in-depth and talk about optimization about how we can avoid reallocations how we can avoid copying and all that stuff and probably some other tips and tricks with vectors in general for people who already kind of get the general premise and want to actually know how they can optimize their code this way though the way that I've shown you over here with like pushback and just this kind of workflow that's probably what you'll see most of the time there's nothing really wrong with it vectors specifically aren't that slaughter usually but in some cases of course we do want to squeeze out just every bit of performance that we possibly can and that's what the next video is going to be about do you guys enjoyed the video don't forget to hit the like button you can also support me on patreon by going to patreon or conv watch the channel you'll be able to see videos early contribute to the planning of videos as well as another pretty cool rewards which you can check out on that side thank you guys for watching as always I'll see you next time goodbye [Music]

Channel: undefined

Views: 176,723

Rating: 4.9363337 out of 5

Keywords: thecherno, thechernoproject, cherno, c++, programming, gamedev, game development, learn c++, c++ tutorial, array, dynamic array, resizeable array, std::vector, vector

Id: PocJ5jXv8No

Length: 14min 13sec (853 seconds)

Published: Wed Sep 20 2017