C++ Stack implementation – C / C++ – Fórum – Programujte.com

Ahoj, chcel som implementovať Stack v C++ pomocou OOP a pola (vektor som nechcel).
Stack.cpp
 

// Stack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Stack.h"
#include <assert.h>
#include <iostream>

Stack::Stack()
{
	Stack::sizeOfStack = 0;
}

Stack::~Stack() {
	delete[] Stack::st;
}

void Stack::push(int num) {
	Stack::st[sizeOfStack++] = num;
}

int Stack::size() {
	return Stack::sizeOfStack;
}

bool Stack::isEmpty() {
	return Stack::sizeOfStack == 0;
}

int Stack::pop() {
	assert(!(Stack::sizeOfStack == 0));
	return Stack::st[sizeOfStack--];
}

void Stack::print() {
	for (int i = 0; i < Stack::sizeOfStack; ++i)
		std::cout << Stack::st[i] << " ";
	std::cout << std::endl;
}

Stack.h
 

#ifndef STACK
#define STACK

class Stack {

	private:
		unsigned short sizeOfStack;
		int *st = new int[sizeOfStack];

	public:
		bool isEmpty();
		int pop();
		void print();
		void push(int num);
		int size();
		Stack();
		~Stack();
		
};
#endif

Otázkou je, že prečo to funguje? Skúšal som iba jeden prípad kedy som to naplnil 4 hodnotami a skúšal
som popovať a fungovalo to. Plán bol dynamicky zväčšovať pole po push() , avšak nejak som na to zabudol , pustil a ide to aj takto. Prepisujem v tomto prípade pamäť ktorú nevlastním? 

Inicializace st proběhne před konstruktorem a proměnná sizeOfStack v té době není inicializovaná.

Pokud má malou hodnotu, tak zapisuješ za to pole. Velikost alokované paměti se zarovnává na nějakou hodnotu, takže za tím polem může být prostor, který lze bez problému přepsat. Ale většinou je to jen pár bajtů, které když překročíš, tak by to nejpozději při delete[] mělo sletět.

Nebo má sizeOfStack takovou hodnotu, že to pole je dostatečně velké.

Mimochodem, pop() máš špatně.

Dík za odpoveď, potom mi to aj nejako došlo že nie je inicializovaná takže v nej bude asi nejaká veľká hodnota.
Trochu som to opravil, prechádzam z C a jediný spôsob čo mi napadol bol cez realloc čo mi nepríde moc C++ :-)
Za hocijaké postrehy budem rád 
 

// Stack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Stack.h"
#include <assert.h>
#include <iostream>
#include <stdlib.h>
#include <vector>

Stack::Stack()
{
	Stack::sizeOfStack = 5;
	Stack::numbersInStack = 0;
	Stack::st = new int[Stack::sizeOfStack];
}

Stack::~Stack() {
	delete[] Stack::st;
}

void Stack::push(int num) {
	Stack::st[numbersInStack++] = num;
	if (numbersInStack == sizeOfStack) {
		sizeOfStack *= 2;
		st = static_cast<int *>(std::realloc(st,sizeof(int) * sizeOfStack));
	}
}

int Stack::size() {
	return Stack::numbersInStack;
}

bool Stack::isEmpty() {
	return Stack::numbersInStack == 0;
}

int Stack::pop() {
	assert(!(Stack::numbersInStack == 0));
	return Stack::st[--numbersInStack];
}

void Stack::print() {
	for (int i = 0; i < Stack::numbersInStack; ++i)
		std::cout << Stack::st[i] << " ";
	std::cout << std::endl;
}

// Stack.h
#ifndef STACK
#define STACK

class Stack {
	private:
		unsigned short sizeOfStack;
		unsigned short numbersInStack;
		int *st = NULL;

	public:
		bool isEmpty();
		int pop();
		void print();
		void push(int num);
		int size();
		Stack();
		~Stack();
		
};
#endif 

#3 Stamp
realloc patri k malloc, neni ani trochu dobrej napad pouzivat ho s new. To same jako se nemicha new a free. Kdo vi jakou neplechu to pak udela pri uvolnovani pomoci delete[]. Hlavne proto, ze interne ma new[] jeste taky ulozenou velikost pred samotnym polem (vrati se ale pointer az na pole). Obzvlaste u objektu to bude delat silenou paseku. Vector taky zvetsuje tak, ze udela dalsi pole a puvodni prvky presune.

Dalsi zasadni problem je co se stane, pokud udelas kopii objektu? Ja nevim, treba predani do funkce hodnotou. Pointer bude stejny v obou instancich a jakmile funkce skonci, zavola se delete[] a najednou mas v puvodnim stacku dangling pointer (pointer na neplatna data) a pak se to samozrejme bude pokouset o druhe uvolneni jiz uvolnene pamete. Taktez, pokud zmenis data, tak se projevi i navenek ikdyz to necekas (ale ne velikost a tak, jen data v poli). Bude to chtit nastudovat  Rule of Three / Rule of Five.

#4 KIIV
ahoj, zajímavé téma.

Chápu to dobře, že pokud objekt chci předávat funkcím hodnotou a pro návratový typ, měl bych mít nadefinovanou obsluhu těch přiřazovacích operátorů, tzn hlubokou kopii, aby se to chovalo správně?

#5 MilanL
Pokud si v objektu vytvaris/zabiras nejake resourcy (a to neni jen alokace pameti), tak je to nutne.

Jinak napriklad u kopirovani (asi hlavne prirazenim) je nutne pohlidat jestli to neni ten samy objekt. Co se stane, kdyz mas nejakou spravu resourcu a nekdo udela   obj = obj; Proste uplne nejdulezitejsi je copy constructor a copy assigment operator.

Move constructor a move assigment operator jsou dulezite, pokud se objekt "registruje" nekam jinam, do nejakych observeru nebo tak. Pokud presunes objekt, zmeni se vlastne jeho umisteni v pameti a callbacky obvykle obsahuji pointer na danny objekt a pointer na nejakou jeho metodu.

Kazdopadne, pokud se predava objekt, tak se pouzivaji zasadne reference. Pokud se objekt nema uvnitr funkce menit, tak konstantni reference. Pak se spolehlive zabrani kopii.

No trochu som to Rule of three postudoval, tak dufam ze to je aspon o nieco lepsie :-) 

// Stack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Stack.h"
#include <assert.h>
#include <iostream>
#include <stdlib.h>
#include <vector>

Stack::Stack()
{
	Stack::sizeOfStack = 5;
	Stack::numbersInStack = 0;
	Stack::st = new int[Stack::sizeOfStack];
}

Stack::Stack(const Stack &n) : // copy constructor
	st(new int[n.numbersInStack]), 
	numbersInStack(n.numbersInStack), 
	sizeOfStack(n.sizeOfStack)
{
	std::copy(n.st,n.st+n.numbersInStack,st);
}

Stack& Stack::operator=(const Stack &source) { // copy assignment constructor
	int *newData = new int[source.numbersInStack];
	numbersInStack = source.numbersInStack;
	sizeOfStack = source.sizeOfStack;
	std::copy(source.st, source.st + source.numbersInStack, newData);
	delete[] st;
	st = newData;
	return *this;
}

Stack::~Stack() { // destructor
	delete[] Stack::st;
}

void Stack::push(int num) {
	Stack::st[numbersInStack++] = num;
	if (numbersInStack == sizeOfStack) {
		sizeOfStack *= 2;
		int *newSt = new int[sizeOfStack];
		std::copy(st, st + numbersInStack, newSt);
		delete[] st;
		st = newSt;
	}
}

int Stack::size() {
	return Stack::numbersInStack;
}

bool Stack::isEmpty() {
	return Stack::numbersInStack == 0;
}

int Stack::pop() {
	assert(!(Stack::numbersInStack == 0));
	return Stack::st[--numbersInStack];
}

void Stack::print() {
	for (int i = 0; i < Stack::numbersInStack; ++i)
		std::cout << Stack::st[i] << " ";
	std::cout << std::endl;
}

#ifndef STACK
#define STACK
#include <algorithm>
class Stack {
	private:
		unsigned short sizeOfStack;
		unsigned short numbersInStack;
		int *st = NULL;

	public:
		bool isEmpty();
		int pop();
		void print();
		void push(int num);
		int size();
		Stack();
		Stack(const Stack &n);
		~Stack();
		Stack &operator=(const Stack &source);
		
};
#endif 

#7 Stamp
Obávám se, že vás KIIV zavedl na myšlenkové zcestí. Prvně si položte otázku: "skutečně potřebuji, aby se mi Stack uměl kopírovat?" Na 99% si odpovíte negativně, k čemu by to bylo.

Starost o kopírování objektů je v C++ nutná, protože překladač je schopen objekt zkopírovat podle svého úsudku, někdy navzdory přání programátora (tím myslím, že existují programátorské chyby, které nepovedou k chybovému hlášení překladače, ale k neočekávané kopii objektu).  A pokud tomu nezabráníte, budou se dít špatné věci (např. zmiňovaný double delete).

Ovšem správná cesta není implementovat kopii objektům, u který to nedává smysl. Správná cesta je překladači říci "tenhle objekt se neumí kopírovat." V C++11 se to dělá takhle: 

class Stack {
  public:
    Stack(const Stack&) = delete;
    Stack& operator = (const Stack&) = delete;
};

Tzn. explicitně jste řekl, že kopírovací konstruktor a kopírovací operátor nechcete. Pokud toto neuděláte, překladač vám je dokáže sám od sebe vygenerovat jako mělkou kopii (kvůli zpětné kompatibilitě, aby se struktury samy od sebe kopírovaly tak, jak bylo zvykem v C).

Pokud máte starší překladač, který C++11 nepodporuje, dělalo se to takto: 

class Stack {
  private:
    Stack(const Stack&);
    Stack& operator = (const Stack&);
};

Konstruktor a operátor se pouze nadeklaroval, funkce se ale nikde nenaimplementovaly. Tím jste překladači zabránil, aby je vygeneroval. Zároveň, pokud je překladač chtěl někde použít, vylámal si zuby na tom, že jsou privátní. Jediná vada byla, pokud jste kopii použil v kódu, který měl k privátním položkám přístup. Pak se kód normálně přeložil a selhalo až linkování, které funkce nikde nenašlo.

#8 Staon
domnívám se, že nemáš tak docela pravdu, copy jeu tam použito pro 2 případy:

1) konstruktor s hodnotou

2) přiřazení hodnoty operátorem =

Jinak reaguješ na pár měsícl starý dotaz, který byl nejspíše úlohou na konci semestru.

#9 MilanL
Odkažte mě, prosím, na konkrétní řádky kódu, kde se Stack kopíruje. Asi jsem natvrdlý, ale nic takového tam nevidím.

Pravděpodobnost reálného použití kopírování stacku je poměrně nízká. Ne, že bych něco takového už neviděl. Pokud např. úlohu paralelizujete, pak může být při rozhození do jiného vlákna nutné překopírovat rozpracovaný stack. Ale jestliže dotyčný má problémy napsat vlastní Stack, pak asi těžko řeší něco takového.

Tohle forum se jmenuje C++, ne semestrální práce. A z hlediska C++ jsem považoval za nutné, byť se zpožděním, reagovat, protože jste dotyčného chudáka pravděpodobně navedli na nesmyslnou myšlenku, že musí implementovat kopírování každému objektu.

#10 Staon
Jakmile pouziva nejake dalsi zdroje (pamet, mutexy, ..............), MUSI bezpodminecne dodrzet pravidlo tri, nebo pravidlo peti (pro novejsi prekladace).

Pravidlo tri:  MUSI byt definovan vlastni destruktor, copy construtor a copy assigment operator (a tento by mel jeste taky kontrolovat prirazeni sam sebe).

Pravidlo peti: pridava jeste  move constructor a move assigment operator.

Do toho samozrejme patri i zakazani defaultnich variant (coz si delal pomoci = delete). Je to forma explicitni definice.

O co jde - objekty se v C++ strasne casto kopirujou. Predas ho hodnotou do funkce, mas kopii, chces ho vlozit do jineho kontejneru, je temer nemozne vyhnout se kopii (od c++11 je tu alespon nejaka sance) a tak dale. A zacatecnici na tohle budou zasadne zapominat. Proc by tam sakra psali blbosti jako   const & ...

#11 KIIV
Bez urážky, ale váš příspěvek obsahuje několik chybných tvrzení.

Copy konstruktor a operátor = nemusí být definován - on musí být deklarován. Explicitní deklarací zabráníte, aby je překladač vygeneroval. Nikde není psáno, že je nutné je i definovat, pokud je nepotřebujete. Což je mimochodem většina případů. I v případě stacku je usecase, kdy potřebujeme kopii celého zásobníku, dost nepravděpodobný. Proč tedy implementovat něco, co pak stejně nikdy nezavoláme. A to nemluvím o tom, že u většiny objektů implementace kopírování ani nedává smysl a vlastně ani nejde udělat.

Další chybné tvrzení je, že se kopírování nejde vyhnout. Samozřejmě jde - přesně tak, jak jsem to popsal. Objekt se zakázaným kopírováním pak nejde předat hodnotou, nejde vrátit hodnotou, ani nejde vložit do kontejneru. A to je ve většině případů chtěné. Navíc v případě polymorfních objektů (nebo obecně ve spojitosti s dědičností) je to naprosto nutné - bráníte se tak slicingu.

#12 Staon
Ja to "= detele" uz povazuju za definici. Proste uz je definovano, ze je metoda zakazana. Deklarace znamena, ze nekde bude (mozna) i definice. Je to slovickareni.

Ano, kopirovani se da vyhnout, ale musite sakra dobre vedet, co delate (a musi byt standard C++11 a vice). Nicmene jsem nemluvil o vlastnich tridach, ale i o STL. Tam zakazete velky kulovy.

U polymorfizmu je dulezite pouzivat vzdy pointer nebo referenci, jinak slicing opravdu hrozi. Pokud toto nekdo nezvladne, tak holt musi zakazovat kopirovani, ikdyz by se treba hodilo.

Mimochodem, pokud si objekt registruje nejake callbacky na sebe, tak je potreba davat bacha i na move operace. Obzvlaste pri ukladani do kontejneru jako vector, ktery se obcas taky nafukuje.

#13 KIIV
Nechce se mi s vámi hádat, ale vaše příspěvky na toto téma mi připadají příliš zavádějící a nepřesné.

Pokud vám rozdíl mezi deklarací a definicí funkce připadá jako slovíčkaření, tak jste se, obávám se, minul oborem. Ta delete deklarace je skutečně pouze deklarací, kterou říkáte, že žádná definice nikdy nebude. Chápu, jak to myslíte, ale pokud chcete něco takového vysvětlovat nováčkům, tak není možné používat termíny vágně. A navíc tento rozdíl je klíčový pro vysvětlení způsobu, jak se kopírování zakazovalo před C++11.

Připouštíte, že kopírování se dá vyhnout, ale přidáváte "musíte sakra dobře vědět, co děláte." Mohl byste být konkrétní, co tím máte na mysli? Protože realita je taková, že vyhnout se kopírování je právě ta jednoduchá věc i pro začátečníky: prostě ho jednoduše bezmyšlenkovitě zakazujete všude. Dobře vědět, co děláte, musíte naopak v době, kdy kopírování něčeho chcete povolit.

Dále tvrdíte, že pro vyhnutí se kopírování potřebujete C++11. Mohl byste být konkrétní a vysvětlit, co konkrétně tomu v C++98 brání? Protože já jsem posledních 12 profesních let strávil na překladači, který se C++11 ani nepřiblížil a nechtěnému kopírování jsem se naprosto úspěšně bránil. Postup jsem popsal ve svém příspěvku výše.

Jak konkrétně souvisí STL s kopírováním? STL kontejnery se umí kopírovat/movevovat. OK, ale to je prostě jejich normální vlastnost, kterou můžete i nemusíte využít. Objekty vkládané do kontejnerů musí být kopírovatelné/movevatelné. Pokud kopírování/move zakážete, objekt prostě vložit nejde. S čím je tedy konkrétní problém?

U polymorfismu je skutečně nutné používat referenci nebo ukazatel, naprosto souhlasím. Zakázáním kopírování třídy toto vynutíte - objekt pak nejde použít jinak. Vůbec to není o tom, zda to někdo "zvládne". Zapomenout napsat & u argumentu funkce je zcela běžná programátorská chyba, kterou udělá i zkušený profesionál. Pokud kopírování nezakazujete s tím, že to přece "zvládáte", ani svatý překladač vám nepomůže.

Kopírovací a move C++ sémantika se až na dvě výjimky (níže) u polymorfního objektu nehodí nikdy. Ne proto, že jsem to řekl, ale proto, že kopírování/move je vlastnost vyhodnocovaná při překladu, což je v přímém rozporu s očekávaným chováním polymorfního objektu. A psát objekty, které se chovají jinak, než jejich uživatelé očekávají, je poměrně zaručená cesta do pekla.

Pokud chcete kopírovat polymorfní objekt, dělá se to postupem, který se označuje jako klonování. Tzn. objekt má na rozhraní virtuální metodu (typicky pojmenovaná clone), která vytvoří kopii. Je praktickým zvykem tuto metodu interně implementovat pomocí protected copy konstruktoru (první ze zmiňovaných výjimek).

Druhá výjimka jsou výjimky. Zde se překladač při odvíjení zásobníku postará o kopii/move správného typu, takže nedochází ke slicingu. Ovšem ke slicingu může dojít a také dochází, pokud výjimku nechytnete referencí - což je přesně důvod, proč se výjimky chytají referencí.

Poznámka o move objektů, které se někde registrují nebo si např. drží uvnitř sebe pointer někam do sebe, je samozřejmě zcela správně. Zbývá dodat, že zákazem kopírování, tak jak jsem ho popsal, zároveň zakazujete i move sémantiku, protože překladač vám nevygeneruje move konstruktor/operátor, pokud máte deklarovaný příslušný copy konstruktor/operátor.

#14 Staon
Dejme tomu, je to deklarace. Jen sem vysvetloval, proc sem to povazoval za definici. Alespon sem se zase neco priucil.

Aby clovek mohl programovat, tak je uplne jedno, jestli slovickari nebo ne. Dulezitejsi je, ze kdyz nekdo reportuje chybu, tak si vzpomenu na to, ze kolegove presne to same resili uz pred 8 lety (a to jen ze sem to zaslechl, ne ze by to reslili se mnou). Novackove presnou terminologii stejne zapomenou hned po precteni. Ja ji taky davno zapomnel, jelikoz to k nicemu nepotrebuju. Jedna zminka za rok je malo, abych si to udrzel.

Ke kopirovani:

Neco funkce()
{
  Neco blabla;
  blabla.makej();
  blabla.nastav();
  return blabla;
}

Dalsi velice  priklad je z Arduina, kde lidi vetsinou ani netusi, ze jde o C++ (a zprasenou verzi std::string alias Arduino String class):

serial.println(String("Nejaky vypis: ") + cislo1 + " neco dalsiho: " + ".............");

V c++11 je move semantika. Viz prvni priklad. Sice tam vznika vice instanci toho objektu, ale nekopiruji se data, presunou se do dalsiho. Predpoklada se samozrejme trida, ktera dava smysl, ze je kopirovatelna. A kopie je draha. U druheho prikladu by trosku pomohla presouvanim dat, ale ne moc, jelikoz se neustale zvetsuji retezce uvnit docasnych objektu.

Jen tak mimochodem proletel jsem si projekt, na kterem pracuju, a veskery polymorfni tridy mam, svete div se, nekopirovatelne. Sice trochu zastarale, pomoci boost::noncopiable, ale to je spise proto, ze je z toho naprosto jasny zamer. Coz u schovavani zakazanych operatoru a konstruktoru, nebo jejich zakazani pomoci = delete, byt nemusi (ten kdo to cte, uz to musi znat, nebo byt alespon hodne chapavej)

Stl - kdyz dela neco, co kopiruje funkcionalitu toho, co existuje, tak by to mohlo byt ve stejnem stylu. Respektive je lepsi rovnou pouzit co existuje. Je to lety overene a testovane. To same algoritmy a tak. Range based for loop je taky skvela vychytavka z C++11, ale na druhou stranu nechutne casto narazim na to, ze potrebuju znat i index, takze zpet k pocitadlu.

Vektor objektu stejneho typu (4bodovy polygon), kde je zbytecne pouzivat dynamickou alokaci, ale pouziva se observer pattern pro zjistovani, jestli se nekliklo v danne oblasti.

Kazdopadne osobne se venuju vetsinou maintenance a sustenance. I zkuseni programatori dokazou udelat docela zaludny chyby. A zacatecnici zvladnou udelat kazdou moznou i nemoznou chybu co se da.

Trochu jina liga jsou pak programatori, co mysli, ze jsou zkuseni a pak je v kodu same nedefinovane chovani (UB) a tak. Treba veci co zalezi na poradi vykonavani parametru a side effekty. Pojem sequence point jim nic nerika a vznikaji veci jako:  fingerTemplate[index++] = bytesReceived[index];   (tohle je teda z jednoho examplu pro arduino fingerprint sensor, ale example je to teda naprosto prisernej, zapisy mimo pamet a tak)