Implementacja wektora w modern C++ - co dodać, co zmienić?

1

Piszę sobie dla ćwiczeń implementację wektora z zastosowaniem feature'ów z nowoczesnego c++ - move semantics, initializer lists etc.
Proszę o opinie, co byście tu zmienili, dodali, wywalili, żeby było to jeszcze bardziej zgodne z nowoczesnym C++.

template<typename T>
class Vector
{
    private:
        T* data;
        size_t size;
        size_t capacity;
    
    private:
        class Iterator
        {
            using iterator_tag = std::forward_iterator_tag;
            using difference_type = std::ptrdiff_t;
            using value_type = T;
            using pointer = T*;
            using reference = T&;

            private:
                pointer ptr;
            
            public:
                Iterator(pointer ptr)
                    :ptr(ptr){}
                
                reference operator*() { return *this->ptr; }
                pointer operator->() { return this->ptr; }

                Iterator& operator++() { this->ptr++; return *this;}
                Iterator operator++(int) { Iterator tmp = *this; this->ptr++; return tmp; }

                friend bool operator==(Iterator& a, Iterator& b) { return (a.ptr == b.ptr); }
                friend bool operator!=(Iterator& a, Iterator& b) { return (a.ptr != b.ptr); }
        };
    
    private:
        void re_alloc(size_t new_capacity)
        {
            T* new_data = new T[new_capacity];

            for(size_t i = 0; i < this->size; i++)
                new_data[i] = this->data[i];

            delete[] this->data;

            this->data = new_data;
        }

    public:
        Vector()
            :data(new T[0]), size(0), capacity(0){}
        
        Vector(size_t size)
            :data(new T[size]), size(0), capacity(size){}
        
        Vector(size_t size, const T& item)
            :data(new T[size]), size(size), capacity(size)
            {
                for(size_t i = 0; i < this->size; i++)
                    this->data[i] = item;
            }
        
        Vector(const Vector<T>& vec)
            :size(vec.size), capacity(vec.capacity)
        {
            this->data = new T[this->capacity];

            for(size_t i = 0; i < this->size; i++)
                this->data[i] = vec[i];
        }
        
        Vector(Vector<T>&& rhs)
            :size(rhs.size), capacity(rhs.capacity), data(rhs.data)
        {
            rhs.data = nullptr;
        }

        Vector(std::initializer_list<T> list)
            :size(0), capacity(list.size() * 2)
        {
            this->data = new T[this->capacity];

            for(auto& item : list)
                this->push_back(item);
        }

        Vector<T>& operator=(const Vector<T>& vec)
        {
            delete[] this->data;

            this->size = vec.size;
            this->capacity = vec.capacity;
            this->data = new T[this->capacity];

            for(size_t i = 0; i < this->size; i++)
                this->data[i] = vec[i];
            
            return *this;
        }
        
        ~Vector() { delete[] this->data; }
        
        T& operator[](size_t index) const { return this->data[index]; }

        void push_back(const T& item)
        {
            if(this->size == this->capacity)
            {
                size_t new_cap = this->capacity;

                if(this->capacity == 0)
                    new_cap = ++this->capacity; 
                else
                    new_cap *= 2;
                
                this->re_alloc(new_cap);
                this->capacity = new_cap;
            }

            this->data[this->size] = item; 
            this->size++;
        }

        void pop_back()
        {
            if(this->size > 0)
            {
                this->data[this->size - 1].~T();
                this->size--;
            }
        }

        void clear()
        {
            for(size_t i = 0; i < this->size; i++)
                this->data[i].~T();
            
            this->size = 0;
        }

        Iterator begin() { return Iterator(&this->data[0]); }
        Iterator end() { return Iterator(&this->data[this->size]); }
        
        size_t get_size() const { return this->size; }
        size_t get_capacity() const { return this->capacity; }
};


template<typename T>
std::ostream& operator<<(std::ostream& ostr, const Vector<T>& vec)
{
    for(size_t i = 0; i < vec.get_size(); i++)
        ostr << vec[i] << " ";
    
    ostr << std::endl;

    return ostr;
}
5

Rzuca się w oczy jeden problem: self assignment. Zobacz z memory sanitizerem co się stanie ;)
Możesz robić checka z thisem, ja osobiście wolę copy-swap idiom (ale to sprawa gustu i wydajności).
Move constructor i assignment powinny być noexcept. Tzn. nie muszą, ale dobrze, żeby były.
Fajnie jakby move poza nullptrem jednak też czyścił capacity i size.
W move'ach możesz wykorzystać std::exchange, dobrą praktyką jest też zerowanie wszystkiego, nie tylko danych.
Warto by było dorobić swap jako frienda.
Ten operator<< też możnaby zaprzyjaźnić wenwnątrz klasy, wtedy ułatwiasz kompilatorowi robotę.
Poza tym skoro wektor ma begin i end to możesz zrobić for (auto&& el:v) cout << //ciach albo wykorzystać ostream iterator, no ale to są detale.
EDIT: no i totalna drobnostka niby, ale bywa że robi różnicę: tam gdzie możesz używaj ++i zamiast i++. Generalnie kompilator to wyoptymalizuje w znakomitej większości przypadków, albo będzie to bez znaczenia. Ale są sytuacje gdzie jednak to takie proste nie będzie, wtedy nie zwracasz obiektu bez sensu.

EDIT2:
Dla non-default constructible klasy chyba Ci ten wektor nie zadziała. To niekoniecznie jest problem, ale dobrze być tego świadomym.
Zobacz dla:

struct SomeStruct
{
    SomeStruct()=delete;
    SomeStruct(int) {}
};

EDIT3: wyższą szkołą jazdy by było jeszcze wykorzystanie move semantics w reallocu jeżeli T jest noexcept_move_constructible ;)

EDIT4: sorry że tak dokładam ale zauwazyłem teraz, że to Ci się nie skompiluje
T& operator[](size_t index) const { return this->data[index]; }

@kq @vpiotr @_13th_Dragon @MarekR22 pozwoliłem sobie Was zawołać bo nie wiem czy się poza C++ ruszacie a myślę że możecie coś tu dołożyć :)

5

Nie będę powtarzać to co już napisano wyżej, ale na jedną rzecz zwrócę uwagę:
skoro wiesz jak się pisze operator ++ przyrostkowy i przedrostkowy to nieuzasadnione użycie inkrementacji przyrostkowej zakrawa bezmyślnością.
Nawet w tych przypadkach kiedy kompilator ma prawo zoptymalizować i zoptymalizuje to smrodek pozostaje: http://forum.4programmers.net/1101404

Jak się zabiera za takie rzeczy to się najpierw piszę testy.
Zdecydowanie brakuje operatorów +/-/+=/-= dla iteratora.
Brakuje resize tak a propos można użyć w push_back
Brakuje capacity i reserve
Przy pop warto zmniejszać rozmiar powiedzmy jeżeli potrzebna tylko 1/4
Takie rzeczy jak size() - nie powinieneś nadawać innych nazw niż standardowe w przeciwnym wypadku nie da się podmienić vector na Vector przez using i voila ...

0

Dzięki, pozmieniam i wrzucę jeszcze raz

0

@Eldorad O.: Zawsze możesz sobie na kod STLa rzucić okiem.

2

@lion137: Strasznie się czyta ten kod.

3

To ja na początek czytania STLa nie polecę. Tam jest kupa boilerplate’u, support dla alokatorów itd. Jasne, jak chcesz to zaimplementować w pełni - nie uciekniesz od tego. Ale skoro się uczysz, nie rzucałbym się na STLa od razu, tylko szedłbym etapami. Zrób dobrze case podstawowy. Potem rozszerz o coś (np. wsparcie dla typów bez defaultowego konstruktora), potestuj, potem znowu rozszerz itd. itd.
I testować polecam wcześnie, nauczysz się od razu jakiegobądź frameworka, czy to będzie boost, czy gtest, czy catch (cppunit nie polecam bo to staroć, ale nadal bywa używany).

2

Tak na pierwszy rzut oka brakuje mi przeładowań dla const referencji i iteratoró (i typów const_reference i const_iterator). Jeśli chodzi o nazwy podtypów, metod itd. to sugerowałbym nazwanie ich tak, aby to był drop-in replacement dla std::vector z domyślnym alokatorem. Tj, aby metody takie jak std::data, std::size działały, aby API klasy było identyczne, aby dało się jej użyć w std::priority_queue. Finalnie, zastanowiłbym się, czy dałoby się użyć malloc/realloc/free zamiast new[]/delete[].

Aha, no i fajnie gdyby było milion unit-testów aby pokazać, że wszystko gra.

Ale żeby nie było, że samo narzekanie: ogółem kod wygląda dobrze, zdaje się być sensownie napisany, ładne wcięcia itd.

0

@kq:

zdaje się być sensownie napisany, ładne wcięcia itd.

A dzięki dzięki :D

2

To ja dodam jedną totalnie durnowatą (ale jakże przyjemą) rzecz:
polecam zrobić Vector<T>& operator=(const Vector<T>& vec) & zamiast Vector<T>& operator=(const Vector<T>& vec). Od C++11 możesz wyspecyfikować czy chcesz żeby f-kcja działała tylko dla lvalue bądź rvalue. Efekt jest taki, że

Vektor<int> f() {return {1, 2,3,5}; }  
//i potem dalej
f() = inny_Vektor;

skończy się błędem kompilacji.
W starym C++ to robiło się zwracając stałą wartość, tutaj takie działanie psuje move semantics, ale dano za to możliwość takiego overloada.
EDIT: i styl muszę pochwalić także. ;)
Generalnie za rzadko chwalę na review, a to błąd ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1