DIG Digital Corner
Alles wat je altijd al over computers, hardware, software, internet en elektronische gadgets had willen weten, maar niet op Tweakers.net durft te vragen.
Ik loop weer ergens mee vast. Wat ik wil doen is de vereniging van twee willekeurig grote verzamelingen bepalen. De verzamelingen codeer ik als vectors. Het idee van de code is als volgt. Stel ik wil de vereniging van vector a en van b. Dan definieer ik een vector c die bestaat uit alle elementen uit b, en alle elementen uit a die niet in b zitten (zodat ik geen duplicaten creëer).
Ik heb er een hele tijd naar zitten staren, en gedebugged, maar ik kan maar niet de fout vinden in mijn code.
Zou natuurlijk als output de vector [3,4,0,45,55,66] moeten geven. Maar ik krijg [3,4,0,55,55,1112944187]
Ik heb er een hele tijd naar zitten staren, en gedebugged, maar ik kan maar niet de fout vinden in mijn code.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> #include <vector> using namespace std; vector<int> vereniging(vector<int> a, vector<int> b) { vector<int> c=b; for(int k=0; k<a.size(); k++) { int check=-1; int l(0); for(l=0; l<b.size(); l++) { if(a[l]==b[k]) { check++; break; } } if(check<0) { c.push_back(a[k]); } } return c; } int main() { int a[]={3,0,45,55,66}; vector<int> m; m.assign(a,a+5); int b[]={3,4}; vector<int> n; n.assign(b,b+2); cout << vereniging(m,n)[0] << endl << vereniging(m,n)[1] << endl << vereniging(m,n)[2] << endl<< vereniging(m,n)[3] << endl << vereniging(m,n)[4] << endl << vereniging(m,n)[5]; } |
Zou natuurlijk als output de vector [3,4,0,45,55,66] moeten geven. Maar ik krijg [3,4,0,55,55,1112944187]
STL heeft een datatype set, zou je ook kunnen gebruiken.quote:Op woensdag 1 augustus 2012 23:58 schreef thenxero het volgende:
Ik loop weer ergens mee vast. Wat ik wil doen is de vereniging van twee willekeurig grote verzamelingen bepalen. De verzamelingen codeer ik als vectors.
Wat zijn de voordelen van dat datatype? Kan je daar wel makkelijk verenigingen mee maken?quote:
[..]
STL heeft een datatype set, zou je ook kunnen gebruiken.
En ik wil alsnog wel graag weten wat er mis is met mijn code, heb er echt uren naar zitten turen
Jouw code heeft looptijd O(nm), een verzamelingendatatype kan het in O((n+m)log(n+m)).quote:
[..]
Wat zijn de voordelen van dat datatype? Kan je daar wel makkelijk verenigingen mee maken?
Weet je wat copy-constructors zijn en waar ze in je code impliciet aangeroepen worden?quote:
OK dat moet ik dan maar gaan bestuderen. Zie je zo snel geen fout in mijn algoritme?
Nee.quote:
[..]
Weet je wat copy-constructors zijn en waar ze in je code impliciet aangeroepen worden?
edit; even snel gegoogled, bedoel je de regel: vector<int> c=b;?
.
Onder andere, maar ook bijvoorbeeld in de functie-aanroep worden ze gebruikt, en in het returnen van die vector.quote:
[..]
Nee.
edit; even snel gegoogled, bedoel je de regel: vector<int> c=b;?
Punt is dat je die vectors beter als reference kunt passen in de functie, maar daar zit de fout op zich niet. Die zit namelijk hier:
Je hebt k en l verwisseld.
| 1 | if(a[l]==b[k]) |
O M Gquote:
Punt is dat je die vectors beter als reference kunt passen in de functie, maar daar zit de fout op zich niet. Die zit namelijk hier:
[ code verwijderd ]
Je hebt k en l verwisseld.
. Bedankt!Ik snap niet echt wat je bedoeld met die reference. Ik weet net pas wat pointers zijn, waar ik ook het nut nog niet echt van snap.
Okee, dan zou ik me daar ook over inlezen, dit soort dingen zijn zo ongeveer hétgene waar C++ van aan elkaar hangt.quote:
[..]
O M G
Ik snap niet echt wat je bedoeld met die reference. Ik weet net pas wat pointers zijn, waar ik ook het nut nog niet echt van snap.
Dit is wel een goede bron voor de basics van C++ (aangenomen dat je enigszins met C bekend bent): http://www.drbio.cornell.(...)one-html/Frames.html
Als hij nog niet zoveel van pointers weet dan is hij eigenlijk niet bekend met Cquote:
[..]
Okee, dan zou ik me daar ook over inlezen, dit soort dingen zijn zo ongeveer hétgene waar C++ van aan elkaar hangt.
Dit is wel een goede bron voor de basics van C++ (aangenomen dat je enigszins met C bekend bent): http://www.drbio.cornell.(...)one-html/Frames.html
Bedankt. Ik ben niet bekend met C. Het enige wat ik weet is alles wat hier staat, tot het over pointers gaat. Ik heb daarmee nu de eerste 10 problemen van PE opgelost, dus ik wil nu weer verder leren.quote:
[..]
Okee, dan zou ik me daar ook over inlezen, dit soort dingen zijn zo ongeveer hétgene waar C++ van aan elkaar hangt.
Dit is wel een goede bron voor de basics van C++ (aangenomen dat je enigszins met C bekend bent): http://www.drbio.cornell.(...)one-html/Frames.html
Ik zal het een keer gaan lezen en dan zie ik wel hoe ver ik kom.
Voor een goede pointer uitleg kun je ook op youtube kijken dan moet je even zoeken naar pointer fun ik zit nu op mijn mobiel alleen dan doet youtube raar als ik de link van het filmpje wil. Een reference is eigenlijk een soort pointer, hij wijst naar een bepaald object die je vervolgens kan bewerken (is heel handig als functies bijvoorbeeld wat toe moeten voegen aan een vector)
Beware of the Raping Zebra's
Een reference is een pointer waarbij je in de notatie het sterretje weglaat. Andere verschillen: een reference kan niet 0 zijn, moet direct geïnitialiseerd worden, en kan daarna niet veranderd worden.
Een toepassing van references in jouw code zou bijvoorbeeld kunnen zijn dat je
vervangt door
In het bovenste geval worden er bij het doorgeven van de vectoren copy-constructors op a en b uitgevoerd, en destructors bij het verlaten van de functie. In het onderste geval worden er references naar reeds bestaande vectoren doorgegeven, en hoeven er op a en b geen constructors of destructors te worden uitgevoerd.
| 1 | vector<int> vereniging(vector<int> a, vector<int> b) |
| 1 | vector<int> vereniging(vector<int>& a, vector<int>& b) |
quote:
[...] een reference kan niet 0 zijn [...]
| 1 | int const &a = 0; |
"Slechts diegene mag slopen die iets beters kan bouwen."
Okee, okee, maar de C++ standaard definieert geen null references, in tegenstelling tot Java, waar references null by default zijn en ook kunnen veranderen.quote:
Neem dan ook gelijk een constant reference, is wat netter.quote:
Een toepassing van references in jouw code zou bijvoorbeeld kunnen zijn dat je
[ code verwijderd ]
vervangt door
[ code verwijderd ]
In het bovenste geval worden er bij het doorgeven van de vectoren copy-constructors op a en b uitgevoerd, en destructors bij het verlaten van de functie. In het onderste geval worden er references naar reeds bestaande vectoren doorgegeven, en hoeven er op a en b geen constructors of destructors te worden uitgevoerd.
Wordt de code daar sneller door? Of wat zijn anders de voordelen?quote:
Een toepassing van references in jouw code zou bijvoorbeeld kunnen zijn dat je
[ code verwijderd ]
vervangt door
[ code verwijderd ]
In het bovenste geval worden er bij het doorgeven van de vectoren copy-constructors op a en b uitgevoerd, en destructors bij het verlaten van de functie. In het onderste geval worden er references naar reeds bestaande vectoren doorgegeven, en hoeven er op a en b geen constructors of destructors te worden uitgevoerd.
In het algemeen wel, al kan het nooit kwaad om het te testen.quote:
[..]
Wordt de code daar sneller door?
quote:
Voor een goede pointer uitleg kun je ook op youtube kijken dan moet je even zoeken naar pointer fun
in C++ heb je trouwens iets veel beters dan malloc
Daar kan je gewoon dit doen:
int *iptr = new int;
ipv
int *iptr = malloc(sizeof(int));
Daar kan je gewoon dit doen:
int *iptr = new int;
ipv
int *iptr = malloc(sizeof(int));
Ja zo heb ik het ook geleerd. Dat malloc vond ik al vaag, maar dat is dus voor C.quote:
in C++ heb je trouwens iets veel beters dan malloc
Daar kan je gewoon dit doen:
int *iptr = new int;
ipv
int *iptr = malloc(sizeof(int));
Ja er bestaat er ook een voor c++ het enige verschil is dat malloc word vervangen door new
Beware of the Raping Zebra's
Let daarmee op dat je in C++ 2 soorten "free()" hebt!! Als je het verkeerd doet, krijg je memory leaks...
versus
| 1 2 3 4 5 6 7 | int *a = new int; int *b = new int[10]; // ... delete a; delete[] b; |
versus
| 1 2 3 4 5 6 7 | int *a = (int*)malloc(sizeof(int)); int *b = (int*)malloc(sizeof(int)*10); //... free(a); free(b); |
Het is niet vaag. Het enigste wat het doet is memory alloceren voor waar de integer in geplaatst kan worden. Met sizeof(int) vraagt hij de grootte op van een integer in bytes. Met malloc reserveerd hij vervolgens dus die grootte.quote:
[..]
Ja zo heb ik het ook geleerd. Dat malloc vond ik al vaag, maar dat is dus voor C.
Klopt idd alleen is new veel duidelijker en overzichtelijker in gebruik
Beware of the Raping Zebra's
Het nut daarvan begrijp ik nog niet echt...quote:
Let daarmee op dat je in C++ 2 soorten "free()" hebt!! Als je het verkeerd doet, krijg je memory leaks...
[ code verwijderd ]
versus
[ code verwijderd ]
En was het niet zo dat je delete[] bij alles kon gebruiken?
| 1 2 | int *i = new int; delete[] i; |
Oh wacht is het mogelijk om dit te doen?
| 1 2 3 4 | int *i = new int[4]; delete &i[3]; delete[] &i[1]; delete i; |
