Zapoctovy test 23.1. 14:00

stinny
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 23. 1. 2007 15:23

Zapoctovy test 23.1. 14:00

Příspěvek od stinny »

Dnesni zadani bylo az trapne jednoduche. Dokulil nam na tabuli napsal hlavicky vsech pozadovanych funkci, potom popsal dva ruzne navrhy na reseni. Mel jsem to tak za 25 minut, opravdu o nicem.

Meli jsme napsat sablonu tridy shared_ptr, ktera se chova jako jediny vlastnik nejakeho objektu. To znamena, ze ukazuje na nejakou polozku a pri sve destrukci s sebou vezme i ji. Cele to melo byt navrhnute pomoci Counted-pointers, bylo tedy mozne, aby se vlastnik zduplikoval (treba nekolikrat), a prislusna data mela tedy byt odalokovana az v momente, kdy zahyne posledni vlastnik. Cele to melo byt tak nejak exception-safe.

Melo to mit nasledujici hlavicku:

Kód: Vybrat vše

template <class T> class shared_ptr {
public:
	shared_ptr();
	explicit shared_ptr(T * p);
	~shared_ptr();
	shared_ptr& operator= (const shared_ptr & r);
	void swap(shared_ptr& r);
	void reset();   // "vzda" se vlastnictvi objektu, ale zustava nazivu
	T* get() const;
	T& operator*() const;
	T* operator->() const;
	long use_count() const;    // pocet vlastniku objektu
	bool operator==(const shared_ptr& r);   // porovnava, zda ukazuji na stejny objekt
	bool operator!=(const shared_ptr& r);
};
Moje reseni - krabickovy model.

Kód: Vybrat vše

#include <stdexcept>
#include <iostream>
#include <string>


template <class T> struct shared_ptr_body {
	int count;
	T * data;
};


template <class T> class shared_ptr {
private:
	shared_ptr_body<T> *body;
public:
	shared_ptr() : body(new shared_ptr_body<T>) {
		body->count = 0;
		body->data = 0;
	};
	explicit shared_ptr(T * p) : body(new shared_ptr_body<T>) {
		body->count = 1;
		body->data = p;
	};
	~shared_ptr() {
		if (body->data) {
			--body->count;
			if (!body->count) {
				delete body->data;
				delete body;
			}
		} else {
			delete body;
		};
	};
	shared_ptr(const shared_ptr & r) {
		body = r.body;
		++body->count;
	};
	shared_ptr& operator= (const shared_ptr & r) {
		shared_ptr tmp(r).swap(* this);
		return * this;
	};
	void swap(shared_ptr& r) {
		shared_ptr_body<T> *tmp(body);
		body = r.body;
		r.body = tmp;
	};
	void reset() {
		shared_ptr tmp.swap(* this);
	};
	T* get() const {
		if (body->data) 
			return body->data;
		else
			return 0;
	};
	T& operator*() const {
		if (body->data) 
			return *(body->data);
		else
			throw std::bad_alloc();
	};
	T* operator->() const {
		return get();
	};
	long use_count() const {
		return body->count;
	};
	bool operator==(const shared_ptr& r) {
		return body->data == r.body->data;
	};
	bool operator!=(const shared_ptr& r) {
		return body->data != r.body->data;
	};
};

using namespace std;

int main(int argc, char **argv) {

	// pokusy s charem
	char *ta = new char('a');
	char *tc = new char('c');

	shared_ptr<char> a;
	a = shared_ptr<char>(ta);
	shared_ptr<char> b(a);
	shared_ptr<char> c(tc);
	cout << *a;
	cout << *b;
	cout << *c << endl;
	c = a;
	cout << *a << *b << *c << a.use_count() << ' ' << (a == b) << ' ' << (a != b) << endl;


	// pokusy se stringem
	string *ts = new string("retezec");
	shared_ptr<string> s(ts);
	cout << *ts << ": " << ts->size() << endl;
	shared_ptr<string> t(s);
	s.reset();

	t.swap(s);
	t = s;
	
	cout << *s << endl;
	cout << *t << endl;
	
}; 
Uživatelský avatar
Void
Matfyz(ák|ačka) level II
Příspěvky: 54
Registrován: 17. 1. 2006 16:21
Typ studia: Informatika Mgr.

upřesnění

Příspěvek od Void »

Ještě bych dodal, že nám navíc po 15 minutách ukázal, jak se to má přesně dělat.. :o

I když ten druhej elegantnější způsob řešení byl moc..
Aurë Entuluva!!
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Re: Zapoctovy test 23.1. 14:00

Příspěvek od cathack »

stinny píše:Dnesni zadani bylo az trapne jednoduche. ...
Ale tvoje řešení spadne na až trapně jednoduchém příkladu:

Kód: Vybrat vše

	int *pk = new int(3);
	{
		shared_ptr<int> p1(pk);
		{
			shared_ptr<int> p2(pk);
		}
		cout << "zrusil jsem p2" << endl;
	}
	cout << "zrusil jsem p1" << endl;
Druhý výpis neproběhne, protože int, na který ukazuje p1 už předtím zrušila p2. bylo by tedy potřeba, aby oba ukazovali na shared_body_ptr s count=2.

Jak toto řešit jsem ale nezjistil a odešel tudíž bez úspěchu. Jestli to zadávající uznával i bez toho, tak jsem pěkně nas*anej :?
Uživatelský avatar
vektor
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 7. 1. 2007 16:59
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zapoctovy test 23.1. 14:00

Příspěvek od vektor »

cathack píše:
stinny píše:Dnesni zadani bylo az trapne jednoduche. ...
Ale tvoje řešení spadne na až trapně jednoduchém příkladu:

Kód: Vybrat vše

	int *pk = new int(3);
	{
		shared_ptr<int> p1(pk);
		{
			shared_ptr<int> p2(pk);
		}
		cout << "zrusil jsem p2" << endl;
	}
	cout << "zrusil jsem p1" << endl;
Druhý výpis neproběhne, protože int, na který ukazuje p1 už předtím zrušila p2. bylo by tedy potřeba, aby oba ukazovali na shared_body_ptr s count=2.

Jak toto řešit jsem ale nezjistil a odešel tudíž bez úspěchu. Jestli to zadávající uznával i bez toho, tak jsem pěkně nas*anej :?
Pada ti to, lebo to pouzivas "proti specifikacii". Nechapem, ako ma podla teba p2 zistit, ze o pk sa uz "stara" p1. Spravne by si to mal pouzit takto:

Kód: Vybrat vše

shared_ptr<int> p2(p1);
pripadne

Kód: Vybrat vše

shared_ptr<int> p2;
p2 = p1; 
Presne z toho dovodu by mal mat shared_ptr nasledovny copy-constructor:

Kód: Vybrat vše

shared_ptr(const shared_ptr & ptr) {
	(_data = ptr._data)->inc();
};
Cely moj kod je k dispozicii tu.
I ? Unicode
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Re: Zapoctovy test 23.1. 14:00

Příspěvek od cathack »

vektor píše:Pada ti to, lebo to pouzivas "proti specifikacii".
Aha, a tu "specifikaci" jsme měli předpokládám odhadnout ze slovního zadání, ze kterého jsem rozuměl každé druhé slovo. No můj problém, měl jsem se zeptat. Každopádně by příště mohl zadávající napsat zadání aspoň na papír, aby bylo jasné, co se vlastně má dělat. Jestli to bylo ve skutečnosti takhle triviální, rvu si vlasy vztekem :(

Zkoušel jsem to totiž řešit pomocí statických dat skrytých ve třídě shared_ptr, kde se zaznamenávalo, jaké pointery už byly použity apod. Ale ke konci jsem se nedostal kvůli tisíce technickým detailům.
KrevO
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 22. 1. 2007 21:06

Re: Zapoctovy test 23.1. 14:00

Příspěvek od KrevO »

cathack píše: Aha, a tu "specifikaci" jsme měli předpokládám odhadnout ze slovního zadání, ze kterého jsem rozuměl každé druhé slovo. No můj problém, měl jsem se zeptat. Každopádně by příště mohl zadávající napsat zadání aspoň na papír, aby bylo jasné, co se vlastně má dělat. Jestli to bylo ve skutečnosti takhle triviální, rvu si vlasy vztekem :(

Zkoušel jsem to totiž řešit pomocí statických dat skrytých ve třídě shared_ptr, kde se zaznamenávalo, jaké pointery už byly použity apod. Ale ke konci jsem se nedostal kvůli tisíce technickým detailům.
No fakt je, ze toto s tymi pointrami co sa nevidia a jeden druhemu umaz data sa asi nejak lahko nevyriesi, kazdopadne to nechcel. My sme presne toto rozoberali na poslednom cviceni a ani cviciaci nam neporadil, ako na to. Asi to trivka nebude :)

Anyway, nepovedal by som ze zadanie bolo "trapne jednoduche", nie kazdy to asi cvicil a nie kazdy hned vedel ako na to, ked uz clovek raz nieco videl, je to potom prenho jednoduchsie. Ked nakreslil chlievicky a medzi nimi sipocky, potom to uz dost jednoduche bolo. Teda mozno az moc. No ale budem sa stazovat, ked to mam za sebou? :)
stinny
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 23. 1. 2007 15:23

Re: Zapoctovy test 23.1. 14:00

Příspěvek od stinny »

KrevO píše:Anyway, nepovedal by som ze zadanie bolo "trapne jednoduche", nie kazdy to asi cvicil a nie kazdy hned vedel ako na to, ked uz clovek raz nieco videl, je to potom prenho jednoduchsie. Ked nakreslil chlievicky a medzi nimi sipocky ...
No ono jde taky o to, ze to bylo na prednasce, Bednarek pomoci counted-pointers reprezentoval stringy (slajdy 94-100). Vzhledem k tomu, ze u stringu se jednalo o ruzne exemplare (fakticky) a tady to byly stejne, odpadal problem pri editaci, takze to bylo o to jednodussi ... samozrejme tam bylo potreba napsat i par jinych veci, ale ten, kdo si alespon precetl slajdy, mel inspiraci.

S tim, ze zadani nebylo jednoznacne a nebylo prilis dobre popsane, souhlasim. Ridil jsem se tim, ze ten ukazatel se chova jako vlastnik objektu, a tedy neni jinych vlastniku, nez ostatnich shared_ptr ... kdyby mi to nesebral, tak by bylo opravdu treba udelat nejakou statickou polozku v te tride ... alena to by asi bohate stacil nejaky STLkovy kontejner, napr. vector<pair<T*, shared_ptr_body<T>*> >, nejake push_back, find_if, erase ... i kdyz nevim jake technicke detaily by bylo treba resit a kolik casu by to sezralo ... mozna to zkusim :)
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Re: Zapoctovy test 23.1. 14:00

Příspěvek od cathack »

stinny píše:kdyby mi to nesebral, tak by bylo opravdu treba udelat nejakou statickou polozku v te tride ... alena to by asi bohate stacil nejaky STLkovy kontejner, napr. vector<pair<T*, shared_ptr_body<T>*> >, nejake push_back, find_if, erase ... i kdyz nevim jake technicke detaily by bylo treba resit a kolik casu by to sezralo ... mozna to zkusim :)
no zkus to. stačí vector<shared_ptr_body<T> *>.
je tam problém se statickými položkami v šabloně. resp. kdy se bude volat konstruktor pro statické datové položky v šablonové třídě? stále mi to házelo různé podivné chyby, do kterých jsem se tak zamotal, že jsem to raději vzdal.
KrevO
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 22. 1. 2007 21:06

Re: Zapoctovy test 23.1. 14:00

Příspěvek od KrevO »

stinny píše: No ono jde taky o to, ze to bylo na prednasce, Bednarek pomoci counted-pointers reprezentoval stringy (slajdy 94-100).
Aha, no vidiiiis, tak za to by sa mi bolo oplatilo tam pravidelne chodit ;)
stinny
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 23. 1. 2007 15:23

Re: Zapoctovy test 23.1. 14:00

Příspěvek od stinny »

Tak mi to nedalo ... nechtelo se mi to uplne ladit, ale proste to na danych pripadech nepada, vystupy to hazi rozumny.

Kód: Vybrat vše

#include <stdexcept>
#include <iostream>
#include <string>
#include <map>

using namespace std;

template <class T> class shared_ptr {
private:
   T * data;
   static map<T*, int> used;
public:
   shared_ptr() : data(0) {};
   explicit shared_ptr(T * p) : data(p) {
	  map<T*, int>::iterator it = used.find(p);
	  if (it == used.end())
		used[p] = 1;
	  else
	    ++used[p];
   };
   ~shared_ptr() {
      if (data) {
         --used[data];
         if (!used[data])  {
              used.erase(data);
              delete data;
         }
      }
   };
   shared_ptr(const shared_ptr & r) : data(r.data) {
       if (data)
          ++used[data];
   };
   shared_ptr& operator= (const shared_ptr & r) {
      shared_ptr tmp(r);
	  swap(tmp);
      return * this;
   };
   void swap(shared_ptr& r) {
      T *tmp(data);
      data = r.data;
      r.data = tmp;
   };
   void reset() {
      shared_ptr tmp;
	  swap(tmp);
   };
   T* get() const {
      return data;
   };
   T& operator*() const {
      if (data)
         return *data;
      else
         throw std::bad_alloc();
   };
   T* operator->() const {
      return get();
   };
   long use_count() const {
	   return data?used[data]:0;
   };
   bool operator==(const shared_ptr& r) {
      return data == data;
   };
   bool operator!=(const shared_ptr& r) {
      return data != data;
   };
};
cathack píše: je tam problém se statickými položkami v šabloně. resp. kdy se bude volat konstruktor pro statické datové položky v šablonové třídě? stále mi to házelo různé podivné chyby, do kterých jsem se tak zamotal, že jsem to raději vzdal.
Pak staci napsat tohle (to na prednasce nebylo, ale na cvikach se to ke mne dostalo)

Kód: Vybrat vše

template <class T> map<T*, int> shared_ptr<T>::used;
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Re: Zapoctovy test 23.1. 14:00

Příspěvek od cathack »

stinny píše:Tak mi to nedalo ... nechtelo se mi to uplne ladit, ale proste to na danych pripadech nepada, vystupy to hazi rozumny.
dobrý nápad s map. já to řešil neobratně přes vector a pokaždé daný pointer vyhledával.
stinny píše:

Kód: Vybrat vše

template <class T> map<T*, int> shared_ptr<T>::used;
tak toto je to klíčové, co jsem potřeboval!
tak snad příště. :)
Prokop
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 28. 8. 2005 20:22

Vzorove reseni

Příspěvek od Prokop »

Vrorove resene jako trida a bez operatoru != a == (resi se pres fci. get), na strankach ke cviceni Jany Stanclove http://kocour.ms.mff.cuni.cz/~stanclova ... index.html
Odpovědět

Zpět na „2006“