Vectors Vs Array

[Paul McKenzie]

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

[KevinHall]

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.

[Paul McKenzie]

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

[KevinHall]

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

[Homestead]

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

[Kheun]

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.

[_uj]

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.

[Mza]

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:

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.

[Kheun]

Use vector::reserve().

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);

[Mza]

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?

[Graham]

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.

[galathaea]

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.

[Graham]

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

[galathaea]

Nor would the array!!

[Graham]

No argument there. Score another point for vector!