Implementacja std::vector – code review

Prosiłbym o ocenę jakości kodu i ewentualne wytknięcie błędów, wycieków pamięci, UB, możliwych optymalizacji. =)

template <class T>
class List {
private:
    int length;
    int capacity;
    int log;
    T *buffer;

    void reserve(int capacity) {
        T *newBuffer = new T[capacity];
        memcpy(newBuffer, buffer, length*sizeof(T));
        delete[] buffer;
        buffer = newBuffer;
        this->capacity = capacity;
    }
public:
    List() {
        length = capacity = log = 0;
        buffer = nullptr;
    }
    List(const List<T> &list) {
        length = list.length;
        log = list.log;
        capacity = list.capacity;
        buffer = new T[capacity];
        memcpy(buffer, list.buffer, length*sizeof(T));
    }
    List(int capacity) {
        log = (int)(Math::ceil(Math::log2(capacity))+0.5)+1; //W ten sposób w najgorszym przypadku, czyli np. log2(4) = 2.001, zostanie zarezerwowane 2 razy więcej pamięci niż to potrzebne. (int)(ceil()+0.5) nie pozwala ceil() na zwrócenie wartości mniejszej niż oczekiwana, czyli gdy ceil(1.5) = 1.999, jest to zamieniane na 2.
        this->capacity = 0b1 << (log-1);
        buffer = new T[this->capacity];
        length = 0;
    }

    inline T &operator[](int index) {
        return buffer[index];
    }

    T *begin() { return buffer; }
    T *end() { return buffer + length; }
    T &front() { return buffer[0]; }
    T &back() { return buffer[length - 1]; }
    int size() {
        return length;
    }
    bool empty() {
        return length == 0;
    }
    void clear() {
        length = capacity = log = 0;
        delete[] buffer;
        buffer = nullptr;
    }
    int find(const T &element) {
        for(int i=0; i<length; i++) {
            if(buffer[i] == element)return i;
        }
        return -1;
    }
    void add(const T &element) {
        if(length == capacity)reserve(0b1 << log++);
        buffer[length++] = element;
    }
    void remove(int index) {
        if(index < 0)return; //Tutaj UB jest jak najbardziej wskazane - jak programista użyje, tak dostanie. Sprawdzanie  czy liczba jest ujemna ma jedynie umożliwić użycie List::remove(List::find(const T &))
        T *i = &buffer[index];
        memcpy(i, i+1, (--length-index)*sizeof(T));
        delete i;
    }

    ~List() {
        delete[] buffer;
    }
};

Co się stanie jak będę chciał sobie zarezerwować 2147483649 elementów w wektorze? Używaj size_t zamiast int. Dodatkowo masz UB w tej sytuacji:

{
  List list;
}

Lub w sytuacji:

{
  List list{10};
  list.clear();
}

Nie używaj memcpy do kopiowania tablicy elementów T. T może być typem złożonym mającym specjalnie zdefiniowany konstruktor kopiujący, który np. zadba o poprawne skopiowanie zasobów takich jak wskaźniki do innych elementów. Kopiowanie bit po bicie może spowodować, że np. dwa obiekty będą chciały zwolnić ten sam obszar pamięci.

Rafbeam napisał(a):

    void remove(int index) {
        if(index < 0)return; //Tutaj UB jest jak najbardziej wskazane - jak programista użyje, tak dostanie. Sprawdzanie  czy liczba jest ujemna ma jedynie umożliwić użycie List::remove(List::find(const T &))
        T *i = &buffer[index];
        memcpy(i, i+1, (--length-index)*sizeof(T));
        delete i;
    }

Ten delete próbuje zwolnić pamięć, której nie przydzielałeś.

No i tak jak przedmówcy wspomnieli, memcpy nie zawsze zda egzamin. Należałoby najpierw sprawdzić czy T można tak kopiować.

Stosując się do waszych zaleceń zmodyfikowałem kod:

template <class T>
class List {
public:
    int size;
    int capacity;
    T *buffer;

    void copy(T *dst, T *src, int size) {
        for(int i=0; i<size; i++) {
            dst[i] = src[i];
        }
    }
    void reserve(int capacity) {
        T *newBuffer = new T[capacity];
        copy(newBuffer, buffer, size);
        delete[] buffer;
        buffer = newBuffer;
        this->capacity = capacity;
    }
public:
    List() {
        size = 0;
        capacity = 1;
        buffer = new T[capacity];
    }
    List(const List<T> &list) {
        size = list.size;
        capacity = list.capacity;
        buffer = new T[capacity];
        copy(buffer, list.buffer, size);
    }

    inline List<T> &operator=(const List<T> &rhs) {
        size = rhs.size;
        capacity = rhs.capacity;
        delete[] buffer;
        buffer = new T[capacity];
        copy(buffer, rhs.buffer, size);
        return *this;
    }
    inline T operator[](int rhs) const {
        return buffer[rhs];
    }
    inline T &operator[](int rhs) {
        return buffer[rhs];
    }

    T *begin() { return buffer; }
    T *end() { return buffer + size; }
    T &front() { return buffer[0]; }
    T &back() { return buffer[size - 1]; }
    T *data() {
        return buffer;
    }
    int length() {
        return size;
    }
    void clear() {
        size = 0;
        capacity = 1;
        delete[] buffer;
        buffer = new T[capacity];
    }
    int find(const T &element) {
        for(int i=0; i<size; i++) {
            if(buffer[i] == element)return i;
        }
        return -1;
    }
    void add(const T &element) {
        if(size == capacity)reserve(2 * capacity);
        buffer[size++] = element;
    }
    void remove(int index) {
        if(index < 0)return;
        T *i = &buffer[index];
        copy(i, i+1, (--size-index));
        delete i;
    }

    ~List() {
        delete[] buffer;
    }
};

Nasunęło mi się kilka porad:

• Sama nazwa List jest trochę myląca bo sugeruję listę, lepszą nazwą może być Vector lub Array.
• Membery klasy List + copy i reserve powinny być prywatne.
• Metoda List::copy może być statyczna gdyż nie zawiera odwołań do this.
• W metodzie List::reserve wywołanie copy(...) może się nie powieść - np. T::operator= może rzucić wyjątkiem a wtedy masz wyciek pamięci. Jest to tematyka nazywana exception safety, tutaj masz dobry punkt startowy do poczytania: https://en.wikipedia.org/wiki/Exception_safety
• Inna sprawa z metodą List::reserve jest tworzenie tablicy newBuffer. Taki sposób czyli T *newBuffer = new T[capacity] spowoduje stworzenie i zainicjowanie wszystkich obiektów w tej tablicy. A chcesz tylko zaalokować pamięć ale nie tworzyć żadnych obiektów. Chociaż ta porada spowoduje zmiany nie tylko w List::reserve ale również List::add i List::remove. I wymagać będzie czegoś takiego jak placement new.
• W konstruktorze klasy List skorzystaj z listy inicjalizacyjnej. W konstruktorze kopiującym również. Dodatkowo w konstruktorze kopiującym i operatorze przypisania część kodu jest łudząco podobna to List::reserve()...
• W metodzie inline T operator[](int rhs) const możesz zwrócić const T& zamiast kopii.
• Metoda length powinna być const.
• Sprawą dyskusyjną jest czy w metodzie List::clear należy skasować pamięć i ustawić capacity na 1. W praktyce rzadko kiedy chcemy zmniejszać zaalokowaną pamięć w takiej strukturze. A jeśli już to np. std::vector posiada specjalną metodę do tego shrink_to_fit().
• Metodę List::find można wyciągnąć poza klasę List ponieważ taki algorytm może (i powinien) operować na iteratorach. Podobnie jak std::find. I w przypadku nieznalezienia elementu zwróć List::end() zamiast -1. Wtedy Twój find może być używany do innych typów kontenerów lub tablic.
• Metoda List::remove nie zadziała. Problem - zaalokowałeś tablicę i tylko całą tablicę możesz usunąć a nie konkretne jej elementy.