Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dynamic arrays vs STL vectors exact difference?

Tags:

c++

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?

like image 838
Rajesh Avatar asked Jun 25 '12 12:06

Rajesh


People also ask

What is the difference between dynamic array and vector?

Differences between a Vector and an ArrayA vector is a dynamic array, whose size can be increased, whereas THE array size can not be changed. Reserve space can be given for vector, whereas for arrays you cannot give reserved space. A vector is a class whereas an array is a datatype.

What is the main difference between an STL vector and a non STL array?

Vector is a sequential container to store elements and not index based. Array stores a fixed-size sequential collection of elements of the same type and it is index based.

Why would we use dynamically allocated arrays vs vectors?

Vector are implemented as dynamic arrays with list interface whereas arrays can be implemented as statically or dynamically with primitive data type interface. Size of arrays are fixed whereas the vectors are resizable i.e they can grow and shrink as vectors are allocated on heap memory.

What is the difference between arrays and vectors?

We can think of a vector as a list that has one dimension. It is a row of data. An array is a list that is arranged in multiple dimensions. A two-dimensional array is a vector of vectors that are all of the same length.


2 Answers

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

like image 70
sbi Avatar answered Nov 15 '22 23:11

sbi


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.

like image 22
Jerry Coffin Avatar answered Nov 15 '22 21:11

Jerry Coffin