Quote:Original post by Caminman
And when it comes to vectors, aren't they implemented like this anyway? I don't know this at all actually, but I could imagine that a vector is a dynamically allocated array with nice wrappers around it?

Coming from C you will not see the inherit advantage and how complex the issues really are in C++, if you only know C plus very little C++ its way beyond your perception. It is not simply just a wrapper that your average joe-blogs C++ programmer can write far from it.

In C++ you have the issues of exception safety, construction/destruction aswell as allocation/deallocation not only that constructors/destructors can be trivial or NON trivial this not only effects preformance it also means what you can and can not do. Different kind of C++ types the main distinction is a POD-type (Plain Old Data type) and NON-POD type this effects things like wheather or not you can use C-memory rountines such as memcpy/move which you should never directly use on NON-POD types most C++ user-defined types are NON-POD types and you should virtually never use realloc in anycase in C++. User-defined types are either bitwise copyable or do a member-wise copy (which is either compiler generated or user-defined) or have no copy semantics meaning its been disabled by the user/client explicitly.

These issues are next to non-existent in C, there is no concept of constructors/destructors explicitly in standard C, all user-defined type are copyable but its always a bitwise copy hence all C-memory routines such as memcpy/move, realloc are always valid, there is no exception-handling natively in C. A C programmer only needs realloc and memcpy/memove for a dynamic arrays and be content, its simply not the case in C++ unfortunately.

Another thing is C-style arrays via implicit invocation of operator new[]/delete[] solves 1/2 issues but now you have new issues to deal with only user-defined types that have default constructor only be used in this way, generally all elements are default constructed.

Say if you want to use user-defined types that have non default constructors or you have a default constructable type but you don't want elements to be default constructed rather initialized using a different constructor well guess what you can but its very low-level, non-typical code, and screaming maintance nightmares e.g.:

struct foo {   int j;   foo(int i): j(i) {}};#include <new>   // for placement new#include <cmath>int main() {   const size_t N = 30;   foo* f = static_cast<foo*>(::operator new(sizeof(foo) * N));	// allocates only   foo* itr = f;   for(; itr < (f + N); ++itr)	::new(itr) foo(std::rand()); // placement new, in-place constructs only   for(itr = f; itr < (f + N); ++itr)	itr->~foo(); // destroys only   ::operator delete(f); // deallocates only	}

I'm sure you would want to kill your self if you had to do this all the time. Guess what aswell i come back to one of the issues i described earlier, generally when you invoke placement new for NON-POD types you must explicitly invoke the destructor, offically not the case for POD types so the final loop code is redundant the compiler should be smart enough to compile it away to NOP, unoffically (as far as i'm aware as of this moment) its also not the case with NON-POD types that have trivial destructors! hence not only is the the final loop code redundant it costs you time. Now can you see how complicated it gets? i've only just scratched the surface.

Not only does std::vector take care of all that it also guareentees to certain extent a level of exception safety, to grow efficiently as can possiably done in standard C++, it wont grow naively by one element but around 1.5-2.0x it's capacity. in essence it works like a stack on a uninitialized contiguous block of memory, each time a push is made on the stack abit of that memory gets initialized (i.e. placement new is used for in-place copy construction of that element). This plus abit more, other optimizations you probably never heard of before all this and its as (in some cases more) efficent than using C-style arrays when compiled with optimizations on.

This is most definitely the reason why Fruny mentioned std::vector and not mention C-style dynamic array at all because as all good C++ programmers & gurus will keep telling everyone you should prefer std::vector over c-style arrays there is very rarely an excuss to use the latter over the former.

Quote:Original post by Caminman
how are vectors implemented? An increase of size in a vectors always requires a completely new array to be created and the old one copied to that? Again, if vectors use arrays at all.. :p

Implementation varies on different compilers but only slightly, essentially they all pretty much do the same thing, imagine in some predeterminate state of a vector:

key:

     ----------    |          | uninitialized element,     ----------     ----------    |  ~~~~~~  | initialized element     ----------

1. std::vector::size == 3, std::vector::capactiy == 5

     ----------  < ----- end of storage    |          |     ----------    |          |     ----------  < ----- finish    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------  < ----- start

2. call std::vector::push_back, std::vector::size == 4, std::vector::capactiy == 5

     ----------  < ----- end of storage    |          |     ----------  < ----- finish    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------  < ----- start

3. call std::vector::push_back, std::vector::size == 5, std::vector::capactiy == 8

     ----------  < ----- end of storage    |          |     ----------    |          |     ----------    |          |     ----------  < ----- finish    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------    |  ~~~~~~  |     ----------  < ----- start

In step 3 it will need to create a new block of uninitialized memory in this case around 1.5x its capacity but the number is imp defined and then copy the old block to the new one, if the type contained is a POD-type it might dispatch at compile time to use memcpy/move to do the copying.

Note that memory is obtained/released through the allocator type, all standard library containers are parameterized by allocator type so you can use custom memory models/schemes with it.

If elements stored in memory contiguously is insignificant but random access is then you could use std::deque as an alternative because std::deque is random accessable container, its not guaranteed to store elements in memeory contiguously but its more efficent at growing as it doesn't suffer from internal copying that may occur with std::vector when they do grow.

[Edited by - snk_kid on August 11, 2005 10:42:08 AM]

bah now Im totaly confused. My English isnt very well so could anyone please give me a conclusion in plain English without too much details.

do I need to use arrays or vectors, or both (and if so when do I need to use which one).

Thanks alot everybody for replaying by the way.

Greetings,
Rob

Ok simple version: use std::vector unless you have a good reason not to. (And usually if you have a reason not to you'll be switching to another standard container like std::list or std::deque instead of an array.)

Quote:Original post by Fruny
Arrays sizes must be defined at compile-time. All they have to go for them is that they are fast to create. Vectors are classes that encapsulate dynamic arrays (created with new). They have variable sizes and loads of extra functionality. They are slightly slower to create than fixed-size arrays, but just as fast, and more convenient, than dynamically-allocated arrays.

Unless you have a solid and well-reasoned reason not to, use a vector.

Wrong. You can resize arrays, but its some crazy pointer new delete crazy memory management stuff.

Quote:Original post by ScottC
Wrong. You can resize arrays, but its some crazy pointer new delete crazy memory management stuff.

Calling that resizing an array is like calling cloning a burn victim and throwing the original into a wood chipper a way of doing a skin graft.

Ok thanks alot everyone.
I'll only use vectors in the future (unless I might need arrays some time when I have more experience and know the exact difference).