How are vectors really made?

[ResidentBiscuit]

Ok so how I understand it, C++ does not allow for dynamic arrays. Yet a vector is exactly that. But, aren't vectors just some class that some individuals wrote, in C++? How did they accomplish something that the language supposedly doesnt allow?

And yes, feel free to get as technical as you want here. I'm just curious as to how it works

[ascii]

I'm sure that somewhere in the vector class there is just a dynamically allocated array. It works by resizing the array whenever there is a need too (i.e. calling push_back() when the array is full). It's designed to do this as infrequently as possible because it's an expensive operation, so it usually increases the size by 50% when it's full, though it's implementation defined. Because the elements are stored sequentially in an array, inserting or deleting an element is also expensive because lots of elements have to be moved backwards or forward to make room. The implementation is pretty similar for a deque.

A list, on the other hand, does not have a dynamically allocated array to store the elements. It most likely just knows where the first element is, and from there can figure out where everything else is (because each node contains a pointer to the next). This means, however that random access is slow because while with a vector in the implementation something like *ptr + 8 can be used to find the 8th element, in a list you have to traverse through the first seven elements to find the desired one. However, inserting and removing elements is easy because you have to change one pointer, and add a new one.

[Moschops]

Here's a very simple dynamicArray that takes care of its own size.

class dynamicArray {

  int* theData;
  int theSizeOfTheArray;
  int amountUsed;

  public:
  dynamicArray()
  {
     theData = new int[0];
     theSizeOfTheArray = 0;
     amountUsed = 0;
  };

    dynamicArray(int size)
  {
     theData = new int[size];
     theSizeOfTheArray = size;
     amountUsed = 0;
  }

  void addToEndOfArray(int valueToAdd)
  {
     if (++amountUsed > theSizeOfTheArray)
     {
         // increaseArraySize
         int* temp = theData;
         theData = new int[theSizeOfTheArray * 2];
         theSizeOfTheArray = theSizeOfTheArray * 2;
         delete [] temp;
      }

      theData[amountUsed] = valueToAdd;
   }

  ~dynamicArray()
   { delete[] theData;}
};

Swap out that int for a <T> and make the whole thing a template, and then add some extra functions, and bingo - you've got yourself a C++ vector.

C++ does not allow for dynamic arrays.

C++ does not allow arrays whose size is unknown at compilation to be created on the stack.