Vectors Vs Array

I have a question. Which of these methods involves the least overhead for a program:

Creating and using a dynamic array (there is no way to ever know the size of this array until program is complete).

using a vector with a reserve big enough (say 100), even if the odds are the entire reserve will almost never be used.

using a static array[100], even if the odds are the entire array will almost never be used.

I may not be able to use the dynamic array idea anyway, since I know I will have to pass the array (a pointer won't do) at least once, and that is not possible, correct?

I guess I will mostly have to choose between the last 2 options (the static array or the vector). I am more comfortable with arrays, but I understand vectors well enough to use them effectively. I can set a pointer to any value in the array by:

ptr = &v[n], where any is any index number

correct?

Thanks for any help or thoughts you may have.

I would suggest using the 'vector' since it provides its own memory management and thus, you do not have to deal with allocation, reallocation and deletion.

To answer your question...the standard guarantees the following:

Code:

---

&vector[ValidIndex] == &vector[0] + ValidIndex

---

Thanks Andreas!

Since you bring up memory mangement, is there any type of object in C++ that absolutely MUST be deallocated before the program terminates, or will termination release ALL held memory?

The program I am writing right now will have to work on a server, and quite frankly, I am not overly concerned about memory leaks during the run of the program (one instance takes millisecs to run, and works on my penny-ante home machine), but the program may run thousands of times a day on the server, and I am just curious if there can be any memory leaks on windows that would only be fixed by restarting the machine.

Thanks again,

Well...usually the operating system will cleanup the memory etc. if the application terminates. However, this is not a requirement and thus, I would not rely on this. In other words...everything that you have allocated dynamically MUST be released by you... ;)

Furthermore, I usually consider memory leaks as a bad programming style. By using special classes like the container classes from the STL in combination with generic programming idioms (such as RAII - Resource Acquisition Is Initialization), you can reduce the possibilities for memory leaks etc. by a high percentage...

Andreas, you've been very helpful, and I have one more question. Is there anywhere I could go online that would list objects that are subject to memory leaks, or discuss this problem in a non-Visual way? I realize you said anything allocated dynamically MUST be released, and while I was thinking about that statement, I realized I don't have a good handle on what constitutes dynamic allocation. I have read that anything allocated with new (uses the heap?) should be specifically deleted, but I don't do that. I use a lot of pointers, but in no case are they the sole owner of the data. However, the data is usually owned by an array (static). I do not make any special provisions for these, since I consider then basic objects. Since all the pointers and arrays and class objects have scope from the beginning to the end of the program, I have not been deleting them specifically. Anyway, you get my point, I'm not sure what "allocating an object dynamically covers". I tried checking the MSDN library for clues on windows behavior, but all of the info I could find was about handling MFC objects. Anyway, you've been a great help already.

Thanks again,

Quote:

---

Originally posted by buster77
I'm not sure what "allocating an object dynamically covers".

---

Dynamic allocation is when you create an object using new (or new[] if it's an array). The basic principle is if you created it you also destroy it using delete (delete[]) otherwise you have a memory leak. There are certain 'smart' pointers which can assist you to some extent. One example is auto_ptr of the standard library. Another is CountedPtr here,

http://www.josuttis.com/libbook/index.html

The Boost library also has a set of smart pointers for this purpose.

Thanks _uj!

I did know about auto_ptr. I appreciate you taking the time to help me. I just wasn't sure if new and new[] were the only instances of dynamic allocation, or if certain structures had a "hidden" dynamic allocation.

Thanks again,

Quote:

---

Originally posted by buster77
Thanks _uj!

I did know about auto_ptr.

---

One thing you must make sure is that you do not create a vector of auto_ptr. Since vectors stores copies of objects, an auto_ptr's copy semantics are not compatible with vector.

Code:

---

#include <vector>
std::vector<auto_ptr> Vect;

---

Some compilers will even flag this as an error, while others will accept the code and have you introduce bugs in your program. Use the boost shared pointers if you need a vector of auto_ptr's.

Quote:

---

I just wasn't sure if new and new[] were the only instances of dynamic allocation,

---

You also have the malloc(), calloc(), realloc() functions from the C library that are available in a C++ program (although you should avoid using these functions unless you have no choice but to use them).

Quote:

---

or if certain structures had a "hidden" dynamic allocation.

---

Vector has a "hidden" allocation, so do most other classes (such as std::string). The difference in these hidden allocations is that they have "hidden" deallocations when instances of these classes are destroyed (i.e. the destructor is invoked for these instances). Therefore they are safe to use and will not introduce memory leaks. If they do leak memory, then that is a bug in the way the class is implemented. What will introduce memory leaks are poorly coded classes that allocate memory, but do not manage the memory correctly.

You also mentioned that you allocated with new[] but never deallocated. The problem with this type of coding is that the code may be copied or moved to another place in your program where the non-deallocation may make a major impact. For example, if you have a function that you presently just call at the beginning of your program that allocates memory, and you don't call it again, then you won't see an impact. Later, you adjust your code so that this same function is now called in a loop 100,000 times -- then you get in a lot of trouble.

Regards,

Paul McKenzie

Thanks, Paul!

I appreciate very much your comments, especially since they spell out a few pitfalls that I haven't had problems with yet, but might in the future.

Quote:

---

One thing you must make sure is that you do not create a vector of auto_ptr. Since vectors stores copies of objects, an auto_ptr's copy semantics are not compatible with vector.

---

I hadn't thought of this yet, but I could see me thinking it would be a cool thing to do, lol. Fortunately, at the moment, what I need (and use) most is a vector of class objects, and then pointers that point to a few of them, and in one case, when the program starts, I actually have pointers to all of the elements in one vector! But, fortunately, as I said above, these pointers are best accessed singly, given their usage, and so it hadn't occured to me to put them in a vector. Since I use the pointers in order to bypass some of the vector structure (allowing me to treat them as single instances), it would not improve functionality to have the pointers stored in a vector.

Quote:

---

You also mentioned that you allocated with new[] but never deallocated.

---

Actually, I apologize for this. I meant to say I do NOT allocate anything with new or new[]. I have not had to use the heap, and so prefer to avoid it.

I was happy to hear your thoughts on this matter. I have read a lot of the posts on this forum, and am very impressed with your command of the language.

Thanks again,

One of the things to be mindful about vector is that it's dog slow. It is safe, it is easy, but slow. It has a few extra conditionals as compared to making your own dynamically allocated array and they really bite you in the butt as your input size increases. I would say that it's basically a non-issue until you start pushing into the 1000's of inputs, of course depending on the data type and what not.

Quote:

---

Originally posted by LoveJones
One of the things to be mindful about vector is that it's dog slow. It is safe, it is easy, but slow.

---

Not true. A vector is just as fast, if not faster than a dynamic array. As a matter of fact, a vector is a dynamic array internally

Quote:

---

It has a few extra conditionals

---

What exactly are you talking about?

Quote:

---

as compared to making your own dynamically allocated array and they really bite you in the butt as your input size increases

---

Use the "reserve" member function.

Quote:

---

I would say that it's basically a non-issue until you start pushing into the 1000's of inputs, of course depending on the data type and what not.

---

And what is the difference between doing this with "new" and "delete" and doing this with a vector? With a dynamic array, you have to do the same thing as vector would need to do -- make room for the new element by pushing all the elements down one slot (which means calling new[] and delete[] again). and place the new element in the array. The difference between doing this yourself and the vector class is the reason why vector will be faster. Vector is coded so that it does this operation as efficiently as possible.

I would like you to follow up your claims with actual timing tests. You will see that doing all this memory management yourself will not beat doing this with vector. If it does, it is by such a small amount, it is insignificant. Also, do not compare debug versions -- only release versions of the code.

Regards,

Paul McKenzie

It's very hard to 'beat' the standard library implementation of any container with your own version. Any dynamic array must at some point reallocate memory to be able to grow, but that's what you wanted wasn't it. It's nothing you can get rid of or speed up by implementing it yourself.

Quote:

---

Originally posted by LoveJones
One of the things to be mindful about vector is that it's dog slow. It is safe, it is easy, but slow.

---

The OP can easily handle this by setting the Vector initial capacity to about the expected number of elements. The time for element additions will be equivalent to that of a static array below this amount. If the amount is exceeded the Vector reallocates BUT you don't have to bother!

I think a Vector is such a good replacement for a static array that you generally should do it (except maybe when implementing low-level algoritms). It has fast random access, it grows when it has to and all memory management is taken care of. Close to the perfect deal. :thumb:

I'm sorry guys, I've actually done research in this area. We compared a vector implementation of a stack to a dynamically allocated array and the array smoked the vector. We took a look into the STL and one conditional was making the difference (in the vector). The times were something like 1.5 for the array and 20+ for the vector given 100,000 inputs (inserts).

I've never liked the STL due to it being slow and I'm telling you first hand that I have seen the numbers. That of course does not mean that vector does not have it's own applications and it's own niches, but in my experience if you are looking to minimize overhead (in terms of coding not in memory) using your own dynamic array >> vector. I'd be happy to share the code with you all if I can find it on my Linux box.

Quote:

---

Originally posted by LoveJones
I'm sorry guys, I've actually done research in this area. We compared a vector implementation of a stack to a dynamically allocated array and the array smoked the vector. We took a look into the STL and one conditional was making the difference (in the vector). The times were something like 1.5 for the array and 20+ for the vector given 100,000 inputs (inserts).

---

No information as to what you mean by "inserts" or what you mean by "a conditional". I have never seen a degradation of speed as you suggested, unless you are comparing apples to bananas.

You say a "stack" implementation. As others suggested, did you use "reserve" to preallocate the memory up front for the vector?

Quote:

---

I've never liked the STL due to it being slow and I'm telling you first hand that I have seen the numbers.

---

I've also seen "the numbers", and again, I have never seen any degradation that you speak of, unless you coded the vector implementation of your code very poorly, or did not take advantage of the functions that make vector operations such as "push_back" speedy. Also, if you are using a stack, what is wrong with std::stack? Why didn't you use a std::deque? Maybe you used the wrong STL container for your purposes.

Quote:

---

That of course does not mean that vector does not have it's own applications and it's own niches,

---

It isn't a "niche" anymore, it is one of the standard containers.

Quote:

---

but in my experience if you are looking to minimize overhead (in terms of coding not in memory) using your own dynamic array >> vector.

---

Many professionals and C++ experts disagree wholeheartedly with this statement.

Quote:

---

I'd be happy to share the code with you all if I can find it on my Linux box.

---

Please do.

Regards,

Paul McKenzie

Quote:

---

Originally posted by LoveJones
I'm sorry guys, I've actually done research in this area. We compared a vector implementation of a stack to a dynamically allocated array and the array smoked the vector. We took a look into the STL and one conditional was making the difference (in the vector). The times were something like 1.5 for the array and 20+ for the vector given 100,000 inputs (inserts).

---

It's not clear what you mean with a dynamically allocated array. Is it a static array you allocate on the heap once using new, or is it your own implementation of a dynamic array (such as Vector)?

If you're comparing a static array with room for 100,000 elements with a dynamic array which starts out at say 100 elements and then grows to 100,000 then you're comparing apples with oranges. Lets say the dynamic array doubles its size in each reallocation. To grow from 100 to 100,000 elements then requires 10 reallocations. So the time you've measured is the time for 10 reallocations!

You should re-run your test with a Vector with an initial capacity of 100,000 elements. You should also clock say 100,000 random accesses to each data structure. This would be a fair comparision between a static array and a Vector.

Did you really expect to get the dynamic behaviour of a Vector for nothing? If so I can understand you're disappointed and call it "slow".

Sounds like one or more of the following:

a) poor implementation of the stack using a vector.

b) poor implementation of the vector class itself by the compiler's library.

c) timing debug build rather than a release build with optimizations turned on.

d) The dynamic array has been "hand-optimized" to take advantage that a stack is being implemented, while the vector implementation has not been optimized.

e) As _uj pointed out, comparing apples to oranges, making the test unfair. For example, start out with a stack that can only hold one element (it has been allocated with new[1], not new[100000] or something like that). Now, each time you push an element onto the stack, you call new[] again, along with delete[] to make room for the new element. Do this for 100,000 elements. Now time your tests against vector. Unfair? No it isn't if you did not call "reserve()" for the vector implementation. Conceivably, an "unreserved" vector may be doing all of these calls to the allocator, (although it isn't likely, it still is possible), so to be fair, your program should be making these same calls.

I have coded a small example that randomly accesses the array and vector that have 1,000,000 elements, and there is no difference between using a vector as opposed to a dynamically created array if the proper functions are used and a release version is timed. There are no "hand-optimizations", just raw accesses to the array and vector (the only optimization is calling the reserve() method of the vector class -- something any experienced C++ programmer would do if they know in advance that they are going to grow the vector dynamically by adding thousands of elements).

I will try to post it today or tomorrow, along with the timings.

Regards,

Paul McKenzie

Quote:

---

Originally posted by Paul McKenzie
One thing you must make sure is that you do not create a vector of auto_ptr. Since vectors stores copies of objects, an auto_ptr's copy semantics are not compatible with vector.

---

According to Scott Meyers, STL containers of auto-pointers are forbidden by the C++ standard.

Quote:

---

Originally posted by KevinHall
According to Scott Meyers, STL containers of auto-pointers are forbidden by the C++ standard.

---

Correct, but there are some buggy compilers that let you declare one anyway, and merrily let you shoot yourself in the foot when you run your app.

Regards,

Paul McKenzie

Quote:

---

Originally posted by Paul McKenzie
Correct, but there are some buggy compilers that let you declare one anyway, and merrily let you shoot yourself in the foot when you run your app.

---

Very true! I just wanted to let people know that it's not just a bad idea to use containers of auto_ptr's, but it is forbidden (despite non-compliant compilers). ;)

- Kevin

Quote:

---

Originally posted by KevinHall
Very true! I just wanted to let people know that it's not just a bad idea to use containers of auto_ptr's, but it is forbidden (despite non-compliant compilers). ;)

- Kevin

---

Why did you say it was forbidden ?
May I ask ?

Thanks,

-FionA

Frist of all, standard compliance compiler will not compile container of auto_ptr. On non-compliance compiler, it will be lead to problem like, element(s) are missing especially after sorting.

Quote:

---

Originally posted by Homestead
Why did you say it was forbidden ?
May I ask ?

---

The short answer is that auto_ptrs are forbidden as container elements because they don't work there :).

This has to do with how auto_ptrs are copied. When you copy an auto_ptr you do get a copy but the auto_ptr you copied from will change. So after the copy the two auto_ptrs still will be different. And this has to do with a basic requirement: Two auto_ptrs may not point to the same object.

I always used arrays but from what I see these vector are very useful. Therefor I started using them in my current project. I want to use these vectors in a situation where I have a fixed number of elements and need direct acces. I use the following code to declare/use them:

Code:

---

std::vector<int> myVector;

//and now n times
myVector.push_back(element);

---

But from what I read in this topic, this is not the fastest way. How can I make sure that this vector has the right size and does not have to grow all the time.

Use vector::reserve().

Code:

---

std::vector<int> myVector

// Ensure that capacity is big enough to avoid memory reallocation.
myVector.reserve(n);

//and now n times
myVector.push_back(element);

---

Code:

---

std::vector<int> myVector

// Ensure that capacity is big enough to avoid memory reallocation.
myVector.reserve(n);

//and now n times
myVector.push_back(element);

---

Great, this works fine :)

By the way, am I correct to assume that if I reserve n items and have yet only used n - k items that myVector.end() points to n - k and not to n?

Quote:

---

Originally posted by Mza
<snip>
By the way, am I correct to assume that if I reserve n items and have yet only used n - k items that myVector.end() points to n - k and not to n?

---

Yes. Well, actually, it will probably point to n - k + 1, since end iterators don't point to an element in the container, but a loop from begin() while != end() will return just the elements that you've added.

If you want to get exactly the same performance as a new'ed array, you should use resize with operator[] assignment. That is the conceptual equivalent that can be optimised by nearly all compilers to the exact same code as an array. Using push_back with a reserve still involves the ++ of the end of vector member each op. However, the latter is safer, one of the big advantages of vector. So if you know a section of vector usage is sized during translation, but you still want the dynamism and safety elsewhere, resize / [], might be appropriate.

Of course, if the class that's in the container doesn't have a default constructor, then resize() isn't going to be much use... ;)

Nor would the array!! :D

No argument there. Score another point for vector!

You can use resize() even if the class does not have
a default constructor.

Code:

---

v.resize(100,MyClass(1,0,"hello world"));

// or even better, if you know the size at creation time

vector<MyClass> v(100,MyClass(1,0,"hello world"));

---

of course, if the constructor is expensive and
you are just going to over-write the values anyway,
then reserve() and push_back() would still be faster.

Ah, yes, I'd forgotten that overload of resize (the curse of Symbian: you get rusty on STL because you're not allowed to use it). Still, as you say, unless that's what you really want (100 identical copies), reserve() and push_back() probably make more sense, from a readability point of view if nothing else.