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".