Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

BcS

arrays vs. vector

This topic is 5477 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. I''m finally dipping my toe into C++ and am wondering about arrays and vectors (std::vector). From what I''ve read, vectors can do anything an array can, plus more. So, I''m curious, are arrays necessary? Are there times where it makes sense to use arrays instead of vectors? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Yes.
If you want arrays of a fixed size, vectors is kind of overkill, for instance. Allso, arrays can sometimes be simpler to optimize, especially for the basic types, where you dont need to call stuff like assignment-operators and copy-ctors, that vector does.
For allmost all normal usage though, std::vector will suffice with flying colors.

Share this post


Link to post
Share on other sites
Like this, arrays only contains the actual data (and sometimes a size variable so that the delete operator know how much to delete. std::vectors are more or less built like a linked list, so that needs at least one pointer per element, also looping through a linked list is slower than just increase a pointer like in arrays.

With huge sized arrays, it might do some difference in realtime apps

----------------------------------------------
Petter Nordlander

"There are only 10 kinds of people in the world. The who understand binary and those who don''t"

Share this post


Link to post
Share on other sites
quote:
Original post by PhiberOptic
Like this, arrays only contains the actual data (and sometimes a size variable so that the delete operator know how much to delete. std::vectors are more or less built like a linked list, so that needs at least one pointer per element, also looping through a linked list is slower than just increase a pointer like in arrays.



Vectors are NOT built like linked lists, they are guaranteed to be contiguous in memory (like real arrays), so accessing an element is constant-time (not linear-time like with a linked list).

Since vectors use contiguous blocks of memory, they allocate extra space at the end of the block. If they didn''t take extra space, then the vector would have to reallocate everything every time you added an element - as it is, vectors only have to reallocate every once in a while.

Share this post


Link to post
Share on other sites
Indeed. Vectors only have some extra space at the end of their internal array, and an 32-bit integer telling it''s size (I think vector::size() is guaranteed to be O(1)). That''s neglible overhead. You should use vectors almost always, unless you really know what you''re doing and realize a situation where an array could gain you in efficiency.

Statically allocated arrays are a lot faster to create and delete, though.
int x[10];
In certain cases using them is almost compulsory as the speed drop of replacing that with a vector would be too significant.

Share this post


Link to post
Share on other sites
yes, you best use a vector, also because it will always free the memory, and you don''t have to worry about a delete that could be skipped by an exception or so.

btw. how much is that extra space allocated? is it relative to the size of the vector, or is it static. I know it''s not static, but if it''s relative, and you have a 1mb mem block, then there could be a lot of extra memory allocated that you''ll never use

My Site

Share this post


Link to post
Share on other sites
quote:
Original post by quasar3d
btw. how much is that extra space allocated? is it relative to the size of the vector, or is it static. I know it's not static, but if it's relative, and you have a 1mb mem block, then there could be a lot of extra memory allocated that you'll never use
It's usually (always?) relative, like 1.5 times the size of the vector when it needs to grow. Notice that at best you could end up with no extra space at all, if you fill the vector up to it's capacity. 1.5 is worst case. Vector allocates this extra space because you could use it. But if you know you won't, then you can use vector::reserve() to reserve the specific amount of memory you need. It's not guaranteed to reserve exactly the amount you specify though, but it's still better than relying on automatic growth.

[edited by - civguy on September 23, 2003 6:56:46 AM]

Share this post


Link to post
Share on other sites
You can reserve memory space at creation of a vector.
So if you knew for the most part you would only need a 1000 things in the vector you could create the vector myvector(1000);
And the vector should not grow until you added the 1001 thing then the vector will go out allocate twice the memory it had before it had to grow. So vector grows to 2000. at 2001 added it grows to 4000, etc.

Lord Bart

Share this post


Link to post
Share on other sites
quote:
Original post by Lord Bart
You can reserve memory space at creation of a vector.
So if you knew for the most part you would only need a 1000 things in the vector you could create the vector myvector(1000);
And the vector should not grow until you added the 1001 thing then the vector will go out allocate twice the memory it had before it had to grow. So vector grows to 2000. at 2001 added it grows to 4000, etc.

Lord Bart


I don''t think this is true, or I don''t understand you correctly.

according to this program:


#include <iostream>
#include <vector>

int main()
{
std::vector<int> v(10);
v.push_back(10);
v.push_back(20);
for(int i = 0;i < v.size();i++)
std::cout << v[i] << std::endl;
return 0;
}


the constructor doesn''t allocate memory for 10 future entries, it just fills the vector with 10 entries, and if you push_back after that, you just push the 11th (or 10th in 0 based count) entry

so there are always extra bytes allocated with a vector? if so, I don''t think it''s a good idea to use a vector for static memory blocks with a fixed size? I don''t want to use new/delete because it''s so clumpsy to make it exception safe, but if vector always allocates huge amounts of extra mem, I think i''ll better write my own static array class.

My Site

Share this post


Link to post
Share on other sites
Thanks to everyone for their replies. I think I''m gonna stick to (and learn a bit more about) vectors. Thanks again.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!