Generic/Abstract Programming με C

[migf1]

Θεώρησα χρήσιμο να ανοίξω νέο νήμα για αυτό το αντικείμενο, με αφορμή τη σχετική κουβέντα στο γενικό νήμα της C. Οπότε τα πρώτα posts είναι απλώς αντιγραφή από εκεί.

 

Μόνο δώστε μου λίγο χρόνο να τα αντιγράψω... done

 

-----------------------------------------------------------------------------

 

Από Δημοσίευση #1127 (migf1)

 

 

 

...

Και κατι ακομα, ασχετο με τα προηγουμενα( που μου ηρθε φλασια), σχετικο ομως με τη C , που αμα αρχισεις δεν μπορεις να σταματησεις ....

 

Εστω οτι εχουμε πχ μια συναρτηση εισαγωγης κομβων στο τελος μιας λιστας η οποια περνει ως ορισμα ενα δεικτη στην αρχη της λιστας, ενα δεικτη στο τελος της λιστας ( "by-ref" και οι δυο ) και ενα int για το field της δομης...

η συναρτηση ειναι αυτη Βοοl Insert( NODE **list , NODE **tail , int data );

Μπορουμε με καποιον τροπο να χρησιμοποιησουμε την ιδια συναρτηση για για ορισματα τυπου ΝΟDE2 **list, NODE2 **tail , float data ;

Δηλαδη να μην ξανα γραφουμε την ιδια συναρτηση για διαφορετικους τυπους δεδομενων ;;

Στη C δεν μπορείς, επειδή δεν επιτρέπει function overloading. Μπορείς να φτιάξεις αν θέλεις ένα ADT Interface (Abstract Data Type Interface) το οποίο όμως κοστίζει πολύ και σε επιδόσεις και σε πολυπλοκότητα ανάπτυξης.

 

 

 

Από όταν είχες κάνει αυτή την ερώτηση ήθελα να σου γράψω ένα μικρό πρόγραμμα που να δείχνει έναν τρόπο του πως μπορείς να κάνεις κάτι παραπλήσιο με C. Μετά έμπλεξα με την C# (ακόμα δεν έχω ξεμπλέξει) μου έτυχε και μια δουλίτσα σε C και έτσι έμεινε πίσω.

 

Σήμερα βρήκα λίγο χρόνο και ορμώμενος από εκείνο το νήμα με την τομή πινάκων, έκανα μια υποτυπώδη βιβλιοθήκη "sets" που τα μόνα που έχει είναι constructors, destructor, ταξινόμηση, αναζήτηση και intersection.

 

Την έκανα όμως να δουλεύει με οποιοδήποτε data-type για τα στοιχεία των sets (τα sets elements δηλαδή).

 

Για τον κάθε τύπο με τον οποίον θέλεις να τη χρησιμοποιήσεις , φτιάχνεις 2 συναρτήσεις: μια που εκτυπώνει την τιμή μιας μεταβλητής του τύπου, και μια που συγκρίνει τις τιμές 2 μεταβλητών του τύπου.

 

Αυτές τις συναρτήσεις τις περνάς ως ορίσματα στις συναρτήσεις της βιβλιοθήκης. Στον constructor του set που θες να δημιουργηθεί με elements του τύπου σου, περνάς και το sizeof του τύπου (το μέγεθος δηλαδή ενός στοιχείου σε bytes). Περνάς και κάτι άλλα, που όμως δεν έχουν να κάνουν με το abstraction που ρώτησες (π.χ. περνάς μια boolean για να ξέρει αν είναι ταξινομημένα τα στοιχεία όταν δημιουργείς το set, αλλιώς τα ταξινομεί... και κάτι τέτοια).

 

Δεν προλαβαίνω τώρα να κάνω αναλυτικό ποστ επεξήγησης (αύριο μάλλον) σου παραθέτω όμως ένα sets_test.c που χρησιμοποιεί την βιβλιοθήκη και διαχειρίζεται ομοιογενώς σύνολα ακεραίων και σύνολα strings, μέσα στο ίδιο πρόγραμμα.

 

 

 

>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <limits.h>

#include "sets.h"

// prepare info for primary-type sets (say int)

typedef int PrimaryElemT;

static const PrimaryElemT elemPrimaryMaxval    = INT_MAX;
char fmttxtPrintPrimaryElem[]            = "%d ";

// prepare info for string sets

#define SIZEOF_StrELEM                ( 20+1 )

typedef char StringElemT;

static const StringElemT elemStringMaxval[sizeOF_StrELEM] = "zzzzzzzzzzzzzzzzzzzz";
static const char *fmttxtPrintStringElem        = "%s ";

static const SetsBool dupsYesNo            = setsNO;

/*****************************************************//**
* Print the value of a primary-typed element
*/
static void cb_print_primaryElement( const void *pElem )
{
   const PrimaryElemT *pelem = (const PrimaryElemT *)pElem;
   if ( pElem ) {
       printf( fmttxtPrintPrimaryElem, *pelem );
       fflush( stdout );
   }
}
/*****************************************************//**
* Compare the values of two primary-typed elements
*/
static int cb_compare_primaryElements( const void *pElem1, const void *pElem2 )
{
   const PrimaryElemT *pelem1 = (const PrimaryElemT *) pElem1;
   const PrimaryElemT *pelem2 = (const PrimaryElemT *) pElem2;

   if ( !pelem1 || !pelem2 )
       return INT_MAX;

   return (*pelem1 > *pelem2) - (*pelem1 < *pelem2);
}
/*****************************************************//**
* Print the value of string element
*/
void cb_print_stringElement( const void *pElem )
{
   const StringElemT *pelem = (const StringElemT *)pElem;
   if ( pElem ) {
       printf( fmttxtPrintStringElem, pelem );
       fflush( stdout );
   }
}
/*****************************************************//**
* Compare the values of two string elements
*/
static int cb_compare_stingElements( const void *pElem1, const void *pElem2 )
{
   const StringElemT *pelem1 = (const StringElemT *) pElem1;
   const StringElemT *pelem2 = (const StringElemT *) pElem2;

   if ( !pelem1 || !pelem2 )
       return INT_MAX;

   return strncmp(pelem1, pelem2, SIZEOF_StrELEM);
}

/*****************************************************//**
*
*********************************************************
*/
int main( void )
{
   // define 3 arrays of strings (to be used for creating & manipulating 3 string sets)
   StringElemT strArr1[4][sizeOF_StrELEM] = {"John", "John", "Mary", "Alex"};
   StringElemT strArr2[3][sizeOF_StrELEM] = {"Tony", "John", "John"};
   StringElemT strArr3[2][sizeOF_StrELEM] = {"John", "John"};

   // define 3 arrays of ints (to be used for creating & manipulating 3 int sets)
   PrimaryElemT primArr1[] = {65, 65, 61, 68};
   PrimaryElemT primArr2[] = {67, 65, 65};
   PrimaryElemT primArr3[] = {65, 65};

   /* -----------------------------------------
    * let's start with the 3 string sets first
    * -----------------------------------------
    */

   size_t len1    = 4;
   size_t len2    = 3;
   size_t len3    = 2;
   Set *set1    = NULL;
   Set *set2    = NULL;
   Set *set3    = NULL;
   Set *result    = NULL;

   sets_setting_dbgmode( setsYES );

   // create and populate 3 unsorted string sets
   set1 = set_new_init( len1, SIZEOF_StrELEM, elemStringMaxval, strArr1, setsFALSE );
   set2 = set_new_init( len2, SIZEOF_StrELEM, elemStringMaxval, strArr2, setsFALSE );
   set3 = set_new_init( len3, SIZEOF_StrELEM, elemStringMaxval, strArr3, setsFALSE );

   // print contents of the 3 string sets
   set_print( set1, "1st set: ", "\n", &cb_print_stringElement );
   set_print( set2, "2nd set: ", "\n", &cb_print_stringElement );
   set_print( set3, "3rd set: ", "\n", &cb_print_stringElement );

   // get and print the intersection of the 3 string sets
   result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_stingElements);
   set_print( result, "Intersection: ", "\n\n", &cb_print_stringElement );

   // free all string sets
   set_free( &set1 );
   set_free( &set2 );
   set_free( &set3 );
   set_free( &result );

   /* -----------------------------------------
    * now let's use the same set & len variables, but for 3 int sets this time
    * -----------------------------------------
    */

   len1 = sizeof(primArr1) / sizeof(primArr1[0]);
   len2 = sizeof(primArr2) / sizeof(primArr2[0]);
   len3 = sizeof(primArr3) / sizeof(primArr3[0]);

   // create and populate 3 unsorted int sets
   set1 = set_new_init( len1, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr1, setsFALSE );
   set2 = set_new_init( len2, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr2, setsFALSE );
   set3 = set_new_init( len3, sizeof(PrimaryElemT), &elemPrimaryMaxval, primArr3, setsFALSE );

   // print contents of the 3 int sets
   set_print( set1, "1st set: ", "\n", &cb_print_primaryElement );
   set_print( set2, "2nd set: ", "\n", &cb_print_primaryElement );
   set_print( set3, "3rd set: ", "\n", &cb_print_primaryElement );

   // get and print the intersection of the 3 int sets
   result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_primaryElements);
   set_print(result, "Intersection: ", "\n\n", &cb_print_primaryElement);

   /* -----------------------------------------
    * since our initial int arrays contained char "compatible" values,
    * let's try to print all the sets and their intersection as char
    * -----------------------------------------
    */

   strncpy(fmttxtPrintPrimaryElem, "%c ", strlen(fmttxtPrintPrimaryElem) );

   set_print( set1, "1st set: ", "\n", &cb_print_primaryElement );
   set_print( set2, "2nd set: ", "\n", &cb_print_primaryElement );
   set_print( set3, "3rd set: ", "\n", &cb_print_primaryElement );
   set_print( result, "Intersection: ", "\n\n", &cb_print_primaryElement );


   // free all int sets
   set_free( &set1 );
   set_free( &set2 );
   set_free( &set3 );
   set_free( &result );

   system( "pause" );
   exit( EXIT_SUCCESS );
}

 

 

 

Ότι βλέπεις να ξεκινάει με "set_" ή με "sets_" ανήκει στην βιβλιοθήκη.

 

Έξοδος:

 

>
1st set: John John Mary Alex
2nd set: Tony John John
3rd set: John John
Intersection: John

1st set: 65 65 61 68
2nd set: 67 65 65
3rd set: 65 65
Intersection: 65

1st set: = A A D
2nd set: A A C
3rd set: A A
Intersection: A

 

-----------------------------------------------------------------------------

 

Από Δημοσίευση #1128 (migf1)

 

Λοιπόν, ας το πάμε λίγο πιο αναλυτικά σήμερα, μιας και νομίζω είναι σημαντικό να γνωρίζει κανείς τις βασικές ιδέες περί generic programming στην C (btw, το function overloading μπορεί να προσομοιωθεί στην C με variadic functions, σε C99 έχουν προστεθεί και variadic macros, ενώ σε C11 έχει προστεθεί και το Type-Generic Selection που συνήθως συνδυάζει το keyword _Generic με macros ως ένα είδος overloading).

 

Σε γενικές γραμμές όμως, καλό είναι να γνωρίζουμε πως για generic programming η C δεν είναι ψηλά στη λίστα των προτιμώμενων γλωσσών.

 

Εξαιρώντας τα macros, ο βασικός μηχανισμός για generic programming με C είναι μέσω δεικτών void (void *). Ο τύπος void όχι μόνο είναι incomplete τύπος αλλά και δεν γίνεται ποτέ complete.

 

Αυτό στην πράξη σημαίνει πως δεν μπορούμε να κάνουμε dereference έναν void δείκτη. Πρέπει πρώτα να τον κάνουμε cast σε έναν complete-type pointer.

 

Π.χ....

 

>
float f = 0.3;
void *pVoid = &f;

printf( "%f\n", *pVoid );  // COMPILE TIME ERROR

 

Ενώ...

 

>
float f = 0.3;
void *pVoid = &f;

printf( "%f\n", *(float *)(char *)pVoid );  // ALL FINE

 

Μια άλλη ιδιαιτερότητα είναι πως εφόσον ο τύπος void δεν έχει size (είναι μονίμως incomplete) δεν μπορούμε να εφαρμόσουμε pointer-arithmetic σε void pointers. EDIT: Όμως το πρότυπο της γλώσσας απαιτεί οι void pointers να είναι συμβατοί με τους char pointers ως προς το pointer arithmetic, οπότε μπορούμε να εφαρμόσουμε χειροκίνητη αριθμητική δεικτών. Ως double safety measure μπορούμε πρώτα να τους κάνουμε cast σε (char *)

Όπως πολύ σωστά παρατήρησε ο imitheos, το πρότυπο απαγορεύει πάντα το void pointer arithmetic. Άρα πρέπει πάντα να τους κάνουμε ΠΑΝΤΑ cast σε (char *) και κατόπιν να εφαρμόσουμε χειροκοκίνητη pointer arithmetic πάνω τους.

 

Π.χ...

 

>
   float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
   void *pVoid = arrFloat;

   printf( "%f\n", pVoid[2] );   // COMPILE TIME ERROR
   printf( "%f\n", *(pVoid+2) ); // COMPILE TIME ERROR
   printf( "%f\n", *(float *)((char *)pVoid+2) ); // NO ERRORS, αλλά δείχνει στον γάμο του καραγκιόζη

 

Στο τελευταίο printf() δεν δείχνει ακριβώς στον γάμο του καραγκιόζη, δείχνει στο 3ο byte από την αρχή του arrFloat (αντί για τον 3ο float που θέλαμε), το οποίο byte θεωρείται κατόπιν λόγω του casting ως έναρξη ενός float αριθμού... οπότε τυπώνει άσχετο πράγμα (αντί για 3.0 που θέλαμε).

 

Για να πάρουμε το επιθυμητό αποτέλεσμα πρέπει να κάνουμε χειροκίνητα τον ακριβή υπολογισμό της θέσης του 3ου στοιχείου, στην αριθμητική του void pointer μας...

 

>
   printf( "%f\n", *(float *)((char *)pVoid + 2*sizeof(float)) );

 

Όπως γράφω και πιο πάνω, EDIT: μπορούμε ως extra safety measure πρέπει να τον κάνουμε πρώτα cast σε (char *) ...

 

αλλά είναι περιττό αν ξέρουμε πως ο compiler μας ακολουθεί πιστά το πρότυπο.

 

Για ευκολία μπορούμε να περιτυλίξουμε τα παραπάνω σε ένα βολικό macro, στο οποίο θα περνάμε τον void pointer, την τιμή του indexer i και τον τύπο στον οποίον αναφέρονται τα δεδομένα μας, και θα μας επιστρέφει την σωστή διεύθυνση casted στον δοθέντα τύπο.

 

Οπότε θα αρκεί απλώς να κάνουμε dereference ότι μας επιστρέφει το εν λόγω macro.

 

Π.χ...

 

>
#include <stdlib.h>

#define PVOID_PLUS_I(pVoid, i, type)    \
   (type *)((char *)(pVoid) + (i) * sizeof(type) )

/*****************************************************//**/
int main( void )
{
   float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
   void *pVoid = arrFloat;

   printf( "%f\n", *PVOID_PLUS_I(pVoid, 2, float) );

   exit( EXIT_SUCCESS );
}

 

Μπορούμε να χρησιμοποιήσουμε κι απευθείας char δείκτες αντί για void, και μάλιστα είναι ουκ ολίγοι οι κώδικες που χρησιμοποιούν char δείκτες αντί για void.

 

Με char δείκτες αντί για void ο παραπάνω κώδικας δείχνει κάπως έτσι...

 

>
#include <stdlib.h>

#define ARRTYPE_PLUS_I(arr, i, type)    \
   (type *)((char *)(arr) + (i) * sizeof(type) )

/*****************************************************//**
*
*********************************************************
*/
int main( void )
{
   float arrFloat[5] = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
   char *pChar = (char *)arrFloat;

   printf( "%f\n", *ARRTYPE_PLUS_I(pChar, 2, float) );

   exit( EXIT_SUCCESS );
}

 

Η βασική διαφορά είναι πως κάνουμε εξαρχής cast τον δείκτη όταν του αναθέτουμε ως τιμή τη διεύθυνση του πίνακα, αλλιώς παραπονιέται ο compiler (ως warning όμως, όχι ως error... εξακολουθεί να λειτουργεί σωστά).

 

Πάνω σε αυτά λοιπόν βασίζεται κι αυτή η υποτυπώδης βιβλιοθήκη που έφτιαξα ως παράδειγμα. Πέρα από τα παραπάνω, δείχνει επίσης κι έναν απλό τρόπο υλοποίησης του information hiding σε C.

 

Λίγο αργότερα όμως, σε άλλο ποστ...

 

EDIT: typos + διορθώσεις περί προτύπου, κατόπιν σωστής παρατήρησης του imitheoy.

 

-----------------------------------------------------------------------------

 

Από Δημοσίευση #1129 (imitheos)

 

 

Αν και είναι γνωστό πόσο συμπαθώ τα macro και ειδικά σε περιπτώσεις όπως αυτή που κάνουμε μπακάλικα με ματσακονιές κάτι που γίνεται εύκολα και δόκιμα σε άλλες γλώσσες, παρόλα αυτά ωραίος. Περιμένουμε και το επόμενο μέρος.

 

Μια άλλη ιδιαιτερότητα είναι πως εφόσον ο τύπος void δεν έχει size (είναι μονίμως incomplete) δεν μπορούμε να εφαρμόσουμε pointer-arithmetic σε void pointers. Όμως το πρότυπο της γλώσσας απαιτεί οι void pointers να είναι συμβατοί με τους char pointers ως προς το pointer arithmetic, οπότε μπορούμε να εφαρμόσουμε χειροκίνητη αριθμητική δεικτών.

 

Π.χ...

 

printf( "%f\n", *(float *)(pVoid+2) ); // NO ERRORS, αλλά δείχνει στον γάμο του καραγκιόζη

 

printf( "%f\n", *(float *)(pVoid + 2*sizeof(float)) ); // ALL FINE

 

 

Όπως γράφω και πιο πάνω, μπορούμε ως extra safety measure να τον κάνουμε πρώτα cast σε (char *) ...

 

printf( "%f\n", *(float *)((char *)pVoid + 2*sizeof(float)) );

 

 

αλλά είναι περιττό αν ξέρουμε πως ο compiler μας ακολουθεί πιστά το πρότυπο.

 

Για να γίνω grammar nazi άλλη μια φορά, είσαι σίγουρος για αυτό ? Συμφωνώ με το 1ο που είπες ότι απαγορεύεται η αριθμητική σε void δείκτες όχι όμως με το 2ο. Αυτό που θυμάμαι είναι ότι οι void δείκτες πρέπει να έχουν όχι ίδια αριθμητική αλλά ίδια αναπαράσταση με τους δείκτες σε char. Αυτό το γεγονός εκμεταλλεύονται πολλοί compilers και επιτρέπουν αριθμητική void δεικτών με αύξηση κατά 1 byte σαν να ήταν δείκτες σε char και έτσι μπορούμε όντως να έχουμε την "χειροκίνητη" αριθμητική που ανέφερες. Αυτό όμως είναι επέκταση κάποιων compilers.

 

 

GCC Manual έγραψε:

In GNU C, addition and subtraction operations are supported on pointers to void and on pointers to functions. This is done by treating the size of a void or of a function as 1.

 

A consequence of this is that sizeof is also allowed on void and on function types, and returns 1.

 

>
% for i in c89 c99 c11; do
> gcc -Wall -std=$i -pedantic tmp.c
> done
tmp.c: In function ‘main’:
tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic]
tmp.c: In function ‘main’:
tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic]
tmp.c: In function ‘main’:
tmp.c:8:34: προειδοποίηση: pointer of type ‘void *’ used in arithmetic [-pedantic]

 

-----------------------------------------------------------------------------

 

Από Δημοσίευση #1130 (migf1)

 

Σε συνέχεια του προηγούμενου post, μια πολύ συνηθισμένη χρήση του abstraction που περιγράφω παραπάνω είναι όταν καλούμε τις συναρτήσεις memXXX() της <stdlib.h>...

 

>
void *memset(void *buffer, int c, size_t size);
void *memcpy(void *restrict dst, const void *restrict src, size_t size); 
void *memmove(void *dst, const void *src, size_t size); 

 

Όπως παρατηρούμε στα πρότυπα των συναρτήσεων, όλες ορίζουν με δείκτες void (void *) τα buffers που περιμένουν. Επίσης αναμένουν ως όρισμα και το συνολικό μέγεθος του buffer σε bytes.

 

Μια πιθανή υλοποίηση ας πούμε της memcpy() θα μπορούσε να είναι κάπως έτσι (αγνοώ τα restrict για να μην μπερδεύουν χωρίς λόγο την συζήτησή μας)...

 

>
void *myMemcpy(void *dst, const void * src, size_t size)
{
   void *ret = dst;
   while (size--) {
       *(char *)dst = *(char *)src;
       dst = (char *)dst + 1;
       src = (char *)src + 1;
   }
   return ret;
}

 

δηλαδή να γίνονται οι void δείκτες treat ως char δείκτες, προκειμένου να μπορούν να γίνουν dereferenced οι τιμές τους κατά την διαδικασία της αντιγραφής από το src buffer στο dst buffer, αλλά και για να μπορεί να εφαρμοστεί αριθμητική δεικτών πάνω τους ( εκείνα τα +1 ).

 

Αυτές οι συναρτήσεις δεν χρειάζεται να συγκρίνουν μεταξύ τους τα στοιχεία των buffers που διαχειρίζονται. Όταν χρειάζεται να γίνει σύγκριση στοιχείων, τότε υπάρχει δυσκολία.

 

Καταρχήν πρέπει η συνάρτηση να γνωρίζει το μέγεθος του κάθε στοιχείου. Έπειτα χρειάζεται να ξέρει πως νοείται η σύγκριση 2 στοιχείων, διότι για παράδειγμα αλλιώς συγκρίνονται μεταξύ τους 2 int στοιχεία, αλλιώς 2 string στοιχεία κι αλλιώς 2 στοιχεία που είναι ας πούμε nodes μιας συνδεδεμένης λίστας.

 

Τις πληροφορίες που χρειάζεται μια τέτοια generic συνάρτηση τις περιμένει στα ορίσματά της. Το πιο χαρακτηριστικό παράδειγμα εδώ είναι και πάλι μια συνάρτηση της <stdlib>, η qsort() που ταξινομεί όποιο buffer της περάσουμε.

 

Το πρότυπό της είναι το εξής...

 

>
void qsort(
   void *buffer,
   size_t nelems,
   size_t elemSize,
   int (*compare)(const void *, const void *)
); 

 

Δηλαδή η συνάρτηση θέλει να ξέρει: την αρχή του buffer, το συνολικό πλήθος των στοιχείων του buffer, το μέγεθος του κάθε στοιχείου σε bytes και τέλος το πως ορίζεται η σύγκριση μεταξύ 2 στοιχείων.

 

Όλα οκ με τα 3 πρώτα, το 4ο όρισμα όμως ίσως θέλει επεξήγηση. Δεν μπορούμε να περάσουμε ως τρόπο σύγκρισης των στοιχείων ότι μας καπνίσει. Θέλουμε έναν δείκτη σε μια συνάρτηση που πρέπει να την ορίσουμε με πολύ συγκεκριμένο τρόπο, δηλαδή στα πρότυπα που την αναμένει η qsort().

 

Πιο συγκεκριμένα, η συνάρτηση σύγκρισης πρέπει να παίρνει ως ορίσματα δυο δείκτες στα προς σύγκριση στοιχεία (έναν για το καθένα τους), και να επιστρέφει έναν ακέραιο μικρότερο, ίσο ή μεγαλύτερο του 0, ανάλογα με τον αν το 1ο στοιχείο είναι μικρότερο, ίσο ή μεγαλύτερο του 2ου στοιχείου (κατά αναλογία δηλαδή των συναρτήσεων strcmp() και strncmp() της <string>, κάτι που προφανώς δεν είναι σύμπτωση ).

 

Όταν καλούμαστε λοιπόν να υλοποιήσουμε τη συνάρτηση σύγκρισης δυο ίδιων τύπου μεταβλητών (για να την περάσουμε κατόπιν ως callback στην qsort()), είμαστε υποχρεωμένοι να ακολουθήσουμε το πρότυπό της όπως το αναμένει η qsort()... δηλαδή ως void δείκτες τα 2 της ορίσματα.

 

Οπότε, αν θέλουμε να ταξινομήσουμε ας πούμε έναν πίνακα από int μέσω της qsort(), τότε η συνάρτηση σύγκρισης θα πρέπει να πάρει τα 2 της ορίσματα ως const void δείκτες και μέσα της να τα κάνει cast σε int (ή const int) δείκτες, προκειμένου να μπορέσει να τα κάνει dereference και να συγκρίνει τις τιμές τους.

 

Αυτό γίνεται κάπως έτσι...

 

>
int cb_compare_integers( const void *pInt1, const void *pInt2 )
{
 // sanity checks should be added here

 const int *pint1 = (const int *) pInt1;  // cast pInt1 to (const int *)
 const int *pint2 = (const int *) pInt2;  // cast pInt2 to (const int *)

 return (*pint1 > *pint2) - (*pint1 < *pint2);
}

ή ισοδύναμα...

int cb_compare_integers( const void *pInt1, const void *pInt2 )
{
 // sanity checks should be added here

 return ( *(int *)pInt1 > *(int *)pInt2 ) - ( *(int *)pInt1 < *(int *)pInt2 );
}

 

Οπότε όταν θέλουμε για παράδειγμα να ταξινομήσουμε έναν πίνακα από 5 floats, μπορούμε να γράψουμε κάτι σαν το παρακάτω...

 

>
#include <stdio.h>
#include <stdlib.h>

/*****************************************************//**/
int cb_compare_floats( const void *pFloat1, const void *pFloat2 )
{
 // sanity checks should be added here

 return ( *(float *)pFloat1 > *(float *)pFloat2 ) - ( *(float *)pFloat1 < *(float *)pFloat2 );
}
/*****************************************************//**
*
*********************************************************
*/
int main( void )
{
   float arrFloat[5] = { 1.0f, 10.0f, 5.0f, 8.0f, 2.0f };

   for (size_t i=0; i < 5; i++)
       printf( "%f ", arrFloat[i] );
   putchar('\n');

   qsort(arrFloat, 5, sizeof(float), &cb_compare_floats );

   for (size_t i=0; i < 5; i++)
       printf( "%f ", arrFloat[i] );
   putchar('\n');

   system( "pause" );
   exit( EXIT_SUCCESS );
}

 

Ένα άλλο σημείο που θέλει προσοχή όταν κάνουμε generic programming είναι ο assignment operator. Δηλαδή όταν υλοποιούμε μια συνάρτηση η οποία δουλεύει με abstract data types (δηλαδή void δείκτες) δεν μπορούμε να χρησιμοποιήσουμε τον τελεστή = για να αναθέτουμε τιμές στις abstract μεταβλητές μας. Ούτε μεταξύ τους ούτε με σταθερές.

 

Πρέπει να πληρούνται 2 προϋποθέσεις:

 

1. Να ξέρουμε και το μέγεθος της μεταβλητής που θα μπει στην αριστερή μεριά της ανάθεσης, το οποίο προφανώς είναι ίδιο με το μέγεθος εκείνης που θα μπει στην δεξιά μεριά της ανάθεσης.

 

2. Το 1. αποκλείει η τιμή που θα μπει στη δεξιά μεριά να είναι σταθερά. Πρέπει κι αυτή να είναι μια μεταβλητή που περιέχει την επιθυμητή τιμή, και να περαστεί κατόπιν στην generic συνάρτηση ένας δείκτης προς αυτή την μεταβλητή.

 

Αφού εξασφαλιστούν οι παραπάνω προϋποθέσεις, τότε μπορεί η generic συνάρτηση μας που λειτουργεί ως assignment operator να κάνει την ανάθεση είτε με memcpy() είτε καλύτερα με memmove().

 

Παράδειγμα...

 

>
...
void *generic_assignment( void *left, const void *right, size_t size )
{
   // sanity checks should be added here

   return memmove( left, right, size );
}
...
int main( void )
{
   float f1, f2 = 3.7f;

   generic_assignment( &f1, &f2, sizeof(float) );
   ...
}

 

Το παραπάνω είναι ο τρόπος υλοποίησης generic assignment operator με χρήση δεικτών void. Ένας άλλος τρόπος είναι με macro...

 

>
#define GENERIC_ASSIGNMENT(x,y) (x=y)

 

αλλά προφανώς προκύπτουν ακόμα περισσότερα θέματα validation από ότι με τους void δείκτες.

 

Και κάπου εδώ τελειώνουν οι βασικές γνώσεις που χρειάζεται να έχει κανείς προκειμένου να πραγματοποιήσει generic programming μέσω void δεικτών στην C

 

Σε επόμενο post θα δώσω και την βιβλιοθήκη, η οποία δεν χρησιμοποιεί τίποτα περισσότερα από όσα περιέγραψα στα 2 αυτά posts

 

@imitheos:

 

Απόλυτα σωστός! My bad, πάω να το διορθώσω (άτιμος gcc ... αν και στην βιβλιοθήκη τους κάνω έτσι κι αλλιώς cast σε char *, για αυτό δεν χτύπησε σε κανέναν από τους 3 compilers που το δοκίμασα: gcc, lcc-win32 και pelles-c).

 

EDIT:

 

Προστέθηκαν μερικές ακόμα απαραίτητες πληροφορίες, για generic programming προς το τέλος του post (και μερικά code snippets).

Επεξ/σία 28 Νοεμβρίου 2012 από migf1

[migf1]

Σχετικά με την βιβλιοθήκη τώρα, όπως έγραψα από την αρχή είναι υποτυπώδης και μη-βέλτιστη. Για παράδειγμα λείπουν συναρτήσεις προσθήκης, διαγραφής στοιχείων, abstract iterators, και πολλά άλλα. Επίσης, δεν ασχολήθηκα με επιδόσεις και πολλές λεπτομέρειες, εκτός από sanity checks με τα οποία είναι γεμάτη.

 

Για παράδειγμα, τα sets ταξινομούνται αναγκαστικά μέσα στις συναρτήσεις παραγωγής της τομής τους, μιας και δεν ασχολήθηκα να υλοποιήσω hashing. Απλώς έχω βάλει ένα .isSorted flag στο καθένα τους ώστε να μην ταξινομείται ξανά αν είναι ήδη ταξινομημένο.

 

Για να μην το κουράζω πολύ, τα επόμενα 2 spoilers περιέχουν 2 testing .c προγράμματα που δοκιμάζουν τη βιβλιοθήκη. Ένα για primary type στοιχεία, κι ένα για στοιχεία που είναι strings συγκεκριμένου μέγιστου μήκους.

 

Είναι δηλαδή τα "συνθετικά" εκείνου του κώδικα που έδωσα στο αρχικό ποστ, τα οποία μάλλον είναι πιο ευκολοδιάβαστα από εκείνο (επειδή είναι πιο στοχευμένα).

 

Primary-typed Elements:

 

 

 

>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <limits.h>

#include "sets.h"

// prepare type specific info for our sets
typedef float SetElemT;
static const SetElemT elemMaxval    = FLT_MAX;
static const char *fmttxtPrintElem    = "%f ";

// we'll always want "no duplicates" when calling set_get_intersection()
// so we just define a global constant for passing that info to the function
static const SetsBool dupsYesNo        = setsNO;

/*****************************************************//**
* Print the value of a set element
*/
static void cb_print_element( const void *pElem )
{
   const SetElemT *pelem = (const SetElemT *)pElem;
   if ( pElem ) {
       printf( fmttxtPrintElem, *pelem );
       fflush( stdout );
   }
}
/*****************************************************//**
* Compare the values of two set elements
*/
static int cb_compare_elements( const void *pElem1, const void *pElem2 )
{
   const SetElemT *pelem1 = (const SetElemT *) pElem1;
   const SetElemT *pelem2 = (const SetElemT *) pElem2;

   if ( !pelem1 || !pelem2 )
       return INT_MAX;

   return (*pelem1 > *pelem2) - (*pelem1 < *pelem2);
}

/*****************************************************//**
*
*********************************************************
*/
int main( void )
{
   // define 3 arrays of ints (to be used for creating & manipulating 3 int sets)
   SetElemT data1[] = {65, 65, 61, 68};
   SetElemT data2[] = {67, 65, 65};
   SetElemT data3[] = {65, 65};

   // define 3 variables holdling the lengths of the above arrays
   size_t len1    = sizeof(data1) / sizeof(data1[0]);
   size_t len2    = sizeof(data2) / sizeof(data2[0]);
   size_t len3    = sizeof(data3) / sizeof(data3[0]);

   // define 3 sets variables to be constructed using the info defined above
   Set *set1    = NULL;
   Set *set2    = NULL;
   Set *set3    = NULL;
   // define another set for holding the intersection of the other sets
   Set *result    = NULL;

   // enable the debugging-mode of the library (will report all library errors)
   sets_setting_dbgmode( setsYES );

   // create and populate 3 unsorted sets (setsFALSE means unsorted)
   set1 = set_new_init( len1, sizeof(SetElemT), &elemMaxval, data1, setsFALSE );
   set2 = set_new_init( len2, sizeof(SetElemT), &elemMaxval, data2, setsFALSE );
   set3 = set_new_init( len3, sizeof(SetElemT), &elemMaxval, data3, setsFALSE );

   // print contents of the 3 sets
   set_print( set1, "1st set: ", "\n", &cb_print_element );
   set_print( set2, "2nd set: ", "\n", &cb_print_element );
   set_print( set3, "3rd set: ", "\n", &cb_print_element );

   // get and print the intersection of the 3 sets
   result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_elements);
   set_print(result, "Intersection: ", "\n\n", &cb_print_element);

   // free all sets
   set_free( &set1 );
   set_free( &set2 );
   set_free( &set3 );
   set_free( &result );

   system( "pause" );
   exit( EXIT_SUCCESS );
}

 

 

 

String Elements:

 

 

 

>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#include "sets.h"

// prepare type specific info for our string sets
#define SIZEOF_StrELEM            ( 20+1 )
typedef char SetElemT;
static const SetElemT elemMaxVal[sizeOF_StrELEM] = "zzzzzzzzzzzzzzzzzzzz";
static const char *fmttxtPrintElem    = "%s ";

// we'll always want "no duplicates" when calling set_get_intersection()
// so we just define a global constant for passing that info to the function
static const SetsBool dupsYesNo        = setsNO;

/*****************************************************//**
* Print the value of a string element
*/
static void cb_print_element( const void *pElem )
{
   const SetElemT *pelem = (const SetElemT *)pElem;
   if ( pElem ) {
       printf( fmttxtPrintElem, pelem );
       fflush( stdout );
   }
}
/*****************************************************//**
* Compare the values of two string elements
*/
static int cb_compare_elements( const void *pElem1, const void *pElem2 )
{
   const SetElemT *pelem1 = (const SetElemT *) pElem1;
   const SetElemT *pelem2 = (const SetElemT *) pElem2;

   if ( !pelem1 || !pelem2 )
       return INT_MAX;

   return     strncmp(pelem1, pelem2, SIZEOF_StrELEM);
}

/*****************************************************//**
*
*********************************************************
*/
int main( void )
{
   // define 3 arrays of strings (to be used for creating & manipulating 3 string sets)
   SetElemT data1[4][sizeOF_StrELEM] = {"John", "John", "Mary", "Alex"};
   SetElemT data2[3][sizeOF_StrELEM] = {"Tony", "John", "John"};
   SetElemT data3[2][sizeOF_StrELEM] = {"John", "John"};

   // define 3 variables holdling the lengths of the above arrays
   size_t len1    = sizeof(data1) / sizeof(data1[0]);
   size_t len2    = sizeof(data2) / sizeof(data2[0]);
   size_t len3    = sizeof(data3) / sizeof(data3[0]);

   // define 3 sets variables to be constructed using the info defined above
   Set *set1    = NULL;
   Set *set2    = NULL;
   Set *set3    = NULL;
   // define another set for holding the intersection of the other sets
   Set *result    = NULL;

   // enable the debugging-mode of the library (will report all library errors)
   sets_setting_dbgmode( setsYES );

   // create and populate 3 unsorted sets (setsFALSE means unsorted)
   set1 = set_new_init( len1, SIZEOF_StrELEM, elemMaxVal, data1, setsFALSE );
   set2 = set_new_init( len2, SIZEOF_StrELEM, elemMaxVal, data2, setsFALSE );
   set3 = set_new_init( len3, SIZEOF_StrELEM, elemMaxVal, data3, setsFALSE );

   // print contents of the 3 sets
   set_print( set1, "1st set: ", "\n", &cb_print_element );
   set_print( set2, "2nd set: ", "\n", &cb_print_element );
   set_print( set3, "3rd set: ", "\n", &cb_print_element );

   // get and print the intersection of the 3 sets
   result = set_get_3intersection(set1, set2, set3, dupsYesNo, &cb_compare_elements);
   set_print(result, "Intersection: ", "\n\n", &cb_print_element );

   // free all sets
   set_free( &set1 );
   set_free( &set2 );
   set_free( &set3 );
   set_free( &result );

   system( "pause" );
   exit( EXIT_SUCCESS );
}

 

 

 

Ουσιαστικά για τον κάθε τύπο στοιχείων που θέλουμε να διαχειριστούμε με την βιβλιοθήκη, πρέπει να της "γνωστοποιήσουμε" τις εξής πληροφορίες:

• size_t elemSize
  Το μέγεθος του τύπου των στοιχείων.
   
  
• const void *pElemMaxVal
  Την μέγιστη τιμή που μπορεί να πάρει οποιοδήποτε στοιχείο αυτού του τύπου (π.χ. INT_MAX αν είναι int) σε μορφή μεταβλητής που περιέχει αυτή την τιμή.
   
  Αυτό το χρησιμοποιεί η βιβλιοθήκη για να αρχικοποιεί τον πίνακα result, πριν ξεκινήσει να του βάζει τα κοινά στοιχεία 2 πινάκων. Επειδή ο αλγόριθμος της τομής (αλλά και της αναζήτησης που είναι binary-search) απαιτεί ταξινομημένα στοιχεία, αυτή αρχικοποίηση εξασφαλίζει πως τα στοιχεία που μπαίνουν στην αρχή του set είναι πάντα μικρότερα ή ίσα από όσα έπονται μέχρι το τέλος του πίνακα (στο τέλος βέβαια ο πίνακας γίνεται truncate στο ωφέλιμο μήκος του).
   
  
• void (*cb_print_element)(const void *elem)
  Την συνάρτηση που εκτυπώνει ένα στοιχείο του τύπου.
   
  
• int (*cb_compare_elements)(const void *, const void *)
  Την συνάρτηση που συγκρίνει 2 στοιχεία του τύπου (στα πρότυπα της συνάρτησης σύγκρισης που περιέγραψα σε προηγούμενο ποστ για την qsort().
  

 

Αυτές είναι οι βασικές πληροφορίες που χρειάζεται η βιβλιοθήκη σε ότι αφορά το abstraction του τύπων των στοιχείων.

 

Στον βασικό constructor...

 

>
Set *set_new_init(
   size_t        len,        /* max # of elements in set */
   size_t        elemSize,    /* size of a single element, in bytes */
   const void    *pElemMaxVal,    /* ptr to an element hodling the max possibe value */
   const void    *data,        /* ptr to data-elements to be copied into set->data */
   SetsBool    isSorted    /* are the inited data-elements already sorted? */
   );

 

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

 

Δηλαδή...

• size_t len
  το πλήθος των στοιχείων που θέλουμε να δημιουργηθούν μέσα στο set
   
  
• const void *data
  έναν πίνακα που περιέχει τα στοιχεία που θέλουμε να μπουν στο set
   
  
• SetsBool isSorted
  μια boolean τιμή για το αν τα στοιχεία του data είναι ήδη ταξινομημένα σε αύξουσα σειρά (αν είναι, άρα του περάσουμε SetsTRUE, τότε αποφεύγεται η εκ νέου ταξινόμησή τους μέσα στις συναρτήσεις εύρεσης τομής.
  

 

Υπάρχει κι ένας 2ος constructor, ο οποίος δημιουργεί ένα set με το πλήθος στοιχείων που του λέμε και τα αρχικοποιεί με μια τιμή που επίσης του λέμε...

 

>
Set *set_new_aggregate(
   size_t        len,        /* max number of elements in set */
   size_t        elemSize,    /* size of any single element, in bytes */
   const void    *pElemMaxVal,    /* ptr to an element hodling the max possibe value */
   const void    *pElemAggregate,/* ptr to the element to be aggregated into set->data */
   int        (*cb_compare_elements)(const void *, const void *)
   );

 

Αυτόν τον χρησιμοποιεί εσωτερικά η βιβλιοθήκη, αλλά τον έχω αφήσει public σε περίπτωση που χρειαστεί να κληθεί εξωτερικά. Αυτός ο constructor παίρνει σαν όρισμα κι έναν δείκτη στη συνάρτηση σύγκρισης στοιχείων, για να μπορεί να ελέγξει αν η τιμή που του λέμε να κάνει aggregate είναι μικρότερη ή ίση από την μέγιστη τιμή του τύπου (την οποία επίσης του την περνάμε)... αν δεν είναι, τότε επιστρέφει NULL.

 

Όλες αυτές οι πληροφορίες (τύπου στοιχείων και έξτρα) αποθηκεύονται με την κλήση των constructors σε αντίστοιχα πεδία (fields) στην εσωτερική δομή του κάθε set, με εξαίρεση τους δείκτες στις συναρτήσεις εκτύπωσης και σύγκρισης...

 

>
/** Private type describing a set */
typedef struct Set {
   size_t    len;        /*!< number of elements in set */
   size_t    elemSize;    /*!< size of any individual element in set, in bytes */
   void    *pElemMaxVal;    /*!< ptr to an element holding the max possible value */
   size_t    size;        /*!< size of all set elements, in bytes */
   SetsBool isSorted;    /*!< are the set elements sorted in ascending order? */
   void    *data;        /*!< dynamically allocated array holding all set elements */
}Set;

 

Το πεδίο: size_t size αντιστοιχεί στο συνολικό μέγεθος όλων των στοιχείων του set (δηλαδή του πεδίου: void *data) και υπολογίζεται επίσης εσωτερικά: len * elemSize.

 

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

 

Για παράδειγμα η συνάρτηση εκτύπωσης όλων των στοιχείων ενός set, αντί για ...

 

>
void set_print(
   const Set    *set,
   const char    *header,
   const char    *footer,
   void        (*cb_print_element)(const void *elem)
   );

 

που είναι τώρα, θα ήταν...

 

>
void set_print(
   const Set    *set,
   const char    *header,
   const char    *footer
   );

 

μιας και ο δείκτης στη συνάρτηση cb_print_element θα ήταν ήδη αποθηκευμένος (από την κλήση του constructor) μέσα στο 1ο όρισμα, το: const Set *set

 

Οπότε όταν θα θέλαμε να εκτυπώσουμε όλα τα στοιχεία ενός δημιουργημένου set, αντί να γράφουμε...

 

>set_print( set1, "1st set: ", "\n", &cb_print_element );

 

όπως τώρα, θα γράφαμε...

 

>set_print( set1, "1st set: ", "\n" );

 

και μέσα στον κώδικα της set_print() θα καλούσαμε την συνάρτηση εκτύπωσης ως εξής:

 

>set->cb_compare_element(bla bla)

 

Ο αντίλογος είναι πως όσα περισσότερα πράγματα βάζουμε ως πεδία στην εσωτερική δομή του κάθε set, τόσο περισσότερη μνήμη καταναλώνουμε, μιας και η δομή δημιουργείται για κάθε set που φτιάχνουμε.

 

Εγώ βέβαια εδώ δεν το υλοποίησα χωρίς εσωτερικούς δείκτες συναρτήσεων για να γλιτώσω μνήμη (σιγά το μνημοβόρο πρόγραμμα). Το έκανα γιατί το θεώρησα πως θα έβγαζε πιο κατανοητό κώδικα σε όσους δεν είναι ακόμα ιδιαίτερα εξοικειωμένοι. Δηλαδή πιο άμεσο κώδικα, με την έννοια του what-you-see-is-what-you-get.

 

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

 

Κάνω ένα διάλειμμα να τσιμπήσω τίποτα, κι επιστρέφω με τον κώδικα της βιβλιοθήκης.

Επεξ/σία 28 Νοεμβρίου 2012 από migf1

[migf1]

Καταρχήν το download: sets_test.zip

 

Η βιβλιοθήκη αποτελείται από δυο αρχεία:

• sets.h
  το δημόσιο interface
  
• sets.c
  η ιδιωτική υλοποίηση
  

Το αρχείο: sets.o είναι το object-file της βιβλιοθήκης από τον mingw32 (δεν το χρειάζεστε βασικά, αφού μάλλον έτσι κι αλλιώς θα την κάνετε μόνοι σας compile την βιβλιοθήκη στον δικό σας compiler... οπότε σβήστε το). Τα υπόλοιπα αρχεία .c είναι αυτά που έχω ποστάρει κι εδώ, που δοκιμάζουν την βιβλιοθήκη.

 

Για γρήγορες δοκιμές ή αν δεν ξέρετε πως να χρησιμοποιείτε εξωτερικές βιβλιοθήκες με το tool-chain του compiler σας, μπορείτε απλώς να κάνετε...

 

>
#include "sets.h"

 

στα πηγαία αρχεία που θέλετε να χρησιμοποιήσουν συναρτήσεις της βιβλιοθήκης, και να συμπεριλάβετε και το sets.c στο project σας.

 

Με gcc σε command-line κάνετε απλώς...

 

>
gcc myporg.c sets.c -o myprog.exe  // ή σκέτο myprog στο τέλος αν είστε σε *nix

 

Information Hiding

 

Λίγο πολύ είναι γνωστά τα πράγματα (και αρκετά περιορισμένα στην C), αλλά εν συντομία να πω 2 λόγια.

 

Το βασικό ζητούμενο είναι να κρύψουμε από τον end-programmer όλες τις εσωτερικές υλοποιήσεις, δομές, σταθερές, κλπ της βιβλιοθήκης. Ταυτόχρονα θέλουμε να του παράσχουμε δημόσια τα ελάχιστα δυνατόν εργαλεία που χρειάζεται, για να μπορεί να χρησιμοποιεί τη βιβλιοθήκη στα προγράμματά του (χωρίς δηλαδή να ρισκάρουμε να μας πειράξει κρίσιμα πράγματα).

 

Public Interface

 

Αυτά τα δημόσια εργαλεία βρίσκονται μαζεμένα στο αρχείο: sets.h, το οποίο και πρέπει να κάνει #include ο end-programmer στα πηγαία του αρχεία.

 

Στην προκειμένη περίπτωση, αποτελείται από...

• τη δήλωση του custom τύπου: Set
  (ο ορισμός του είναι κρυμμένος στο αρχείο: sets.c)
   
  
• τον ορισμό του custom boolean τύπου: SetsBool
  με πιθανές τιμές: setsTRUE, setsFALSE, setsYES και setsNO, (με τις 2 τελευταίες να είναι απλά aliases των 2 πρώτων).
   
  
• την καθολική μεταβλητή: g_sets_settings καθώς και τον ορισμό του τύπο της
  (μπορεί να αλλαχτεί η τιμή της (όχι όμως το όνομά της) είτε απευθείας, είτε μέσω της συνάρτησης: sets_setting_dbgmode(). Την μεταβλητή αυτή την χρησιμοποιούν κι εσωτερικές συναρτήσεις της βιβλιοθήκης.
   
  
• τα πρότυπα των συναρτήσεων που θέλουμε να είναι public.
  (οι υλοποιήσεις τους είναι κρυμμένες, στο αρχείο: sets.c)
  

 

Private Implementation

 

Όλα τα κρίσιμα στοιχεία της βιβλιοθήκης, που αφορούν δηλαδή τις λεπτομέρειες της εσωτερικής της υλοποίησης βρίσκονται στο αρχείο: sets.c.

 

Έτσι εκτός από το ότι δεν ρισκάρουμε να πειραχτούν εξωγενώς τα εσωτερικά mechanics της βιβλιοθήκης, αν τα έχουμε σχεδιάσει προσεχτικά τότε μπορούμε να αλλάξουμε την εσωτερική υλοποίηση οποιουδήποτε σημείου, χωρίς να χρειαστεί να αλλαχτούν οι κώδικες που έχουν γράψει ήδη οι end-programmers με τις παλιές υλοποιήσεις.

 

Θα χρειαστεί απλώς να κάνουν re-compile τους κώδικές τους (εκτός αν την βιβλιοθήκη την διαθέτουμε ως shared, αντί για static, περίπτωση κατά την οποία δεν χρειάζεται ούτε να κάνουν recompile... απλώς θα βάλουν στο σύστημά τους την νέα έκδοση της βιβλιοθήκης... π.χ. το νέο .dll αρχείο, αν μιλάμε για Windows).

 

Με άλλα λόγια, το αρχείο sest.c δεν είναι προς δημόσια διάθεση. Για αυτό και περιέχει τα όλα τα private stuff.

 

Αν πρόκειται για στατική βιβλιοθήκη, τότε δίνουμε στον end-programmer μονάχα το object αρχείο της βιβλιοθήκης, για να κάνει re-compile τους κώδικές του.

 

Αν πρόκειται για δυναμική βιβλιοθήκη (shared) του δίνουμε απλώς το shared object file και δεν χρειάζεται να κάνει ούτε re-compile.

 

Δείτε τι περιέχει το αρχείο sets.c, και απλώς κρατήστε πως όποια συνάρτηση ΔΕΝ έχει το keyword static μπροστά από τον ορισμό της, τότε δεν μπορεί να βγει public ούτε καν το πρότυπό της (αντί για static έχω φτιάξει ένα alias PRIVATE, για να το κάνει πιο εμφανές... αν και μόνο μια συνάρτηση είναι PRIVATE, η SetsBool _set_aggregate() ).

 

Οτιδήποτε άλλο που δεν είναι συνάρτηση (π.χ. macro, custom type, κλπ) είναι ορατό μονάχα μέσα στο αρχείο: sets.c

 

Τέλος παρατηρήστε πως στην αρχή του sets.c γίνεται #include και το sets.h, μιας ξαθ χρειάζονται και μέσα στο sets.c κάποια από τα public πράγματα (όπως για παράδειγμα ο custom boolean τύπος SetsBool, όπως και η καθολική μεταβλητή: g_sets_settings, κλπ).

[migf1]

Προσθέτω κάτι έξτρα πράγματα σε ένα απλό generic stack interface (όχι εκείνο το παλιό για την RSA στην Αμερική, άλλο).

 

Εν συντομία, το interface υλοποιεί τα κλασικά operations μιας στοίβας, αλλά έχει κι αρκετά έξτρα (είναι υλοποιημένη ως διπλά συνδεδεμένη λίστα).

 

Θέλω λοιπόν να προσθέσω έναν iterator της στοίβας στο interface (βασικά τον έχω προσθέσει ήδη), αλλά επειδή το interface υλοποιείται με πολύ απλοϊκό OOP μου έχει βγει ολίγον παραπάνω... φλύαρο από ότι θα επιθυμούσα.

 

 

 

>
typedef void* GSIterator;

GSIterator gstack_iter_set (GStack *gs, size_t count)
    Move the specified stack's iterator to the specified position in the stack.

GSIterator gstack_iter_set_beg (GStack *gs)
    Move the specified stack's iterator to the first node.

GSIterator gstack_iter_set_end (GStack *gs)
    Move the specified stack's iterator to the last node.

GSIterator gstack_iter_set_next (GStack *gs)
    Move the specified stack's iterator to the next node.

GSIterator gstack_iter_set_prev (GStack *gs)
    Move the specified stack's iterator to the previous node.

GSIterator gstack_iter_current (const GStack *gs)
    Get an iteratable object from the current position of the specified stack's iterator.

GSIterator gstack_iter_beg (const GStack *gs)
    Get an iteratable object from the specified stack's first node.

GSIterator gstack_iter_end (const GStack *gs)
    Get an iteratable object from the specified stack's last node.

GSItemData *gstack_iter_peek (const GStack *gs)
    Get the data from the node under the current position of the iterator.

 

 

 

Με μια συνηθισμένη χρήση του κάπως έτσι...

 

>
   for ( gstack_iter_set_end(gs); NULL != gstack_iter_current(gs); gstack_iter_set_prev(gs) ) {
       int amount = 20;
       cb_increase_int( gstack_iter_peek(gs), &amount );
   }

 

Το παραπάνω loop πιάνει τη στοίβα gs από την κορυφή μέχρι τον πάτο και προσθέτει +20 στα ακέραια data του κάθε node.

 

Να δώσω και λίγο κώδικα εδώ για να δείτε πως το έχω κάνει τώρα, ώστε να μπορέσετε να μου απαντήσετε πιο κάτω...

 

 

 

 

Η δομή της στοίβας...

 

>
typedef struct _GSNode {
   void        *data;
   struct _GSNode    *prev;
   struct _GSNode    *next;
   size_t        count;
}_GSNode;

typedef struct _GSIter {
   int        tid;    // unused
   struct _GSNode    *beg;
   struct _GSNode    *curr;
   struct _GSNode    *end;
}_GSIter;

typedef struct GStack {
   size_t        dataSize;    /*!< size of data in every stack node */
   _GSNode        *tos;        /*!< top of stack */
   _GSNode        *bos;        /*!< bottom of stack */
   _GSIter        iter;        /*!< internal stack iterator struct */
   void        *poppedData;    /*!< for saving the popped data */
}GStack;

 

Ο κώδικας των προαναφερθεισών συναρτήσεων...

 

>
/*****************************************************//**
*   Move the iterator to the last node (gs->tos) & return it
*/
void *gstack_iter_set_end( GStack *gs )
{
   if ( !gs )
       return NULL;

   return (gs->iter.curr = gs->iter.end);
}
/*****************************************************//**
* Move the iterator to the previous node & return it
*/
void *gstack_iter_set_prev( GStack *gs )
{
   if ( !gs || !gs->iter.curr )
       return NULL;

   return (gs->iter.curr = gs->iter.curr->prev);
}
/*****************************************************//**
* Return a pointer to the node under the iterator's current position
*/
void *gstack_iter_current( const GStack *gs )
{
   if ( !gs )
       return NULL;

   return gs->iter.curr;
}
/*****************************************************//**
* Peek the node at the current position of the iterator
*/
void *gstack_iter_peek( const GStack *gs )
{
   if ( !gs || !gs->iter.curr )
       return NULL;

   return gs->iter.curr->data;
}

 

 

 

 

 

Που είναι η φλυαρία; Εκτός της προφανούς συντακτικής, όλες οι συναρτήσεις του iterator επιστρέφουν έναν δείκτη που είναι τελείως άχρηστος (πλην της συνάρτησης gstack_iter_peek(gs) η τιμή επιστροφή της οποίας γίνεται dereferenced στα data του node).

 

Δηλαδή, ενώ μπορούμε να γράψουμε το loop κάπως έτσι...

 

>
   for ( GSIterator it=gstack_iter_set_end(gs); NULL != it; it = gstack_iter_set_prev(gs) ) {
       int amount = 20;
       cb_increase_int( gstack_iter_peek(gs), &amount );
   }

 

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

 

Από την άλλη μεριά, έστω πως κάνω τις συναρτήσεις να δέχονται τον iterator ως όρισμα και να τον αλλάζουν. Νομίζω δεν θα με απαλλάξει από την ανάγκη διατήρησης και εσωτερικού housekeeping, όπως κάνω τώρα.

 

Δηλαδή ας πούμε θα έχουμε οπτικά το loop κάπως έτσι...

 

>
   for ( GSIterator it=gstack_iter_end(gs); NULL != it; it = gstack_iter_set_prev(gs, it) ) {
       int amount = 20;
       cb_increase_int( gstack_iter_peek(gs, it), &amount );
   }

 

ή έστω το peeking χωρίς πέρασμα της gs...

 

>
   for ( ... ) {
       ...
       cb_increase_int( gsΙter_peek(it), &amount );
   }

 

μιας και ο it βασικά είναι reference σε node, και η συνάρτηση κάνει dereference το node->data (που με τη σειρά του είναι void δείκτης ).

 

Το πρώτο ερώτημα που προκύπτει αν το υλοποιήσω έτσι, είναι πως θα μπορέσει η gstack_iter_peek(gs, it) (ή η gsΙter_peek(it) ) να πιστοποιήσει πως το όρισμά της -ο iterator, δηλαδή το it εδώ- δείχνει όντως σε κάποιο node της στοίβας και όχι π.χ. στο σπίτι της θείας Αντιγόνης στη Τζια;

 

Επίσης, όπως το έχω τώρα διατηρώ ανά πάσα στιγμή εσωτερικά τον gs->iter.cur σκεπτόμενος πως θα με διευκολύνει στο να επιταχύνω τις random access αιτήσεις.

 

Πιο συγκεκριμένα, αν για παράδειγμα μου δώσει την 1η φορά: gs_iter_set(gs, 20) θα πάω linear τον gs->iter.curr στον 20 κόμβο, είτε ξεκινώντας από τον gs->tos είτε από τον gs->bos, ανάλογα ποιος είναι πιο κοντά.

 

Όταν όμως μετά μου δώσει ας πούμε: gs_iter_set(gs, 21) τότε θα έχω τη δυνατότητα να βάλω και τον gs->iter.curr μέσα στο παιχνίδι, και αντί να ξεκινήσω ξανά μανά από τον gs->bos ή από τον gs->tos, να δω πρώτα αν με συμφέρει να ξεκινήσω από τον gs->iter.curr.

 

Εν ολίγοις, έχω καταλήξει στο ότι χρειάζομαι έτσι κι αλλιώς εσωτερικό houskeeping (που στον κώδικα εκφράζεται βασικά με την διαχείριση του struct _GSiter) αλλά δεν μου αρέσει καθόλου αυτή η συντακτική φλυαρία και οι άχρηστες τιμές επιστροφών.

 

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

 

[migf1]

Μάλλον δεν ενδιαφέρει κανέναν, αλλά τελικά έβγαλα άκρη: έβαλα και internal και external iterator support

 

>
#include <assert.h>
#include "genstack.h"

int main( void )
{
   int *data = NULL;
   GStack *gs = gstack_new( sizeof(int) );

   assert( gs );

   // populate the stack with integers from 0 to 9
   for (int i=0; i < 10; i++)
       gstack_push( gs, &i );

   // use the INternal iteraTOR to increase each node data by 20
   for ( gstack_intor_begin(gs); gstack_intor_is_valid(gs); gstack_intor_next(gs) )
   {
       data = gstack_intor_peek(gs);
       if ( data )
           (*data) += 20;
   }

   // use an external iterator to print the stack
   for ( GSIterator it = gstack_iter_end(gs); gsiter_is_valid(it); gsiter_prev(&it) )
   {
       data = gsiter_peek(it);
       if ( data )
           printf("%d\n", *data );
   }

   gstack_free(&gs);

   system( "pause" );
   return 0;
}

 

Άφησα τις συναρτήσεις μετακίνησης να επιστρέφουν pointers στους εαυτούς τους, ίσως μου χρειαστεί μελλοντικά.

[παπι]

Μάλλον δεν ενδιαφέρει κανέναν, αλλά τελικά έβγαλα άκρη: έβαλα και internal και external iterator support

ρε συ Mig δεν τσιπριζει αυτο το πραγμα. Η μονη διφορα απο μια κοινη στακ ειναι οτι εχει void pointer.

[migf1]

Τι σημαίνει τσιπρίζει;

 

Βασικά η συγκεκριμένη κάνει πολλά περισσότερα από μια κοινή stack. Αν και δεν ξέρω πως την εννοείς την κοινή stack (εγώ την εννοώ βάση του κοινού ορισμού της, δηλαδή με 3 μόνο operations: push, pop, top... άντε και άλλα 2 για is_empty και is_full και απολύτως τίποτα άλλο).

 

Έχω επίσης το ελεύθερο να την διαθέσω public μόλις την τελειώσω, αν το επιθυμώ, με κάποιους περιορισμούς, στους οποίους δεν έχουμε καταλήξει ακόμα. Ένας που θα υπάρχει μάλλον στο public version θα είναι να μην υπάρχει η δυνατότητα να περαστούν ως callback στον constructor της στοίβας user-defined constructor & destructor για τα data... θα περιορίζονται στα απλά, εσωτερικά malloc/free των void pointers. Οπότε αν π.χ. στο κάθε node της στοίβας θέλει κάποιος να κρέμονται ας πούμε τίποτα δέντρα, θα είναι υποχρεωμένος την περισσότερη δουλειά να την κάνει εξωτερικά.

 

Από εκεί και πέρα όμως, το βασικό πλεονέκτημα του void * είναι πως μπορεί να χρησιμοποιηθεί ακριβώς το ίδιο interface με οποιοδήποτε data, είτε custom είτε user-defined.

 

Επίσης, όπως έγραψα και πριν η συγκεκριμένη στοίβα κάνει αρκετά περισσότερα από μια κοινή στοίβα, με κυριότερο extension ότι σου δίνει και FIFO access στα nodes, εκτός από το default LIFO.

 

Π.χ.

 

>
size_t     gstack_rfind (const GStack *gs, const void *pData, int(*cb_compare_nodeData)(const void *pData1, const void *pData2))
    Look for the most recent occurrence of the specified data, in the specified stack.

size_t     gstack_find (const GStack *gs, const void *pData, int(*cb_compare_nodeData)(const void *pData1, const void *pData2))
    Look for the least recent occurrence of the specified data, in the specified stack.

size_t     gstack_rforeach (GStack *gs, void *pUserExtra, void *(*cb_ondata)(const void *pDataBefore, void *pUserExtra))
    Starting from top to bottom, apply the specified callback function on the data of every node in the specified stack.

size_t     gstack_foreach (GStack *gs, void *pUserExtra, void *(*cb_ondata)(const void *pDataBefore, void *pUserExtra))
    Starting from bottom to top, apply the specified callback function on the data of every node in the specified stack.

 

Η ίδια ευελιξία παρέχεται και μέσω των iterators, με έξτρα πως αυτοί δίνουν και random access και relative access. Χωρίς όμως να τους επιτρέπεται να διαγράφουν ή να προσθέτουν κόμβους. Επειδή είναι στοίβα, η προσθήκη/διαγραφή κόμβων γίνεται πάντα με LIFO order.

 

Βασικά είναι υλοποιημένη ως διπλά συνδεδεμένη λίστα, όπου σε κάθε κόμβο κρατιέται κι ένα index number. Το σκεπτικό είναι πως με αυτόν τον τρόπο θα είναι ευέλικτη στο π.χ. να διαχειριστεί αργότερα και ως queue και ως deque και ως γενική λίστα, κλπ απλώς με την προσθήκη κάποιων ακόμα συναρτήσεων στο interface ή/και κάποιων ακόμα τύπων iterators.

 

Δηλαδή είναι ωραίο, ενδιαφέρον και χρήσιμο project, με βασική γραμμή να θυμίζει και να λειτουργεί όσο το δυνατόν περισσότερο με C style.

 

[παπι]

 

 

Οχι παρισφαλ, δεν υπαρχει τιποτα εδω που να παραβιαζει τους κανονες

 

 

Τσιπρας= βολεμα

Τσιπριζει = βολεβει

 

 

 

[moukoublen]

 

 

Οχι παρισφαλ, δεν υπαρχει τιποτα εδω που να παραβιαζει τους κανονες

 

 

Τσιπρας= βολεμα

Τσιπριζει = βολεβει

 

 

 

 

 

 

Αυτά είναι.

Οταν ακούω τέτοιες βαθιά "πολιτικές" αναλύσεις, ενθουσιάζομαι (απ όπου και αν προέρχονται και προς όπου και αν κατευθύνονται).

 

 

 

 

[on topic]

Ενδιαφέροντα πάντως τα όσα κάνεις migf1.

[migf1]

Ενδιαφέροντα πάντως τα όσα κάνεις migf1.

 

Όντως, αλλά as usual θέλουν δουλίτσα... κι ακόμα χειρότερα, θέλουν και documentation

 

@παπι:

 

Φαντάσου να θέλεις να τυπώσεις π.χ. τα 5 πιο παλιά στοιχεία που έχεις φυλαγμένα με χρονολογική σειρά σε μια κοινή στοίβα (πόσο μάλλον να τα σβήσεις). Πρέπει να κάνεις pop όλα τα από πάνω τους και ταυτόχρονα push σε μια προσωρινή κοινή στοίβα. Μόλις τελειώσεις με τα 5 τελευταία, θα πρέπει να κάνεις reverse την προσωρινή στοίβα για να είναι ίδια με την αυθεντική.

 

Ζήσε Μάη μου να φας τριφύλλι δηλαδή.

 

[defacer]

Δε θέλω να μπλεχτώ πολύ γιατί είναι πολύς ο κώδικας και για να τον αξιολογήσεις σαν προσέγγιση δε φτάνει ούτε καν να τον μελετήσεις όλο, αλλά:

 

Δεν καταλαβαίνω γιατί έχεις μπλέξει όλα τα container μαζί. Όταν λέμε ότι κάτι είναι stack, πάει να πει είναι stack και έχει push(), pop() και peek(). Αν αποκτήσει επιπλέον δυνατότητες τότε δεν είναι πια stack και δε θα πρέπει να παρουσιάζει τον εαυτό του ως τέτοιο.

 

Θα σου πρότεινα να δεις πώς έχει σχεδιαστεί η φάση με τους containers στη C++: υπάρχουν κάποιοι βασικοί sequence containers (vector<T> και το μικρό αδερφάκι array<T>, singly και doubly linked list και η deque) και τα stack, queue και priority_queue είναι adaptors: τους δίνεις έναν container type (όποιον θες εσύ) και υλοποιούν το storage τους μ' αυτόν.

 

Επίσης νομίζω ότι είναι πολύ μεγάλο λάθος το γεγονός ότι έχεις κάνει το state του iteration να είναι μέρος του container, με το προφανές μειονέκτημα πως δεν θα μπορείς ποτέ να κάνεις δύο iterations ταυτόχρονα.

[Timonkaipumpa]

Sorry για το hijack

@defacer

 

 

Μεταξύ vector και array, έχεις υπόψη σου εάν υπάρχει διαφορά στις επιδόσεις;

 

 

[migf1]

...

Δεν καταλαβαίνω γιατί έχεις μπλέξει όλα τα container μαζί. Όταν λέμε ότι κάτι είναι stack, πάει να πει είναι stack και έχει push(), pop() και peek(). Αν αποκτήσει επιπλέον δυνατότητες τότε δεν είναι πια stack και δε θα πρέπει να παρουσιάζει τον εαυτό του ως τέτοιο.

 

Για διάφορους λόγους, ο βασικότερος εκ των οποίων είναι πώς αυτό μου ζητήθηκε. Ένας άλλος είναι πως πρόκειται όντως για stack αφού δεν σε αφήνει να προσθέσεις/διαγράψεις κόμβους με οποιοδήποτε άλλο order πλην του LIFO (δηλαδή με push και pop). Επίσης σε επίπεδο api δεν σε αφήνει να ταξινομήσεις τα data της, κλπ. Σου δίνει όμως την δυνατότητα να τα κάνεις modify αν το θελήσεις, και κατ΄επέκταση να τα κάνεις και sort και οτιδήποτε, όταν και αν το χρειαστείς. Ένας τρίτος λόγος είναι πως αν ήθελαν μια απλή stack θα χρησιμοποιούσαν κάποιες από τις 10-άδες έτοιμες που κυκλοφορούν ελεύθερες, ή θα έφτιαχναν μια δικιά τους σε μισή ωρίτσα. Think of this simply as an enhanced, flexible and generic stack.

 

Θα σου πρότεινα να δεις πώς έχει σχεδιαστεί η φάση με τους containers στη C++: υπάρχουν κάποιοι βασικοί sequence containers (vector<T> και το μικρό αδερφάκι array<T>, singly και doubly linked list και η deque) και τα stack, queue και priority_queue είναι adaptors: τους δίνεις έναν container type (όποιον θες εσύ) και υλοποιούν το storage τους μ' αυτόν.

 

Κάπως έτσι θα γίνει στο τέλος, αλλά όχι με την ορολογία ούτε με την υλοποίηση της C++ (αν είναι να φτιάξω C++ container api σε C, χίλιες φορές να μετατρέψουν το project τους σε C++ ή να χρησιμοποιήσουν βιβλιοθήκες τύπου GObject).

 

Ήδη έχω αναφέρει πως η στοίβα είναι υλοποιημένη ως διπλά συνδεδεμένη λίστα με το σκεπτικό πως θα μπορέσει μελλοντικά να προστεθεί και queue, και deque και list και όποιο άλλο functionality, μέσω διαφορετικών interface (διαφορετικών σετ συναρτήσεων) μόνο για τα μη κοινά χαρακτηριστικά τους.

 

Επίσης νομίζω ότι είναι πολύ μεγάλο λάθος το γεγονός ότι έχεις κάνει το state του iteration να είναι μέρος του container, με το προφανές μειονέκτημα πως δεν θα μπορείς ποτέ να κάνεις δύο iterations ταυτόχρονα.

 

Για αυτό όπως έγραψα και σε προηγούμενο ποστ, και με δείγμα κώδικα, αποφάσισα να κάνω support και internal iterator και external iterators. Μου μένει λίγο ακόμα για να ολοκληρώσω τα του internal iterator, και μετά θα πιάσω τους external. Παράλληλα με τον κώδικα γράφω και documentation, ώστε να μην τα έχω όλα μαζί στο τέλος.

 

Μπορείς να διαβάσεις αν θέλεις τα περί intor που έχουν υλοποιηθεί μέχρι στιγμής εδώ: http://x-karagiannis.gr/prg/custom/doc/genstack/html/quick_guide.html#intorSection, ενώ υπάρχουν κι άλλες πληροφορίες για το γενικότερο project (αλλά π.χ. οι external iterators, όπως και διάφορα άλλα δεν είναι όχι απλώς ολοκληρωμένα αλλά ούτε καν δοκιμασμένα ακόμα).

 

ΥΓ. Οι... καστομιές είναι κατά κανόνα άκρως ενδιαφέρουσες και πληρώνονται καλύτερα. Κι ευτυχώς που πάντα υπήρχε και πάντα θα υπάρχει ανάγκη για καστομιές.

[defacer]

Μεταξύ vector και array, έχεις υπόψη σου εάν υπάρχει διαφορά στις επιδόσεις;

 

 

Εκτός από κατασκευασμένες περιπτώσεις γενικά το array πρέπει να είναι λίιιιιιγο γρηγορότερο αφού λογικά τα στοιχεία θα αποθηκεύονται inline στο αντικείμενο και όχι πίσω από ένα pointer όπως στο vector. Πάντως η ειδοποιός διαφορά τους είναι χρηστική (άλλα use cases, άλλες δυνατότητες) και όχι performance-oriented.

 

 

@migf1:

Βεβαίως ο πελάτης έχει σχεδόν πάντα δίκιο αλλά από την περιγραφή εμένα αυτό μου φαίνεται πως είναι list με περιορισμένες δυνατότητες και όχι stack με αυξημένες. Η όλη ιδέα με ένα stack είναι πως επίτηδες δεν μπορείς να κάνεις άλλο access πέραν του peek(). Π.χ. στη C++ θα ήταν trivial ο stack να υποστηρίζει iterators (μιας και οι containers που χρησιμοποιεί για το implementation το κάνουν ήδη) αλλά αυτό δε συμβαίνει -- προφανώς by design.

 

Anyway not worth spending more time over it.

[Timonkaipumpa]

 

Εκτός από κατασκευασμένες περιπτώσεις γενικά το array πρέπει να είναι λίιιιιιγο γρηγορότερο αφού λογικά τα στοιχεία θα αποθηκεύονται inline στο αντικείμενο και όχι πίσω από ένα pointer όπως στο vector. Πάντως η ειδοποιός διαφορά τους είναι χρηστική (άλλα use cases, άλλες δυνατότητες) και όχι performance-oriented.

 

 

 

 

Μαζί σου... αλλά, πιστεύω, ότι όταν έχεις μεγέθη πίνακα τάξης 10^5 και πάνω ίσως με έψηνε να άλλαζα τον κώδικα για λίγο performance εάν άξιζε τον κόπο (και πάντα όταν το bottleneck είναι στον πίνακα).