Klasa stack

Siema Bracia (Siostry też ;)

Onego czasu dostałem zadanie napisania klasy Stack wg wytycznych:
-przechowywanie wartości całkowitoliczbowych,jakich nie powiedziano; przyjąłem int
miał posiadać metody:
-push; przyjmująca 1 argument będący elementem do położenia na stosie
-pop; bezargumentowa zdejmująca element z wierzchołka stosu.Jeśli stos jest pusty ma polecieć wyjątek
-min; bezargumentowa zwracająca najmniejszy element jaki umieszczono na stosie,przy czym nie powinna go ze stosu usuwać
-empty; bezargumentowa zwracająca true jeśli na stosie nie ma elementów,jeśli są to false

Napisałem tą klasę (kod w załączniku,o dziwo .h i .cpp nie chciał łyknąć,pojechał mi komunikatem "Typ "application/octet-stream" tego pliku nie jest akceptowany") i teraz mam do Was pytanie-nie przedobrzyłem z czymś czasem?Podoba się/nie podoba?Albowiem nie dostałem pracy tam gdzie aplikowałem i nie wiem już,czy to z powodu tego że coś kiepsko napisałem,czy innych względów...Stąd ewentualne kiepskie kodzenie chciałbym wyeliminować pytając się Was.

Dlaczego rzucasz przepełnienie, a nie rezerwujesz nowej pamięci? Chcąc skorzystać z Twojej klasy oczekiwałbym od niej implementacji dynamicznego bufora, a nie tablicy opakowanej w klasę i dwie metody :)

int min(void);///Returns minimum value among the ones stored,or throws EmptyStack exception if the stack is empty

bool empty(void)///Returns true if no data have been pushed yet,false otherwise

{

		return isStackEmpty;

}

czy te metody wpływają w jakiś sposób na życie obiektu i modyfikują coś wewnątrz jego czy są, że tak nazwę "read only" ? Jeśli nie wpływają one na obiekt na rzecz, którego są wywoływane to wypadało by nadać im const.

Ostatnie pytanie brzmi "po co Ci te void'y" ? Estetyka czy masz w tym jakiś głębszy cel? To nie jest C.
pozdrawiam

@przepełnienie:
Jak napisałem,ten stos działa podobnie do znanego mi z asemblera pod DOS-ale tylko i wyłącznie dlatego,że nie określono jak ma być zrealizowany.Pisząc go na spokojnie i tak do rzeczywistego użytku najprawdopodobniej oparłbym go na pojemniku typu talia.

@consty:
To są właśnie te oczywistości,które mi umknęły i które miałem nadzieję przy Waszej pomocy znaleźć ;)Całkowita racja tutaj.

@voidy:
estetyka+przyzwyczajenie z czasów pisania w c.

Za taki kod można dostać pracę co najwyżej na kasie w Biedronce. Do rzeczy:

• większość objętości stanowią zbędne, śmieciowe komentarze:
• kod piszesz dla programisty, który tak jak ty zna język i posiada pewne doświadczenie, nie dla laika, któremu musisz pokazywać palcem "a cio to? a zmienna! xD"
• przekładasz kod na angielski, grafomańsko rozpisujesz wszystko, dłużej czyta się "dokumentację" niż kod i mniej z tego wynika
• komentujesz sensownie nazwane składowe o oczywistym działaniu i przeznaczeniu, w tym deklaracje funkcji, które same powinny być jednoznaczne
• rzucane wyjątki wpisujesz w komentarz zamiast klauzuli throw, chociaż w tym wypadku zwyczajnie nie możesz tego zrobić sensownie
• komentujesz wyniki oczywistych testów logicznych
• komentujesz podstawowe elementy mechaniki języka, każdy czytający kod doskonale te zasady zna
• najlepszym komentarzem jest sytuacja, kiedy komentarz w ogóle jest zbędny, następnie komentuje się nieoczywiste rzeczy i algorytmy oraz wzorce projektowe, kod powinen sam siebie dokumentować, wyrazistym nazewnictwem i strukturą
• tworzysz zbędne składowe i zależności
• empty zamist używać dodatkowej składowej mogłoby sprawdzać realny stan kontenera, w tym wypadku bool empty() { return stackArea == stackPointer; }
• isStackEmpty jest używane w wielu miejscach wprowadzając zależność od wewnętrznej implementacji chociaż istnieje metoda empty, która ukrywa detale sprawdzania stanu kontenera
• niektóre nazwy są w pierwszej chwili niejasne, jak stackArea i stackPointer;
• zamiast indeksowania tablic używasz koszmarnej arytmetyki pointerów, po co? Wydajności nie zmienia w zauważalny sposób, użyte w pokazany sposób jest skrajnie nieczytelne
• jako wyjątków używasz elementów enumu, chyba największy debilizm w tym kodzie:
• klauzula catch może łapać wyłącznie po typie, jesteś zmuszony zawsze łapać typ Exceptions i potem sprawdzać, co konkretnie złapałeś
• nie jest możliwe umieszczenie konkretnej wartości enuma w klauzuli throw przy deklaracji funkcji lub metody
• enum nie może przekazywać dodatkowej informacji
• rzucanie czegokolwiek innego niż obiekty to efekt zamierzchłych czasów, wyłącznie kompatybilność wsteczna, wyjątki powinny dziedziczyć z dedykowanej klasy bazowej, jak std::exception i pochodne
• uniemożliwiasz złapanie tylko konkretnego typu wyjątku rzucanego przez stos, np. w wypadku zagnieżdżonej obsługi wyjątku, konieczny jest if lub switch i przerzucanie w górę
• niekiedy konieczność nadużywania catch(...)
• gorszy support ze strony narzędzi
• wyszukiwanie wartości minimalnej w metodzie pop(), z operacji O(1) zrobiłeś O(n), przeniosłeś logikę min() do pop(), jeżeli tak bardzo chcesz spamiętywać najmniejszą wartość to powinieneś wprowadzić flagę informującą o ważności przechowywanej liczby i przeszukiwać jedynie wtedy, kiedy aktualnie przetrzymywana wartość mogła zostać unieważniona (push lub min po pop, ale nie pop po pop, informacja na tym etapie jest zbędna)
• przyjmujesz rozmiar tablicy jako liczbę ze znakiem
• metody nie posiadające efektów ubocznych powinny być const
• stosujesz te same nazwy składowych i argumentów konstruktora, co w liście inicjalizacyjnej jest nieczytelne
• nie ma realokacji, powiększania stosu w miarę potrzeb
• największą katastrofą tego kodu jest brak operatora przypisania i konstruktora kopiującego, chociażby prywatnych stubów
• przy kopiowaniu i przypisaniu zachodzi kopiowanie pole po polu, kopiowane są wartości pointerów
• otrzymujesz kilka stosów trzymających ten sam pointer
• w momencie zwolnienia pamięci przez destruktur jednego stosu zniszczy pamięć używaną przez pozostałe, scenariusze use-after-free i free-after-free, co może (ale niestety nie musi od razu) skutkować wyłożeniem programu, czasem czymś jeszcze poważniejszym
• to elemntarna podstawa, której typowy adept C++ uczy się w drugim tygodniu nauki

-wszyskie komentarze (prócz tych uwag) piszę tak,jak robiłbym to w poważnym projekcie

Pierwszego dnia pracy zostałbyś zatłuczony monitorem za takie komentarze.

-ta klasa aż prosi się,aby ją zdefiniować szablonem:
...
jednie kłopot byłby wtedy z tą minimalną wartością,jeśliby podało się jakiś typ złożony,np string

operator< lub komparator przekazywany jako argument albo parametr, tak jak w STL, kłopotu by nie było.

Sądząc po przedstawionym kodzie to jesteś najpóźniej na pierwszym roku studiów, jeszcze długa droga przed Tobą. Polecam przerobienie Thinking in C++ i np. Clean Code na dobry początek.

programista COBOLa: dobra robota :)

MasterBLB: Aż z ciekawości ściągnąłem kod. Pierwsza rzecz, która rzucił mi się w o czy to konstrukcja _tmain(). Nie jest to część klasy, ale skoro wysyłasz jakiś kod, na pewno zostanie on chociaż podejrzany. Standard podaje dwie poprawne formy funkcji main i którejś z nich należy użyć. _tmain() to jakiś dziwoląg.

Co powiesz na scenariusz, kiedy kod w pierwszej kolejności próbuje skompilować jakiś technik, który większej wiedzy o C++ nie posiada? Kompilator nie znajduje maina i kończy robotę.

Użycie szablonu byłoby zdecydowanie lepszym pomysłem. Wtedy natrafiłbyś na realny problem i zaproponowałbyś jego rozwiązanie. A tak masz więcej komentarzy niż kodu :)

@programista COBOLa:
co do komentarzy,to jakoś nikt mnie nie zatłukł :P Mało tego,przydają się po pewnym czasie jak wracam do starego kodu nie pamiętając już,co tam on miał robić.
Ale reszta uwag niezwykle cenna,dzięki :)
Niejasne jest tylko to wyszukiwanie min (O1 i On)-co masz dokładnie na myśli?Jak niby mam znaleźć minimalną wartość pośród pozostałych na stosie nie sprawdzając co na nim leży?
@K:
_tmain to automat wygenerowany przez VS2003

MasterBLB napisał(a)

Niejasne jest tylko to wyszukiwanie min (O1 i On)-co masz dokładnie na myśli?Jak niby mam znaleźć minimalną wartość pośród pozostałych na stosie nie sprawdzając co na nim leży?

Rzecz w tym, że metoda pop() powinna realizować wyłącznie swój cel, jakim jest zdejmowanie elmentu z wierzchu stosu, to zaś realizuje się w czasie O(1). Ty łamiesz zasady i dodajesz dodatkową logikę, wyszukiwanie minimum podczas zdejmowania ze stosu, dla samych efektów ubocznch, które dla pop() nie mają znaczenia, w O(n). Teraz spójrz na ten kod:

int sth1 = stack.pop();
int sth2 = stack.pop();
int sth3 = stack.pop();
int sth4 = stack.pop();

Czy faktycznie wyszukiwanie minimum za każdym razem jest tutaj potrzebne? Czy użytkownik chciał wyszukać minimum? Spamiętywanie wartości bywa przydatne, ale rób to z sensem, najprostszy wariant:

class Stack {
    bool isMinValueCacheValid;
    int cachedMinValue;
    // ...
    void push(int newValue) {
        // ...
        if (isMinValueCacheValid) {
            cachedMinValue = std::min(cachedMinValue, newValue);
        }
        // ...
    }
    int pop() {
        // ...
        isMinValueCacheValid = false;
        // ...
    }

    int min() {
        // ...
        if (!isMinValueCacheValid) {
            cachedMinValue = findMin();
            isMinValueCacheValid = true;
        }
        return cachedMinValue;
    }
};

Teraz minimum jest szukane wyłącznie wtedy, kiedy jest potrzebne. Pozostaje problem stałych referencji i wywoływania metody min, która powinna dać się dla nich wywołać. Rozwiązania są dwa - pola mutable lub przeciążony wariant min dla const zwracająca wynik findMin().

Jaśniej?

Chyba nie wczytałeś się dobrze Bracie-wyszukiwanie nowego min jest realizowane wyłącznie wtedy,kiedy wartość==minCache została właśnie zdjęta z wierchołka stosu,nie za każdym razem.

Faktycznie niedopatrzenie z mojej strony. Mimo wszystko nadal nie jest to efektywne, stos nie przechowuje wartości unikatowych:

for (int i = 4; i > 0; --i) {
    stack.push(i); // lub stack.push(0);
}
int sth1 = stack.pop();
int sth2 = stack.pop();
int sth3 = stack.pop();
int sth4 = stack.pop();

Przy podobnym układzie stosu wyszukiwanie jest realizowane przy każdym pop().

Ok widzę już co nie do końca jest tak jak trzeba.O ile idea zapamiętywania min podczas push/pop jest słuszna,o tyle zrealizować to faktycznie jest lepiej poprzez jakąś flagę isMinValueValid.Flagę tą ustawiałoby się na false w pop() zamiast tego kodu znajdującego minimum,ów zaś należałoby przenieść do funkcji min.Przy czym polemizowałbym z tym czyszczeniem przy każdym pop-ie,ja widziałbym to raczej w sytuacji poppedValue==cachedMinValue.
Hmm aż nie wiem jak tak teraz patrzę,co mnie podkusiło aby tak to zrobić...