Dynamic arrays vs STL vectors exact difference?

Question

What is the exact difference between dynamic arrays and vectors. It was an interview question to me.

1. I said both have sequential memory.

2. Vectors can be grown in size at any point in the code. He then said even dynamic arrays can be grown in size after creating.

3. I said vectors are error free since it is in the standard library. He said he will provide as .so file of dynamic arrays which is error free and has all the qualities on par with STL.

I am confused and didn't answer the exact difference. When I searched on Internet, I had seen the above statements only.

Can someone please explain me the exact difference? And what was the interviewer expecting from me?

Answer 1

He said he will provide as .so file of dynamic arrays which is error free and has all the qualities on par with STL.

If his dynamic array class does the same as std::vector (that is: it implements RAII to clean up after itself, can grow and shrink and whatever else std::vector does), then there's only one major advantage std::vector has over his dynamic array class:

std::vector is standardized and everybody knows it. If I see a std::vector in some piece of code, I know exactly what it does and how it is supposed to be used. If, however, I see a my::dynamic_array, I do not know that at all. I would need to have to look at its documentation or even — gasp! — implementation to find out whether my_dynamic_array::resize() does the same as std::vector::resize().

Answer 2

A great deal here depends on what he means by a "dynamic array". Most people mean something where the memory is allocated with array-new and freed with array-delete. If that's the intent here, then having qualities on a par with std::vector simply isn't possible.

The reason is fairly simple: std::vector routinely allocates a chunk of memory larger than necessary to hold the number of elements currently being stored. It then constructs objects in that memory as needed to expand. With array-new, however, you have no choice -- you're allocating an array of objects, so if you allocate space for (say) 100 objects, you end up with 100 objects being created in that space (immediately). It simply has no provision for having a buffer some part of which contains real objects, and another part of which is just plain memory, containing nothing.

I suppose if yo want to stretch a point, it's possible to imitate std::vector and still allocate the space with array-new. To do it, you just have to allocate an array of char, and then use placement new to create objects in that raw memory space. This allows pretty much the same things as std::vector, because it is nearly the same thing as std::vector. We're still missing a (potential) level of indirection though -- std::vector actually allocates memory via an Allocator object so you can change exactly how it allocates its raw memory (by default it uses std::allocator<T>, which uses operator new, but if you wanted to, you could actually write an allocator that would use new char[size], though I can't quite imagine why you would).

You could, of course, write your dynamic array to use an allocator object as well. At that point, for all practical purposes you've just reinvented std::vector under a (presumably) new name. In that case, @sbi is still right: the mere fact that it's not standardized means it's still missing one of the chief qualities of std:::vector -- the quality of being standardized and already known by everybody who knows C++. Even without that, though, we have to stretch the phrase "dynamic array" to (and I'd posit, beyond) the breaking point to get the same qualities as std::vector, even if we ignore standardization.

Answer 3

I expect they wanted you to talk about the traps of forgetting to delete the dynamic array with operator delete[] and then got confused themselves when they tried to help you along; it doesn't make much sense to implement a dynamic array as a plain class since it bakes in the element type.

Answer 4

The array memory allocated for vectors is released when the vector goes out of scope, in case the vector is declared on the stack (the backing array will be on the heap).

void foo() {
  vector<int> v;

  // ... method body

  // backing array will be freed here
}

Answer 5

It says here: "Internally, vectors use a dynamically allocated array to store their elements." Underlying concept of vectors is dynamically allocated array.

http://www.cplusplus.com/reference/vector/vector/

Answer 6

Maybe it's that dynamic array you would go through the copy process to a new dynamic array whenever you want to resize, but you are able to control when it does that depending on your knowledge of the data going into the array.

Whereas a vector uses the same process, but a vector does not know if it will grow or not later, so it probably allocates extra storage for possible growth in size, therefore it COULD possibly consume more memory space than intended to manage itself compared to dynamic arrays.

So, I'd say the difference is to use a vector when managing it's size is not a big deal, where you would use a dynamic array when you would rather do the resizing yourself.

Answer 7

1. Arrays have to be deallocated explicitly if defined dynamically whereas vectors are automatically de-allocated from heap memory.

2. Size of array cannot be determined if dynamically allocated whereas Size of the vector can be determined in O(1) time.

3.When arrays are passed to a function, a separate parameter for size is also passed whereas in case of passing a vector to a function, there is no such need as vector maintains variables which keeps track of size of container at all times.

4.When we allocate array dynamically then after size is initialized we cannot change the size whereasin vector we can do it.