How does a vector resize work?

[momof4]

I'm trying to recreate the standard vector class, but I'm having a hard time figuring out how the vector does its resize. How do I allocate more memory after I've already allocated some? I've tried just creating a new vector with double the capacity and deleting the old one, but I can't figure out how to copy over the data from the first one. There has got to be an easier way! help!

[jonnin]

you can use C and re-alloc (raw pointer tool) or in c++, you make the new memory first, copy the data to the new memory, then delete the old memory.

Note that this is expensive to do, so you want a smart algorithm that does this occasionally, not every time you add a new item to a block. Eg double its size every time you need more space (very excessive but an example).

you can copy in a loop, which is safe for objects etc. If its simple types like int, or c-structs, etc, memcpy can do it faster. Think about it. How would you make a copy of an array of integers? The STL has a copy algorithm (several, actually). https://www.cplusplus.com/reference/algorithm/copy/

[ne555]

vector::increase_capacity(){
   //allocate twice the memory
   value_type *aux = new value_type[2*this->capacity];

   //copy the values stored
   for (int K=0; K<this->size; ++K)
      aux[K] = this->data[K];

   //release the old array
   delete [] this->data;
   //point to the new location
   this->data = aux;

   this->capacity *= 2;
}

[momof4]

okay, here's what I have.

template <class T>
void Vector <T> :: resize (int capacity) throw (const char *)
{
   try
   {
       data = new T[capacity];
   }

   catch
   {
      throw "ERROR: unable to allocate buffer";
   }

   for (int i = 0; i < numItems; i++)
      T[i] = this->data[i];
   delete [] this->data;
   this->data = T;
   this->capacity = capacity;
}

I'm getting these errors:
vector.h:258:8: error: structured binding declaration cannot have type ‘T’
T[i] = this->data[i];
^~~
vector.h:258:8: note: type must be cv-qualified ‘auto’ or reference to cv-qualified ‘auto’
vector.h:258:10: error: redeclaration of ‘auto i’
T[i] = this->data[i];
^
vector.h:257:13: note: ‘int i’ previously declared here
for (int i = 0; i < numItems; i++)
^
vector.h:260:18: error: expected primary-expression before ‘;’ token
this->data = T;
^
vector.h: In instantiation of ‘void Vector<T>::resize(int) [with T = double]’:
vector.h:231:7: required from ‘void Vector<T>::push_back(const T&) [with T = double]’
vector.h:218:7: required from ‘Vector<T>::Vector(int) [with T = double]’
assignment01.cpp:107:37: required from here
vector.h:258:8: error: redeclaration of ‘auto i’
T[i] = this->data[i];
^~~
vector.h:257:13: note: ‘int i’ previously declared here
for (int i = 0; i < numItems; i++)
^
vector.h:258:24: error: use of ‘i’ before deduction of ‘auto’
T[i] = this->data[i];

[seeplus]

T is the type that the vector holds, not the vector. So you can't index onto say a double or int.


The problem is in the re-allocation. What you need to do is allocate some new memory, copy the contents of the old memory into the new, delete the old memory and set the pointer to the new.

See ne555's post above.

figuring out how the vector does its resize. 

Just look at the source code of std::vector and see how it's done there. The source of all of the STL is part of the C++ compiler install.

[jonnin]

this -> is a great tool when you need it. You can avoid it sometimes by having distinct names, and that also a tool worth using. Anyway, line 4 & 7 is critical to understanding where you were going wrong:

template <class T>
void Vector <T> :: resize (int capacity) throw (const char *)
{
   T * tmp;
   try
   {
       tmp = new T[capacity];
   }

   catch
   {
      throw "ERROR: unable to allocate buffer";
   }

   for (int i = 0; i < numItems; i++)
      tmp[i] = data[i];
   
   delete [] data;
   data = tmp;
   this->capacity = capacity;
}

[ne555]

just a small logic error that may be hard to detect:
resize() may allow you to shrink the vector, it is not guaranteed that new_size > old_size

for (int i = 0; i < numItems; i++)
   tmp[i] = data[i];

so you may be trying to access invalid elements there

> Just look at the source code of std::vector and see how it's done there.
here you are(comments added and fat removed)

void resize(size_type __new_size) {
  //¿shrink or enlarge?
  if (__new_size > size())
    _M_default_append(__new_size - size());
  else if (__new_size < size())
    _M_erase_at_end(this->_M_impl._M_start + __new_size);
}

void _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT {
  // note that there is no reallocation in the shrink case
  if (size_type __n = this->_M_impl._M_finish - __pos) {
    std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
    // just say that the vector ends earlier
    this->_M_impl._M_finish = __pos;
  }
}

template <typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_default_append(size_type __n) {
  if (__n != 0) {
    const size_type __size = size();
    size_type __navail =
        size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_finish);

    // too much memory requested, fail
    if (__size > max_size() || __navail > max_size() - __size)
      __builtin_unreachable();

    if (__navail >= __n) {
      // we have some extra space, use that
      this->_M_impl._M_finish = std::__uninitialized_default_n_a(
          this->_M_impl._M_finish, __n, _M_get_Tp_allocator());
    } else {
      // have to reallocate
      const size_type __len = _M_check_len(
          __n, "vector::_M_default_append"); // new size (duplicate length)
      pointer __new_start(this->_M_allocate(__len)); // aux = new[]
      pointer __destroy_from = pointer();
      __try {
        // default values for the new elements
        std::__uninitialized_default_n_a(__new_start + __size, __n,
                                         _M_get_Tp_allocator());
        __destroy_from = __new_start + __size;
        // move the values to the new location
        std::__uninitialized_move_if_noexcept_a(
            this->_M_impl._M_start, this->_M_impl._M_finish, __new_start,
            _M_get_Tp_allocator());
      }
      __catch(...) {
        // something failed, have to cleanup
        if (__destroy_from)
          std::_Destroy(__destroy_from, __destroy_from + __n,
                        _M_get_Tp_allocator());
        _M_deallocate(__new_start, __len);
        __throw_exception_again;
      }
      // delete [] this->data
      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                    _M_get_Tp_allocator());
      _M_deallocate(this->_M_impl._M_start,
                    this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
      // adjust pointers
      this->_M_impl._M_start = __new_start;
      this->_M_impl._M_finish = __new_start + __size + __n;
      this->_M_impl._M_end_of_storage = __new_start + __len;
    }
  }
}

[Ganado]

momof4, also note that throw specifiers are deprecated (and actually now removed). e.g.
void myfunc() throw (const char *)

https://en.cppreference.com/w/cpp/language/except_spec

[dhayden]

Just look at the source code of std::vector

The problem is that when std::vector<> grows, it does something that most people don't seem to realize. More accurately, it doesn't do something....

It doesn't create new items in the empty space. In other words, when std::vector decides to grow from 20 to 30 items, it doesn't construct 10 extra items. It just allocates space for them to be constructed later on. It also doesn't construct 20 empty items and then copy the existing ones to the new ones either. What is does, is allocate space for 30 items, and then move the existing 20 items to the new space. If you add a new item, it copy-constructs a new item in allocated space.

As ne555's code points out, it does some fancy memory management to ensure the minimum number of copy or move operations.

I'm not suggesting that momof4 should do the same thing, I'm just pointing out that vector<> is more complicated than most people seem to realize.