CODEWITHSUNDEEP
c++templates
Dov
Dov

Reputation: 8542

Implementing efficient initialization of C++ Template List classes

For writing a template list class, the equivalent of vector (purely as a design exercise) I am trying to find out what is done to be efficient.

If one writes:

v = new T[size];

then the compiler will call the constructor for T, right? T().

So instead in the class below:

v = (T*) new char[sizeof(T) * size]

This seems easy enough. However, in the destructor, how to delete just the ones that have been initialized? In the following class, only the first "used" elements are initialized.

Also, in the copy constructor, how to call the copy constructor for T for only the used elements efficiently?

If I initialized the expensive way, it works:

v = new T[size];
for (int i = 0; i < used; i++)
  v[i] = orig.v[i];

but that requires that v already be intiialized with T(). What is the better way?

Class is below:

#include <cstdint>

template<typename T>
class List {
private:
    uint32_t used;
    uint32_t capacity;
    T* v;
public:
    List(uint32_t cap) : used(0), capacity(cap), v((T*)new char[sizeof(T)*capacity]) {}
    ~List() {
        delete [] v; // no
    }
    List(const List& orig) : used(orig.used), capacity(orig.capacity), v((T*) new char[sizeof(T)*capacity]) {
        // now copy only the used ones
        for (int i = 0; i < used; i++)
            v[i] = orig.v[i]; // no, operator = will call destructor on v[i], but it is uninitialized
    }
};

Upvotes: 0

Views: 48

Answers (3)

Ananta Yudica
Ananta Yudica

Reputation: 11

For in the copy constructor you can try this code:

#include <cstring>

List(const List& orig) : used(orig.used), capacity(orig.capacity), v((T*) new char[sizeof(T) * capacity]) {
        // now copy only the used ones
        memcpy(v, orig.v, sizeof(T)*capacity);
    }

or

List(const List& orig) : used(orig.used), capacity(orig.capacity), v((T*) new char[sizeof(T) * capacity]) {
        // now copy only the used ones
        memcpy_s(v, capacity, orig.v, sizeof(T)*capacity);
    }

Upvotes: 0

aschepler
aschepler

Reputation: 72271

To be like std::vector, you need to use "placement new" and explicitly call destructors.

#include <new>

~List() {
    while (used) {
        --used;
        v[used]->~T();
    }
    delete[] reinterpret_cast<char*>(v);
}

List(const List& orig) : used(orig.used), capacity(orig.capacity),
    v(reinterpret_cast<T*>(new char[sizeof(T)*capacity])) {
    // now copy only the used ones
    for (int i = 0; i < used; i++)
        new(v+i) T(orig.v[i]);
}

Note the above copy constructor is not exception-safe. Try to make it so.

Upvotes: 1

cdhowie
cdhowie

Reputation: 168988

First, just use std::vector<T> instead of reimplementing this yourself.

What you're looking for here is placement new and explicit destructor calls. Where normally, each new should be paired with a delete, each placement new should be paired with an explicit destructor call.

To answer your specific questions:

However, in the destructor, how to delete just the ones that have been initialized?

Explicitly call their destructors, then delete[] the original char[] allocation correctly, which will (correctly) not automatically call any T destructors.

for (uint32_t i = 0; i < used; ++i) {
    v[i]->~T();
}

delete [] reinterpret_cast<char *>(v);

Also, in the copy constructor, how to call the copy constructor for T for only the used elements efficiently?

You need to placement-new here. Your line v[i] = orig.v[i]; causes undefined behavior because v[i] has not yet been constructed.

Placement-new the objects instead (which you should do to each v[i] before you use it):

new(reinterpret_cast<char *>(v + i)) T(orig.v[i]);

Upvotes: 0

Related Questions