Implementacja kontenera-wektor

Question

Witam !

Ostatnio pomyślałem sobie, że spróbuję napisać kontener-wektor. Niestety jestem początkujący i sprawia mi to dużo problemu :) Myślę, że moje rozwiązanie wektora jest bardzo słabe, dużo jeszcze w nim brakuje, poza tym brakuje mi pomysłów jak niektóre rzeczy rozwiązać, dlatego piszę do was z prośbą o pomoc :) To kod, który póki co napisałem:

#ifndef wektor_hpp
#define wektor_hpp

#include <iostream>

namespace amadi
{

template <typename T>
class wektor
{
private:
    T * tab;
    T * tabEnd;
    int tabSize;

    void resize(bool temp)
    {
        if (temp)
        {
            T * newTab = new T[tabSize+1];
            for (int i = 0; i < tabSize; i++)
                newTab[i] = tab[i];
            tabSize += temp;
            delete [] tab;
            tab = newTab;
        }
        else
        {
            T * newTab = new T[tabSize-1];
            for (int i = 0; i < tabSize-1; i++)
                newTab[i] = tab[i];
            tabSize -= 1;
            delete [] tab;
            tab = newTab;
        }
    }
public:
    wektor()
    {
        tabSize = 0;
        tab = new T [tabSize];
        tabEnd = tab;
    }
    wektor(int tabSize)
    {
        this -> tabSize = tabSize;
        tab = new T [tabSize];
        tabEnd = tab+tabSize-1;
    }
    ~wektor()
    {
        delete [] tab;
        tab = 0;
        tabEnd = 0;
    }
    void pushBack(T temp)
    {
        resize(1);
        tab[tabSize-1] = temp;
        tabEnd = tab+tabSize-1;
    }
    void popBack()
    {
        resize(0);
        tabEnd = tab+tabSize-1;
    }
    bool isEmpty() const
    {
        if(tabSize == 0)
            return true;
        else
            return false;
    }
    void clear()
    {
        delete [] tab;
        tabSize = 0;
        tab = new T[tabSize];
        tabEnd = tab;
    }
    int & operator[](int el)
    {
            return tab[el];
    }
    int getSize() const
    {
        return tabSize;
    }
    T getFirst() const
    {
        return *tab;
    }
    T getLast() const
    {
        return *tabEnd;
    }
};
}
#endif // wektor

Czy dałoby się zrobić to lepiej ? 

Które z wykonanych przeze mnie pomysłów jest na poziomie dopuszczalnym, a które nie do przyjęcia ?

Standardowy wektor posiada iterator, niestety nie mam żadnego pomysłu jak go wykonać i jakby miał on działać.

Zdaję sobie sprawę, że nie ma żadnej obsługi błędów, jednak nie wiem jakby miała ona wyglądać.

Z góry dziękuję za pomoc i pozdrawiam !

Answer 1

Jeżeli jesteś początkujący, to Twoje rozwiązanie jest całkiem niezłe. No ale mam dość sporo zastrzeżeń i uwag:

1. Chyba nie rozumiesz na czym polega działanie wektora. Twoje rozwiązanie jest powolne, gdyż przy każdej operacji push/pop usuwasz starą tablicę i alokujesz o jeden element większą/mniejszą. Wektor ma to do siebie, że alokuje więcej pamięci niż potrzebuje tego użytkownik, aby operacje push/pop nie były czasochłonne. Np. Twój wektor ma 9 elementów, ale pamięć którą zarezerwował starczy na 16. Dopiero później dokonuje realokacji (tworzy i inicjalizuje nową tablicę, zwalnia starą) i znowu rezerwuje więcej miejsca niż potrzbuje.

2. Radziłbym zapoznać Ci się z tym, czym tak naprawdę jest konterener w C++. Otóż jest to klasa, która spełnia tzw. wymagania kontenera: http://en.cppreference.com/w/cpp/concept/Container. Chyba żadna z funkcji składowych nie pasuje do tych wymagań. Nie ma podstawowych rzeczy: konstruktora kopiującego/przenoszącego, funkcji begin/end, swapa czy operatorów porównania.

3. Wektor jest także kontenerem sekwencyjnym. Proszę tu wymagania: http://en.cppreference.com/w/cpp/concept/SequenceContainer.

4. W standardowej bibliotece wektor spełnia jeszcze te wymagania dotyczące kontenerów: http://en.cppreference.com/w/cpp/concept/ReversibleContainer http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer.

5. Nazwę funkcji pushBack zmień na push_back. Twój kontener będzie mógł wówczas współpracować z obiektami klasy std::back_inserter_iterator: http://en.cppreference.com/w/cpp/iterator/back_insert_iterator

6. Kluczowe (jak dla mnie) są funkcje begin/end. Umożliwiają one wiele ciekawych rzeczy takie jak na przykład pętla foreach:

amadi::wektor<int> integers;
// ...
for(int& value : integers) {
  value += 10;
}

7. Iterator to może być zwykły wskaźnik. Jeżeli jednak chce Ci się budować jego klasę to pamiętaj o odpowiednich wymaganiach: http://en.cppreference.com/w/cpp/concept/RandomAccessIterator

8. Obsługi błędów nie potrzeba, chociaż mógłbyś zrobić np. funkcję at, która sprawdza czy podany indeks jest prawidłowy (nieujemny i niewykraczający poza granicę kontenera).

9. Co do implementacji to najlepiej użyć 3 wskaźników wskazujących na: początek kontenera, element za ostatnim elementem kontenera, element za ostatnim fragmentem zarezerwowanej przez wektor pamięci.

Pozdrawiam!

Comments

Cóż, trochę się załamałem, jednak postaram się powoli, ze zrozumieniem, dodawać do mojego kodu :)

---

Nie ma co się załamywać, najważniejsze że Twój kontener działa i nie ma żadnych błedów! Poza tym liczą się chęci! :) Jednak zanim zabierzesz się do samodzielnej implementacji, radzę Ci zobaczyć prace innych użytkowników. Mógłbyś np. zobaczyć jak std::vector jest zaimplementowany w Twoim kompilatorze. Pozdrawiam!

Answer 2

Tak, da się zrobić to lepiej.

Przede wszystkim u ciebie korzystanie z niego jest niewygodne, bo wymaga sprawdzania poza wektorem za każdym razem przy wywołaniu push_back czy czasami nie przekroczymy wielkości tablicy. Jesteś na dobrym tropie bo chociaż nie alokujesz nowej pamięci przy każdym dodawaniu/usuwaniu elementu.

Rzuć okiem na blog Adama Sawickiego, gdzie on tłumaczy rzeczy tego typu: http://www.asawicki.info/productions/artykuly/strukturyd_formatyp.php5#2_1

Comments

Dziękuję za odpowiedź :) Z artykułu z pewnością skorzystam :)

Answer 3

IMO ogólnie nie jest źle. Kilka uwag:

1. Staraj się nie używać w argumentach metod tych samych nazw, jak składowych jak ma to miejsce w konstruktorze. Wskaźnik this oczywiście ratuje sprawe, ale mimo wszystko jest mniej czytelne.
2. Zupełnie bezsensowny wskaźnik na ostatni element. Za każdym, kiedy w konterze coś się zmienia, musisz zadbać też, żeby on zmienił pozycje. Bardzo utrudnia prace nad kodem, a wszystko tylko po to żeby obsłużyć metode getLast(). Bez sensu, prawda?
3. operator[] nie uwzględnia template-a.
4. Metody resize() przekombinowana, a argument typu bool tylko miesza. W ogóle nie potrzebna wg mnie.

Co do samej zasady działania. std::vector za każdym razem gdy brakuje mu miejsca na przyjęcie kolejnego, podwaja swój rozmiar - alokuje dwa razy więcej pamięci. Dzięki temu jest znacznie szybszy. Prawda - marnujemy pamięć, ale zyskujemy mase czasu.

Comments

Dziękuję za zwrócenie uwag :) Postaram się naprawić, ale najpierw poczytam dokładniej o tych vectorach :)