εκμάθηση STL

jtsc21 · 15 Ιουλίου 2010

Όπως λέει και ο τίτλος, θέλω να μάθω και να εμβαθύνω στην STL της C++. Μέχρι τώρα έχω διαβάσει από διάφορα sites (γοογλινγκ) αλλά θα προτιμούσα κάποιο περιεκτικό βιβλίο. Η αλήθεια είναι ότι πελάγωσα λίγο..

Οι γνώσεις μου σε C++ (εκτός STL) είναι αρκετά καλές, οπότε δε θα με πείραζε και κάτι λίγο πιο advanced.

Σκοπός μου είναι να αποκτήσω ευχέρεια με την STL καθώς μέχρι τώρα δεν την πολυχρησιμοποιούσα.

//btw εσείς κατά πόσο την χρησιμοποιείτε??

V.I.Smirnov · 15 Ιουλίου 2010

Tα βιβλία αναφοράς για τα templates και την STL είναι του Ν. Μ. Josuttis και μάλιστα εδώ και δέκα χρόνια :

http://www.amazon.com/Standard-Library-Tutorial-Reference/dp/0201379260/ref=sr_1_1?s=books&ie=UTF8&qid=1279164099&sr=1-1

http://www.amazon.com/Templates-Complete-Guide-David-Vandevoorde/dp/0201734842/ref=cm_cr_pr_sims_t

Oι δεκάδες θετικές κριτικές σημαίνουν πολλά...

Τα έχω και ηλεκτρονικά.

Πώς ασχολείσαι με την STL και δεν τα ξέρεις ;

Κακώς διαβάζεις πρώτα από sites.

Η βιβλιογραφία πρέπει να είναι η πρώτη πηγή για σοβαρή μελέτη. Εξάλλου και τα sites από βιβλία όπως τα παραπάνω αντλούν το υλικό τους

Και μού κάνει εντύπωση που πολλοί εδώ ρωτούν τι και από πού να διαβάσουν ενώ με μια

ματιά στο amazon μπορούνε να δουν αμέσως τι κυκλοφορεί και ποιο είναι το καταλληλότερο.

Πέραν αυτών, η STL ΔΕΝ είναι η καλύτερη λύση από πλευράς επιδόσεων τόσο σε ταχύτητα όσο και σε μνήμη.

Ο κύριος σκοπός της είναι να καλύπτει με βολικό τρόπο μια πληθώρα περιπτώσεων χρήσης δομών δεδομένων.

Oι περισσότερες container classes της έχουν γραφεί με τρόπο ώστε να είναι οικονομικές και γρήγορες με την ασυμπτωτική έννοια.

Για εφαρμογές όπου η ταχύτητα είναι σημαντική, η επιβάρυνση που έχει η STL στην ταχύτητα ενίοτε και στην μνήμη,

την καθιστούν ακατάλληλη και συνήθως πρέπει ο προγραμματιστής να ξαναγράψει μόνος του αυτό που χρειάζεται.

Π.χ. η ρουτίνα quick sort που έχει είναι πολύ βραδύτερη (πάνω από 5 φορές) από την κλασσική της C++.

Όταν η μικρότερη ταχύτητα δεν ενοχλεί και δεν αξίζει η φασαρία να γραφεί κάτι που στην STL υπάρχει έτοιμο τότε η STL είναι καλή επιλογή.

Evgenios1 · 15 Ιουλίου 2010

Προσωπικα δε νομιζω να χρειαζεται κανα βιβλιο για τη stl. Ενα manual ειναι οτι πρεπει, πχ

αυτο και αυτο και αλλα πολλα που υπαρχουν.

ΥΓ: Να αποφευγεις το "using namespace std;" βαζε πιο κατω απο τα include πχ "using std::cin;"

jtsc21 · 15 Ιουλίου 2010

Tα βιβλία αναφοράς για τα templates και την STL είναι του Ν. Μ. Josuttis και μάλιστα εδώ και δέκα χρόνια :

http://www.amazon.com/Standard-Library-Tutorial-Reference/dp/0201379260/ref=sr_1_1?s=books&ie=UTF8&qid=1279164099&sr=1-1

http://www.amazon.com/Templates-Complete-Guide-David-Vandevoorde/dp/0201734842/ref=cm_cr_pr_sims_t

Oι δεκάδες θετικές κριτικές σημαίνουν πολλά...

Τα έχω και ηλεκτρονικά.

Πώς ασχολείσαι με την STL και δεν τα ξέρεις ;

Κακώς διαβάζεις πρώτα από sites.

Η βιβλιογραφία πρέπει να είναι η πρώτη πηγή για σοβαρή μελέτη. Εξάλλου και τα sites από βιβλία όπως τα παραπάνω αντλούν το υλικό τους

Και μού κάνει εντύπωση που πολλοί εδώ ρωτούν τι και από πού να διαβάσουν ενώ με μια

ματιά στο amazon μπορούνε να δουν αμέσως τι κυκλοφορεί και ποιο είναι το καταλληλότερο.

Πέραν αυτών, η STL ΔΕΝ είναι η καλύτερη λύση από πλευράς επιδόσεων τόσο σε ταχύτητα όσο και σε μνήμη.

Ο κύριος σκοπός της είναι να καλύπτει με βολικό τρόπο μια πληθώρα περιπτώσεων χρήσης δομών δεδομένων.

Oι περισσότερες container classes της έχουν γραφεί με τρόπο ώστε να είναι οικονομικές και γρήγορες με την ασυμπτωτική έννοια.

Για εφαρμογές όπου η ταχύτητα είναι σημαντική, η επιβάρυνση που έχει η STL στην ταχύτητα ενίοτε και στην μνήμη,

την καθιστούν ακατάλληλη και συνήθως πρέπει ο προγραμματιστής να ξαναγράψει μόνος του αυτό που χρειάζεται.

Π.χ. η ρουτίνα quick sort που έχει είναι πολύ βραδύτερη (πάνω από 5 φορές) από την κλασσική της C++.

Όταν η μικρότερη ταχύτητα δεν ενοχλεί και δεν αξίζει η φασαρία να γραφεί κάτι που στην STL υπάρχει έτοιμο τότε η STL είναι καλή επιλογή.

Δεν ασχολούμαι με STL τώρα είπα να αρχήσω, απλά έχω δει 1-2 πολύ σύντομα tutorials . Όσον αφορά σχετικά με την άποψη σου για τα βιβλία (ότι πρέπει να είναι η πρώτη πηγή για σοβαρή μελέτη) συμφωνώ απόλυτα.

Το 1ο βιβλίο που παραθέτεις το είχα "σταμπάρει" και εγώ. Το 2ο δεν το ήξερα. Για αυτό ρώτησα ώστε να επιλέξω κάποιο και να μην το πάρω στα "τυφλά".

Προσωπικα δε νομιζω να χρειαζεται κανα βιβλιο για τη stl. Ενα manual ειναι οτι πρεπει, πχ
αυτο και αυτο και αλλα πολλα που υπαρχουν.

ΥΓ: Να αποφευγεις το "using namespace std;" βαζε πιο κατω απο τα include πχ "using std::cin;"

thanks για τις απαντήσεις σας!

jstark · 15 Ιουλίου 2010

Tα βιβλία αναφοράς για τα templates και την STL είναι του Ν. Μ. Josuttis και μάλιστα εδώ και δέκα χρόνια :

Πέραν αυτών, η STL ΔΕΝ είναι η καλύτερη λύση από πλευράς επιδόσεων τόσο σε ταχύτητα όσο και σε μνήμη.

Ο κύριος σκοπός της είναι να καλύπτει με βολικό τρόπο μια πληθώρα περιπτώσεων χρήσης δομών δεδομένων.

Oι περισσότερες container classes της έχουν γραφεί με τρόπο ώστε να είναι οικονομικές και γρήγορες με την ασυμπτωτική έννοια.

Για εφαρμογές όπου η ταχύτητα είναι σημαντική, η επιβάρυνση που έχει η STL στην ταχύτητα ενίοτε και στην μνήμη,

την καθιστούν ακατάλληλη και συνήθως πρέπει ο προγραμματιστής να ξαναγράψει μόνος του αυτό που χρειάζεται.

Π.χ. η ρουτίνα quick sort που έχει είναι πολύ βραδύτερη (πάνω από 5 φορές) από την κλασσική της C++.

Όταν η μικρότερη ταχύτητα δεν ενοχλεί και δεν αξίζει η φασαρία να γραφεί κάτι που στην STL υπάρχει έτοιμο τότε η STL είναι καλή επιλογή.

Έχεις κάποια παραπομπή; Από αυτά που έχω δει, η sort της C++ δεν ειναι καθόλου αργή σε σχέση με την qsort της C, αν αυτό εννοούσες. Εκτός και αν έπεσες πάνω σε κάποιο περίεργο implementation.

V.I.Smirnov · 16 Ιουλίου 2010

Έχεις κάποια παραπομπή; Από αυτά που έχω δει, η sort της C++ δεν ειναι καθόλου αργή σε σχέση με την qsort της C, αν αυτό εννοούσες. Εκτός και αν έπεσες πάνω σε κάποιο περίεργο implementation.

H ακαταλληλότητα της STL σε κρίσιμα ως προς την ταχύτητα και την μνήμη τμήματα εφαρμογών εκτιμάται κατά περίπτωση.

Π.χ. στο "3d game engine architecture Real time applications with wild magic", D. Eberly,

ο συγγραφέας εξηγεί (1η έκδοση, σελ. 32) γιατί ΔΕΝ χρησιμοποιεί τις έτοιμες κλάσσεις της STL :

Με την δική του υλοποίηση

α) η εκτέλεση είναι ταχύτερη,

β) κερδίζει περισσότερο από 40% σε μνήμη.

Ειδικά για την βραδύτητα της quick sort στην STL δεν έχω προσωπική εμπειρία αλλά το λέει (και) άλλος που δοκίμασε :

http://www.insomnia.gr/forum/showthread.php?t=372625&highlight=quick+sort

Πλήρως τεκμηριωμένη σύγκριση δεν έχω υπόψη μου.

NewProject · 16 Ιουλίου 2010

φυσικα και το κανει μιας και φτιαχνει τις δικες του κλασεις με βαση τις δικες του αναγκες και τις αναγκες του project σε αντιθεση με το STL το οποιο ειναι general purpose

V.I.Smirnov · 16 Ιουλίου 2010

φυσικα και το κανει μιας και φτιαχνει τις δικες του κλασεις με βαση τις δικες του αναγκες και τις αναγκες του project σε αντιθεση με το STL το οποιο ειναι general purpose

Ακριβώς, είναι προφανές.

Αν δεν αξίζει να φτιαχτεί κάτι από άποψη κόπου/χρόνου/κόστους, είναι πολύ βολική.

Αλλιώς πρέπει να ξαναφτιάξεις τον τροχό που χρειάζεσαι...

jstark · 16 Ιουλίου 2010

H ακαταλληλότητα της STL σε κρίσιμα ως προς την ταχύτητα και την μνήμη τμήματα εφαρμογών εκτιμάται κατά περίπτωση.
Π.χ. στο "3d game engine architecture Real time applications with wild magic", D. Eberly,

ο συγγραφέας εξηγεί (1η έκδοση, σελ. 32) γιατί ΔΕΝ χρησιμοποιεί τις έτοιμες κλάσσεις της STL :

Με την δική του υλοποίηση

α) η εκτέλεση είναι ταχύτερη,

β) κερδίζει περισσότερο από 40% σε μνήμη.

Ειδικά για την βραδύτητα της quick sort στην STL δεν έχω προσωπική εμπειρία αλλά το λέει (και) άλλος που δοκίμασε :

http://www.insomnia.gr/forum/showthread.php?t=372625&highlight=quick+sort

Πλήρως τεκμηριωμένη σύγκριση δεν έχω υπόψη μου.

Τα σχόλιά μου:

1. Η compare function που χρησιμοποιεί ο Ευγένιος δεν φαίνεται να ειναι σωστά γραμμένη, μιας και δεν επιστρέφει τις τρεις προβλεπόμενες τιμές (1, -1, 0).

2. Δε γίνεται χρήση της δυνατότητας inlining που παρέχει η C++, χρησιμοποιώντας function object στιν std::sort.

Στο δικό μου μηχανάκι η std::sort είναι 2-3 φορές ταχύτερη της qsort. Το άλλο βιβλίο που παραθέτεις δεν το έχω διαβάσει, αλλά θα το τσεκάρω.

V.I.Smirnov · 16 Ιουλίου 2010

Τα σχόλιά μου:

1. Η compare function που χρησιμοποιεί ο Ευγένιος δεν φαίνεται να ειναι σωστά γραμμένη, μιας και δεν επιστρέφει τις τρεις προβλεπόμενες τιμές (1, -1, 0).

2. Δε γίνεται χρήση της δυνατότητας inlining που παρέχει η C++, χρησιμοποιώντας function object στιν std::sort.

Στο δικό μου μηχανάκι η std::sort είναι 2-3 φορές ταχύτερη της qsort. Το άλλο βιβλίο που παραθέτεις δεν το έχω διαβάσει, αλλά θα το τσεκάρω.

Για τα 1, 2 δεν έχω προσωπική άποψη - πιθανόν έχεις δίκιο.

Αλλά γενικά αυτό που είπε (και) ο NewProject είναι αλήθεια.

Για το βιβλίο που ανέφερα δες το αντίστοιχο απόσπασμα που εσωκλείω.

Επεδή ξέρω ότι o συγγραφέας ανήκει στις κορυφές των κορυφών δεν αμφισβητώ την επιλογή του, τουλάχιστον για την μηχανή γραφικών που έφτιαξε και αναλύει.

Evgenios1 · 16 Ιουλίου 2010

Τα σχόλιά μου:

1. Η compare function που χρησιμοποιεί ο Ευγένιος δεν φαίνεται να ειναι σωστά γραμμένη, μιας και δεν επιστρέφει τις τρεις προβλεπόμενες τιμές (1, -1, 0).

2. Δε γίνεται χρήση της δυνατότητας inlining που παρέχει η C++, χρησιμοποιώντας function object στιν std::sort.

Στο δικό μου μηχανάκι η std::sort είναι 2-3 φορές ταχύτερη της qsort. Το άλλο βιβλίο που παραθέτεις δεν το έχω διαβάσει, αλλά θα το τσεκάρω.

Τι να πω. Τωρα που εφτιαξα ενα τεστ σε 0χ παλι το ιδιο μου βγαζει. Να και ο κωδικας που μπορει να εχει και bugs..

>// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define use using std::

use cout;
use cin;
use endl;
use string;
use for_each;
use sort;
use vector;

int comp(const void* i,const void* x)
{
return ( *(int*)i < *(int*)x );
}
int _tmain(int argc, _TCHAR* argv[])
{
const unsigned size = 0x000fffff;
clock_t start;
vector<int> v(size);
int *arr;
for_each(v.begin(),v.end(),[](int& i)
{
	i = rand();
});
start = clock();

sort(v.begin(),v.end(),[](int y,int x)-> bool
{
	return x<y;
});

cout<<"std:\t"<<clock()-start<<endl;
v.clear();

arr = new int[size];
for_each(arr,arr+size,[](int& i){
	i=rand();
});
start = clock();
qsort(arr,size,4,comp);
cout<<"c std:\t"<<clock()-start<<endl;
cin.get();
delete []arr;
return 0;
}

ΥΓ: Σου βγαζει σωστα αποτελεσματα; Ποσταρε αυτο που εκανες.

jstark · 16 Ιουλίου 2010

Τι να πω. Τωρα που εφτιαξα ενα τεστ σε 0χ παλι το ιδιο μου βγαζει. Να και ο κωδικας που μπορει να εχει και bugs..
>// test.cpp : Defines the entry point for the console application.
//

int comp(const void* i,const void* x)
{
return ( *(int*)i < *(int*)x );
}

Για την comp, δοκίμασε να την γράψεις έτσι:

>int comp(const void* i,const void* x)
{
       int i1 = *(int *)i;
       int i2 = *(int *)x;

       // to parakatw if, mporeis na to antikatastiseis kai me r[b]eturn i1-i2[/b];
       if (i1 > i2) return 1;
       else if (i1 < i2) return -1;
       else return 0;
}
}

$ man qsort

...

The comparison function must return an integer less than, equal to, or

greater than zero if the first argument is considered to be respectively

less than, equal to, or greater than the second.

Evgenios1 · 16 Ιουλίου 2010

Εγινε πιο αργη η qsort . Αλλα παλη πιο γρηγορη απο την sort.

ΥΓ: Ανεβασε αυτο που εκανες

jstark · 16 Ιουλίου 2010

Εγινε πιο αργη η qsort . Αλλα παλη πιο γρηγορη απο την sort.
ΥΓ: Ανεβασε αυτο που εκανες

Δεν εχω compiler στο pc που ειμαι, αλλα κατι τετοιο ειχα γραψει:

cpp:

>#define MAX_LEN 500000000

struct comp {
       bool operator() (const double a, const double  const {
               return a > b;
       }
};

int main(int argc, char *argv[])
{
       double *d = new double[MAX_LEN];

       for (int i = 0; i < MAX_LEN; ++i)
       {
               d[i] = rand();
       }

       std::cout << "sorting...\n";
       time_t t0, t1;
       time(&t0);
       std::sort(d, d+MAX_LEN, comp());
       time(&t1);
       std::cout << "t1-t0 = " << (t1-t0) << std::endl;
       delete[] d;
       return 0;
}

c:

>
#define MAX_LEN 500000000

int comp(const void *p1, const void *p2)
{
       double *p = (double *)p1;
       double *q = (double *)p2;
       if (*p < *q) return 1;
       else if (*p > *q) return -1;
       else return 0;
}

int main(int argc, char *argv[])
{
       double *d = malloc(MAX_LEN*sizeof(double));

       int i = 0;
       for (i = 0; i < MAX_LEN; ++i)
       {
               d[i] = rand();
       }

       printf("sorting:...\n");
       time_t t0, t1;
       time(&t0);
       qsort(d, MAX_LEN, sizeof(double), comp);
       time(&t1);
       printf("t1-t0 = %ld\n", (t1-t0));
       free(d);
       return 0;
}

m1cRo · 16 Ιουλίου 2010

Η STL δεν επηρεάζει τις επιδόσεις του προγράμματος. Τις επιδόσεις τις επηρεάζει ο αλγόριθμος που χρησιμοποιείς. Αν πάρεις έτοιμο αλγόριθμο τις STL τότε ναι ίσος να είναι πιο argos αν και αμφιβάλλω για αυτό. Η STL δεν είναι ένα framework είναι κομμάτι της γλώσσας. Η όλη επιβάρυνση της stl πέφτει στο compile time και όχι στο runtime. Βεβαια παρα πολλοί πιστεύουν ότι η STL είναι μια βιβλιοθήκη που απλά έχει το vector και την map, μεγάλο λάθος....

Επίσης καλο είναι να μην συγκρίνουμε κώδικα c και c++ γιατί είναι γνωστό ότι ο GCC δεν είναι και ο καλύτερος C++ compiler αντίθετος δεν έχει κανένα πρόβλημα με c.

Σύνδεση

εκμάθηση STL

Προτεινόμενες αναρτήσεις

jtsc21

V.I.Smirnov

Evgenios1

jtsc21

jstark

V.I.Smirnov

NewProject

V.I.Smirnov

jstark

V.I.Smirnov

Evgenios1

jstark

Evgenios1

jstark

m1cRo

Αρχειοθετημένο

Σύνδεση