How does std::vector destruct its objects?

Question

I'm trying to implement my own std::vector for sake of practice. Current source code:http://pastebin.com/bE4kjzcb

---

Here is an outline of my class:

1. Array() allocate some memory using malloc()
2. push_back(const T &t) add one element, call realloc() if necessary.
3. ~Array() call free() to release memory.

The major issue with this model is, free() recycles the memory, but it doesn't call T's destructor(when T is a class rather than standard data type).

This could cause severe resource leak when elements inside vectors are objects. My solution to this problem is, call ~T() EXPLICITLY before I free() the memory.

The reason I'm using malloc() is, I'm trying to utilize realloc(). If I use new and delete, memory usage will peak when reallocing. (The moment when both the new buffer and old buffer are present.)

Q: Is that a bad design? how does std::vector resolve this problem? Is there other flaws in my vector class?

PS:Let's not talk about multithread performances of malloc() now.

Answer 1

At the limit it is possible to use new [] if the default constructor is reserved for just allocated objects and if the /move/copy constructors/assignment operators and destructor of T propagate the information just allocated or user object. The solution in std::vector and its default allocator is nevertheless a far better design.

The construction

buffer = new T[capacity];

instead of

buffer = (T*)malloc(capacity * sizeof(T));

and

delete [] buffer;

instead of

free(buffer);

will automatically call the destructor of each object as on the example

class A {
public:
  ~A() { std::cout << "ok" << std::endl; }
};

int main() {
  A* a = new A[3];
  delete [] a;
  return 0;
}

this code outputs 3 "ok". Then A should contain additional fields and a non default constructor to differentiate allocation from user construction.

Answer 2

Calling ~T() is exactly how std::vector handles the problem.

You do however have a couple of problems:

Firstly, push_back needs to use placement new to copy-construct the value into the vector. You can't just use assignment.

Secondly, you can't call realloc - if the object have internal pointers, they are going to end up pointing outside them selves. You must call malloc again, then use placement new to copy-construct the values, then explictly delete all the old values, then call free to release the old value.

(Actually, std::vector doesn't call ~T() itself. Instead it calls the allocator which is responsible for ... allocating and deallocating memory. Internally though, that is how general purpose allocators do it.)

Answer 3

Here you have an example how it works more or less std::vector:

#ifndef __STDVECTOR__
#define __STDVECTOR__

#include <iostream>

using namespace std;

template <typename T>
    class StdVector{
        private:
            T *buffer;
            unsigned int capacity;
        public:
            //Constructor.
            StdVector(){
                capacity=0;
                buffer=new T[capacity];
            }
            //Copy constructor.
            StdVector(const StdVector &asv){
                int i;
                
                capacity=asv.getCapacity();
                buffer=new T[asv.getCapacity()];
                for (i=0; i<capacity; i++){
                    buffer[i]=asv[i];
                }
            }
            //Destructor.
            ~StdVector(){
                delete []buffer;
            }
            void push_back(T obj){
                StdVector oldSV(*this);
                int i;
                
                capacity++;
                delete []buffer;
                buffer=new T[capacity];
                for (i=0; i<oldSV.getCapacity(); i++){
                    buffer[i]=oldSV[i];
                }
                buffer[i]=obj;
            };
            T getBuffer() const{
                if (capacity==0){
                    throw exception();
                }
                return *buffer;
            };
            T &operator[](int index) const{
                if (index>=capacity){
                    //Out of range.
                    throw exception();
                }
                else{
                    return buffer[index];
                }
            }
            StdVector &operator=(const StdVector &obj){
                capacity=obj.getCapacity();
                delete []buffer;
                buffer=new T[capacity];
                buffer=obj.getBuffer();
                return *this;
            }
            unsigned int getCapacity() const{
                return capacity;
            };
    };
 
#endif

int main(){
    try{
        StdVector<int> test;
        StdVector<string> test2;
        unsigned int i;
        
        test.push_back(5);
        test.push_back(4);
        test.push_back(3);
        test.push_back(2);
        test.push_back(1);
        test.push_back(0);
        test.push_back(-1);
        test.push_back(-2);
        test.push_back(-3);
        test.push_back(-4);
        test.push_back(-5);
        for (i=0; i<test.getCapacity(); i++){
            cout << test[i] << endl;
        }
        test2.push_back("Hello");
        test2.push_back(" ");
        test2.push_back("World");
        test2.push_back(".");
        cout << "---------------" << endl;
        for (i=0; i<test2.getCapacity(); i++){
            cout << test2[i];
        }
        cout << endl;
    }
    catch(...){
        cout << "Exception." << endl;
    }
    return 0;
}

It prints:

5

4

3

2

1

0

-1

-2

-3

-4

-5

---------------

Hello World.

Maybe i have some error. If you know, say me pls.

Answer 4

push_back(const T &t) add one element, call realloc() if necessary.

It is ok as long as T is trivially copiable, for example, try to push back double linked lists and after reallcoation take one and iterate backwards - the app will probably crash. the solution is to overload the function twice, one for types which are trivialy copiable, and one for objects that are not.

As opposed to others, I'm quite sorry that the standard containers do not use realloc for objects which are trivially copiable. at least on Windows, realloc first checks if the current block can hold the new size and if so - it just updates the heap entry, causing huge performance boost (no copying).

call ~T() EXPLICITLY before I free() the memory.

Yes, this is how the standard allocator does it. assume size is the object count, you iterate each one and destruct it manually:

for (auto i=0U;i<size;i++){
   data[i].~T();
}

Interestingly, C++17 will add std::destruct which does exactly that.

Bonus: Using new[] and delete[] will not help here. usually, dynamic arrays saves more space than what they need to achieve capacity ,the extra space is not filled with live objects, only junk.

new[] will fill the entire memory with objects. capacity cannot be implemented this way. the array will move/copy the entire objects whenever someone pushes back new elements. so after 1000 push_back's, there will be 1000 reallocations. we want amortized time of O(log (n)).

even the standard allocator will call new(size_t) or malloc and not new[]

Answer 5

Rather than calling to malloc and free, prefer to use new and delete. Calling to delete will ensure that the instance dtor is called. =)