Quote:Original post by lordcorm

Quote:Original post by jyk

Quote:Vectors are not necessarily slow, but arrays are faster.

How/why/when are (raw) arrays faster?

How: Using a Vector, you need to make a method call (1 cpu instruction "call") each time you want to add something to your Vector.

If you are using operator[], it's no slower than a raw array (assuming normal implementation).

Quote:push_back(), also has some extra overhead stuff it does such as incrementing counters, reallocing a new spot *each* time you push_back(). Then it will add what you want to the array.

Yes, but that can't be considered to be slower than doing push_back on an array, because that operation doesn't even exist on arrays. Coding your own version is very likely to be slower than the std::vector implementation.

Quote:Doing "myarray[1] = MyValue" is one cpu instruction "mov".

Try doing that operation and then doing the same for a vector, using the same operator, and compile the code (with optimizations on, of course). Check the assembly code. I think you'll see that there aren't any differences. Note that if you are using Visual Studio, you'll first have to disable the Microsoft-specific extension that turns operator[] into function at(), which is slower.

Quote:When: Always.

There is only one instance where vector is slower than an array, and that is during initialization since vector always calls the constructors for allocated items while arrays don't. I have only ever seen that be a problem once, in an extremely specialized application.

To get over the pointer-to-allocated-memory issue... why is it so much worse than std::vector ? The above implementation proposed by lordcorm, while longer, is still quite simple:

class Text{public:  Text (int size) : blah(new int[size]) {}private:  int* blah; };

However, it leaks memory, because that memory you allocate is never deallocated. Then, you have Twisol's proposal, which does not leak as much, but still creates problems when using the assignment operator or copy constructor:

class Text{    private:        int* blah;    public:        Text(int size) : blah(new int[size]) {}        ~Text() { delete [] blah; }};

A correct implementation would be:

class text{    private:        int* blah;        int size;        Text();        void swap(Text &other)        {          std::swap(blah, other.blah);          std::swap(size, other.size);        }    public:        Text(int size) : blah(new int[size]), size(size) {}        Text(const Text & other) : blah(new int[other.size]), size(other.size)        {          std::copy(other.blah, other.blah + other.size, blah);        }        Text &operator=(const Text &other)        {          Text temp(other);          temp.swap(*this);          return *this;        }        ~Text() { delete [] blah; }}

This is longer and harder to get right (on the other hand, it works sanely, never leaks memory and is exception-safe). Besides, it's also not optimal (though it could be optimized with some additional work). By contrast, std::vector is also shorter to write, and you run less risks of leaking memory by not paying attention.

Quote:Original post by Lordcorm
How: Using a Vector, you need to make a method call (1 cpu instruction "call") each time you want to add something to your Vector. push_back(), also has some extra overhead stuff it does such as incrementing counters, reallocing a new spot *each* time you push_back(). Then it will add what you want to the array.

Doing "myarray[1] = MyValue" is one cpu instruction "mov".

When: Always.

Why: Same has How.

Oh, please, don't be silly. This is like saying "gliders fly very slowly, therefore we should use bikes". Sure, appending elements to a vector does involve some overhead, but since one cannot append elements to an array, the comparison is utterly useless. Yes, vectors do it slowly and arrays don't do it at all, now can we move on to more significant comparisons?

As far as assigning elements, vectors are designed to be as fast as arrays (though you might have to do some compiler configuration to enable this). Also, you can get a pointer to the vector's contents and access those using the pointer, achieving performance equivalent to any other pointer-to-buffer approach you could imagine while still getting the memory management benefits.

As a side note, push_back does not allocate memory every time. Actually, the number of allocations is logarithmic in the number of insertions: inserting a thousand elements in an array will only take 10 allocations (even fewer if you reserved a reasonable amount ahead of time).