C++ vector

Started by
11 comments, last by Zahlman 18 years, 2 months ago
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?
______________________________Stranger things have happened...The Following Sentence is True. The Above Sentence is False.
Advertisement
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.
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.
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)?
______________________________Stranger things have happened...The Following Sentence is True. The Above Sentence is False.
vectors allocate memory when their constructor is called. At runtime.
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.
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; 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.
Thanks Doc! That was really illuminating.

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?
______________________________Stranger things have happened...The Following Sentence is True. The Above Sentence is False.
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).
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.

This topic is closed to new replies.

Advertisement