Good Idea to Reserve Memory for Vectors?

Say I had a program like the following:

Code:

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
        vector<string> words;
        vector<string>::iterator it;
        string temp;

        cout << "Enter a series of words separated by spaces and terminated with [Enter]:" << endl;

        do
        {
                cin >> temp;
                words.push_back(temp);
        }
        while (cin.get() != '\n');

        sort(words.begin(), words.end());
       
        cout << "\n\nYou entered (sorted): ";
        for (it = words.begin(); it != words.end(); it++)
        {
                cout << *it << " ";
        }

        cin.get();
        return 0;
}

---

and I knew that there was going to be at least ten words entered. Would it be better to call words.reserve() to reserve that space and eliminate the need to allocate more memory each time push_back() is called? I know it costs performance when the entire vector has to be copied to a new location, but if it is just allocating more memory (without copying) does it make a difference?

Since you are planning on such a small number of words, I wouldn't reserve any memory. Typically vector implementations preallocate an array to start with anyway, so even if you reserve it would make no difference.

if I know how many elements are going to be put in the vector, I often reserve space, especially if I know it's going to be a lot of elements.

Obviously I wouldn't bother with it if I only had 10 items, this was just an example program.

My question was more of whether or not it costs performance to allocate more memory if movement of the vector is unnecessary and, as a result, if it is wise to to reserve memory if you have a general idea, but don't know exactly, how much memory needs to be allocated.

I'm not aware of any implementation that actually is capable of reallocating in place. If you have to reallocate, it's going to be a performance hit, but it's not worse than reallocating anything else. You probably won't feel it unless the n in O(n) for linear copying is very large: on the order of thousands for really big, contained objects that eat memory.

Quote:

---

Originally Posted by LyTning94

My question was more of whether or not it costs performance to allocate more memory if movement of the vector is unnecessary and, as a result, if it is wise to to reserve memory if you have a general idea, but don't know exactly, how much memory needs to be allocated.

---

If you are using reserve as an optimisation rather than to avoid invalidation of iterators due to reallocation, then the general optimisation guideline applies: measure to be sure.

Quote:

---

Originally Posted by whiteflags

I'm not aware of any implementation that actually is capable of reallocating in place. If you have to reallocate, it's going to be a performance hit, but it's not worse than reallocating anything else. You probably won't feel it unless the n in O(n) for linear copying is very large: on the order of thousands for really big, contained objects that eat memory.

---

So...you're saying that if a vector had adjacent unallocated memory, and you pushed a value into the vector which exceeded its reserved size, it couldn't just allocate some of the adjacent memory for the new value, but instead has to reallocate memory for the entire thing and copy the vector?

Quote:

---

Originally Posted by LyTning94

So...you're saying that if a vector had adjacent unallocated memory, and you pushed a value into the vector which exceeded its reserved size, it couldn't just allocate some of the adjacent memory for the new value, but instead has to reallocate memory for the entire thing and copy the vector?

---

Yes, at least with the standard allocator used by a "typical" vector implementation.

Quote:

---

Originally Posted by laserlight

Yes, at least with the standard allocator used by a "typical" vector implementation.

---

Is it possible...to implement it otherwise?
How would the allocator know what is occupied memory and what isn't, out of the piece reserved?

Quote:

---

Originally Posted by manasij7479

Is it possible...to implement it otherwise?
How would the allocator know what is occupied memory and what isn't, out of the piece reserved?

---

Realloc, or simmilar OS specific functions could make it work. The problem is, the standard containers wouldn't know to call such a function, since it's not part of the allocator "interface".

It isn't possible to implement with a stateless allocator. Nevertheless, with a stateful allocator, it is possible. That is to say, if the allocator remembers if it has previously allocated memory, it can probably deduce that the container wants to reallocate. Care needs to be taken care of, but certainly it's possible.

Quote:

---

Originally Posted by manasij7479

Is it possible...to implement it otherwise?
How would the allocator know what is occupied memory and what isn't, out of the piece reserved?

---

Every operating system typically uses virtual memory and hence gives functions to manipulate said thing. Windows, for example, allows you to allocate and reserve and even query the status of virtual pages. This allows you to see if an adjacent page is used or not.

> I know it costs performance when the entire vector has to be copied to a new location,
> but if it is just allocating more memory (without copying) does it make a difference?
This smacks of premature optimisation disease.
Yes, there is likely a performance hit.

But the elephant in the room is still likely to be your file I/O. Modern processors execute millions of instructions in the time it takes a hard disk to do a sector seek (and there will be a lot of those in a large file). Plenty of time to relocate your data structure before anything else has a chance to notice.

It MIGHT be worth doing after you've finished the program and done some decent profiling with real data.
Before then - it's just a distraction from you getting it finished and working.