Sign in to follow this  

C++ vector

This topic is 4334 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If you had a program, lets say a text-based RPG, that depended on the user to determine the length of a vector of Player objects, you would probably do something like this:
vector<Player> players;

string s;
while (cin>>s) {
   if (s == "player") {
      Player* p = new Player;   // make a new Player
      players.push_back(p);
   }
   // ...
}

But, you could also do it like this (at least I have long ago):
int i;
cout<<"Enter number of Players.\n";
cin>>i;
vector<Player> players(i);
//...initialize players in a for loop

In the first case, the memory for the vector is allocated as needed, but my question is, how is memory set aside in the second case?

Share this post


Link to post
Share on other sites
The first method would likely result in vector with more memory reserved, due to the way vectors resize as you push stuff onto them. The second would probably be a tighter fit to the number of objects you will end up needing. Not that it matters too much either eay in a text rpg. I'd go with method 2 for simplicity. Method 2 would probably result in a vector with size and capacity of 'i', while method 1 could end up with reserved memory over the number of players allocated.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
The first method would likely result in vector with more memory reserved, due to the way vectors resize as you push stuff onto them. The second would probably be a tighter fit to the number of objects you will end up needing. Not that it matters too much either eay in a text rpg. I'd go with method 2 for simplicity. Method 2 would probably result in a vector with size and capacity of 'i', while method 1 could end up with reserved memory over the number of players allocated.


Ditto.

Also, you are declaring a vector of non-pointers and pushing back a pointer. Wrong.

Share this post


Link to post
Share on other sites
Quote:
Also, you are declaring a vector of non-pointers and pushing back a pointer. Wrong.


Now, isn't this funny: That code was copy-pasted from an e-mail from Bjarne Stroustrup...

I really don't have any spectacular STL documents, which is why this problem makes my head hurt. When the program allocates memory for a variable, it has to know how much space to reserve for it on the stack, right? So how could the program allocate the right amount of space in the binary if it never knows the size of the vector? Or does the constructor called in case 2 dynamically allocate memory for (i) number of objects (putting the vector on the heap without using new)?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
And also they change their size as needed so they are more flexible than dynamic arrays. vectors internally use the new and delete operators, it's a class after all.

Share this post


Link to post
Share on other sites
To expand on what AP said. Vectors, and most dynamic containers or classes essentially hold pointers, maybe a cached size variable. But if you have a vector such as your example above

vector<Player> players;

and you do a

size_t so = sizeof(players);

You will get the same result for an empty players vector as you would with a players vector with 10000 players in it. The sizeof a class is fixed at compile time, and if you make a vector on the stack, thats the about of stack space that will be used.

As you push stuff onto it, or pop stuff off, the vector itself manipulates memory from the heap, and this memory is dependant on what you are storing, and how many you are storing.

When you do
vector<Player> players(i);

You are telling the constructor of the vector to initialize with a size of i, so it will allocate from the heap something like new Player[i]; The capacity and size of the vector will probably both be set to i by the time its done.

The first method creates an empty vector. I think its implementation defined as to the initial capacity of the vector, but as you push things on, the vector has to grow when it runs out of room, usually by 1.5 or 2x the size each time it grows(again implementation specific). Depending on how many players your loop pushes onto the vector, the vector will end up with the size() of that many players, but the capacity() of the vector could be much more, resulting in wasted memory. Again not a big deal for a text rpg, but important to understand. This is why most people will recommend that if you know up front how many items you will be added to a vector to go ahead and reserve() the space in the vector for it, so that the vector doesn't have to do any costly resizing during runtime.

Edit: an additional detail. Remember, the vector<Player> players(i); method of initialization sets the size of the vector to i, so when you go filling in the values you need to do so with players[] = ?, and not push_back(). With push_back you are adding to the end of the array. In this example the vector would be initialized with i player objects default constructor.

Since it appears you meant for it to be a vector<Player*> players(i); you might want to use the 2 parameter constructor to initialize the value of the elements to null, such as vector<Player*> players(i, NULL); to ensure that all the pointers are not some garbage values.

Although MSDN says that not including the 2nd parameter will default it to 0, at least for their vector<int> example, I'm not entirely sure if this is their implementation or part of the standard.

Share this post


Link to post
Share on other sites
Thanks Doc! That was really illuminating.

[quote]but as you push things on, the vector has to grow when it runs out of room, usually by 1.5 or 2x the size each time it grows(again implementation specific)[/qoute]

Why does pushing waste so much memory?

Share this post


Link to post
Share on other sites
It's a design decision for speed. If the vector only grew by 1 element each push, that would mean every time you push something on it, it would have to allocate a new buffer on the heap of currentsize+1, copy old data to new data, free old buffer. It resizes to currentsize * 2 when it needs to resize so that it quickly gets up to a size where it wont need to resize. Still, whenever possible use the constructor method that you've pasted or .reserve(size); if you have a good idea of the size you are going to need. Also note the difference between .reserve(size), and .resize(size).

Share this post


Link to post
Share on other sites
Quote:
Original post by Photonman
Why does pushing waste so much memory?


Because that makes push_back take amortized constant time. If it only grew by one each time, push_backing n elements would need to make n(n-1)/2 copies of elements. By doubling its capacity when it runs out, it only has to make n-1 copies, which is MUCH faster.

Note that it doesn't have more than 50% extra memory. Also remember that new[] will often actually allocate a memory block bigger than the one you asked for anyways. If you're still worried, reserve to the correct size beforehand or use the swap trick to drop the capacity down to just what is needed.

Quote:
Original post by DrEvil
Although MSDN says that not including the 2nd parameter will default it to 0, at least for their vector<int> example, I'm not entirely sure if this is their implementation or part of the standard.


The second parameter defaults to T(), a default-constructed temporary of type T, which is the null pointer if T is a pointer type.

Share this post


Link to post
Share on other sites
Quote:
Original post by me22
The second parameter defaults to T(), a default-constructed temporary of type T, which is the null pointer if T is a pointer type.


Yea, thats what it says, but is that some special case thing that vector uses? Since when do pointers or ints default construct to 0? Haven't heard of that before. I was under the impression that you pretty much have to initialize pointers/pod types or theres no telling what values they will have(especially in release builds).

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
Yea, thats what it says, but is that some special case thing that vector uses? Since when do pointers or ints default construct to 0?


Since way back in C++ history :) However, primitive variables aren't necessarily constructed *at all*; it's just that they will be default constructed to 0 if that is requested. Behold:


int a; // a is anything that happened to be lying around in memory
int b = 0; // b is initialized to 0
int c = int(); // c is also initialized to 0 by copying the default-constructed int
int d(); // does NOT initialize to 0, or even declare an int d - but instead
// declares a function named d that takes no arguments and returns int. Yes,
// even when this appears inside some other function.

Share this post


Link to post
Share on other sites

This topic is 4334 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this