[C] dynamisch declareren.

[Verwijderd]

Ik heb voor een klein tooltje waar ik mee bezig ben een structure met daarin 3 "velden". In deze structure komen een soort van "records". voor elk record een nieuwe instantie van zow een structure dus. Alleen weet ik pas tijdens run-time hoeveel van die dingen ik nodig ga hebben. En om het zootje effiecient (en compatibel) te houden wil ik dus een dynamisch aantal van die dingen declareren tijdens runtime. hoe ga ik dit voor elkaar krijgen? Iemand een idee? Bij voorbaat dank!

P.S.: me struct ziet er zo uit (maar dat mag eigenlijk nix uitmaken natuurlijk ):

C:

struct file_info {
  int num;
  unsigned long start;
  unsigned long end;
};

[Onno]

Dat doe je met malloc(). In je C handleiding staan daar vast wel voorbeelden van.

[_Squatt_]

Als ik het goed begrijp wil je dus een variabel aantal structs hebben?

Dan kun je met malloc() geheugen reserveren:

C:

int aantal_structs = 5;
struct file_info *fp = (struct file_info *) malloc( aantal_structs * sizeof(struct file_info));

// Met fp[0] t/m fp[4] kun je bij je structs komen. Bijvoorbeeld:
fp[2].num = 3;

// Als je klaar bent met de structs geef je het geheugen weer vrij:
free( fp);

Dit zou overigens in elk boek over C wel moeten staan.

[ Voor 0% gewijzigd door _Squatt_ op 02-01-2005 12:28 . Reden: spuit 11 :P ]

[Verwijderd]

Ja malloc(); ken ik wel. die alloceert X aantal bytes. Dus als ik het goed begrijp, moet ik dit ongeveer doen:

code:

file_info *ptr;

ptr = malloc(aantal_records * size_van_1_record);

zoiets?

edit: oh, iemand geeft etzelfde antwoord als ik wat ik wou suggereren terwijl ik aan het typen was. lang leve het internet

[ Voor 24% gewijzigd door Verwijderd op 02-01-2005 12:28 ]

[windancer]

Yep, of je gebruikt het broertje van malloc : calloc

C:

file_info *ptr;

ptr = calloc(aantal_records, size_van_1_record);

dan worden alle waarden direct netjes op "0" geinitialiseerd.

Verwijderd schreef op zondag 02 januari 2005 @ 12:28:
Ja malloc(); ken ik wel. die alloceert X aantal bytes. Dus als ik het goed begrijp, moet ik dit ongeveer doen:

code:

file_info *ptr;

ptr = malloc(aantal_records * size_van_1_record);

zoiets?

edit: oh, iemand geeft etzelfde antwoord als ik wat ik wou suggereren terwijl ik aan het typen was. lang leve het internet

[MSalters]

windancer schreef op zondag 02 januari 2005 @ 13:10:
Yep, of je gebruikt het broertje van malloc : calloc
dan worden alle waarden direct netjes op "0" geinitialiseerd.
[...]

Nou ja, alle integers en chars. Floats en pointers geldt dat iha niet voor.

[tofus]

Volgens mij is de enige nette manier om dynamisch lijsten van dit soort records op te slaan, de manier die gebruik maakt van zgn. 'linked list'. Linked lists zijn, hoewel niet standaard opgenomen in de syntax van C, eigenlijk zo standaard dat zo'n beetje elk boek over programmeer-technieken wel uitlegt hoe ze werken.

Voordeel van linked lists: je alloceert records pas op het moment dat je ze nodig hebt. Je code 'vreet' dus geen onnodige geheugenruimte weg. Dynamisch alloceren met een (virtuele) array en malloc() kan natuurlijk ook, maar dan moet je op het moment van de malloc al weten hoeveel records je precies nodig gaat hebben (wat bijna op hetzelfde neerkomt als wanneer je ze gewoon statisch declareert), en kan je ze dus niet meer 1 voor 1 dynamisch declareren (of je moet gaan vloeken in de kerk door realloc() te gebruiken op zulke kleine data-strukturen)..

Ik denk dus echt dat linked list voor dit probleem de beste oplossing zijn. Zoeken op google met de termen 'linked list' en 'C' moet zeker wat opleveren.

voorbeeldje uit 1 van mijn eigen linked list modules (waarschuwing: dit is alleen bedoeld om je een indruk te geven van de struktuur van linked lists; je zult de code aan moeten passen/uit moeten breiden voor je eigen datastrukturen):

code:

// list.c - Implementation of the linked list functionality.

#ifndef IN_LIST_CODE
#define IN_LIST_CODE

#define LIS_ID  "$Id: list.c,v 0.0.8.1 2004/10/06 18:57:25 tofus Exp $"

// This code is released under the Berkeley Software Distribution
// (BSD) license.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <input.h>
#include <list.h>
#include <parser.h>

// Module version information
const char lis_id[] = LIS_ID;

plist list_destroy( plist p ) {
  if ( p ) {
    list_destroy( p->next );

    if ( p->data ) {
      free( (void*) p->data );
    }
    free( (void*) p );
  }

  return p;
}

plist list_add( const plist p, const void *q ) {
  plist r = (plist) malloc( sizeof( list ) );

  if ( r ) {
    r->data = (void*) q;
    r->next = p;
  }

  return r;
}

plist list_remove( plist p, void *q ) {
  plist r;
  
  if ( p ) {
    if ( p->data == q ) {
      if ( q ) {
        free( (void*) q );
      }

      r = p->next;

      free( (void*) p );

      return r;
    } else {
      p->next = list_remove( p->next, q );
    }
  }

  return p;
}

plist list_join( const plist p, const plist q ) {
  if ( p ) {
    p->next = list_join( p->next, q );
    
    return p;
  } else return q;
}
    
plist list_loadfile( const char *s ) {   
   char buf[prs_LINELENGTH];
   plist p = (void*) 0;
   FILE *f;
   char *t;

   if ( ( s ) && (f = fopen( s, "r" )) ) {
     while ( fread_line( f, buf, prs_LINELENGTH ) ) {
       t = (char*) malloc ( strlen( buf ) );
       strcpy( t, buf );
       
       p = list_add( p, t );
     }

     fclose(f);     
   }
   
   return p;
}

#endif  // ifndef IN_LIST_CODE

// End of ../engine/list.c

[ Voor 67% gewijzigd door tofus op 02-01-2005 15:14 ]

[elevator]

tofus schreef op zondag 02 januari 2005 @ 15:08:
Voordeel van linked lists: je alloceert records pas op het moment dat je ze nodig hebt. Je code 'vreet' dus geen onnodige geheugenruimte weg.

Maar als je niet sequentieel door je elementen heen wil lopen is het volgens mij niet zo'n efficiente manier?

Dynamisch alloceren met een (virtuele) array en malloc() kan natuurlijk ook, maar dan moet je op het moment van de malloc al weten hoeveel records je precies nodig gaat hebben (wat bijna op hetzelfde neerkomt als wanneer je ze gewoon statisch declareert).

Niet helemaal - stel je voor je leest een file uit met in de header het aantal records - met de malloc() manier kan je dan vrij gemakkelijk het juiste aantal elementen alloceren, dat gaat met een vaste array wat moeilijker

[tofus]

elevator schreef op zondag 02 januari 2005 @ 15:12:
[...]

Maar als je niet sequentieel door je elementen heen wil lopen is het volgens mij niet zo'n efficiente manier?

Niet echt minder efficient dan niet-sequentieel door een array van elementen lopen...

Maar inderdaad, linked lists hebben natuurlijk ook nadelen. Het is een wat complexere struktuur dan bijv. arrays, dus is het doorzoeken van zo'n struktuur ook iets ingewikkelder. Maar als je je code goed in elkaar zet, geven linked lists (mits correct gebruikt) weldegelijk performance (en code-maintainance) voordelen.

[...]

Niet helemaal - stel je voor je leest een file uit met in de header het aantal records - met de malloc() manier kan je dan vrij gemakkelijk het juiste aantal elementen alloceren, dat gaat met een vaste array wat moeilijker

Inderdaad. Als je al weet hoeveel records je nodig gaat hebben voordat je de malloc gaat uitvoeren, kun je (technisch bekeken) inderdaad net zo goed een malloc gebruiken. Maar ik ging hier even uit van het abstracte geval waarin je dus van te voren niet weet hoeveel records je nodig gaat hebben (wat ongeveer ook de strekking van de topic-starter was, toch?).

[ Voor 9% gewijzigd door tofus op 02-01-2005 15:21 ]

[Onno]

tofus schreef op zondag 02 januari 2005 @ 15:18:
Maar ik ging hier even uit van het abstracte geval waarin je dus van te voren niet weet hoeveel records je nodig gaat hebben (wat ongeveer ook de strekking van de topic-starter was, toch?).

Nou, volgens mij zegt ie dat ie dat wel weet, at runtime. En dan voegt een linked list weinig toe. Maar als je een dynamisch aantal elementen hebt is het een betere oplossing ja.

[elevator]

tofus schreef op zondag 02 januari 2005 @ 15:18:
Niet echt minder efficient dan niet-sequentieel door een array van elementen lopen...

Dat lijkt me wel? Als je bv. een 'filepicker' pakt (even aansluitend op de struct namen die gebruikt worden), dan is het naar pagina 'xx' springen in een Linked list gewoon mer weer dan dan in een array?

Verder lijkt het me in dit geval complexiteit toevoegen, die niet per se nodig is

[Robtimus]

tofus schreef op zondag 02 januari 2005 @ 15:08:

code:

plist list_destroy( plist p ) {
  if ( p ) {
    list_destroy( p->next );

    if ( p->data ) {
      free( (void*) p->data );
    }
    free( (void*) p );
  }

  return p;
}

[mierenneuker-modus]
Waarom return je hier een waarde? Als p NULL is dan return je NULL, anders return je een pointer naar geheugenruimte die je net hebt gefreed. In beide gevallen dus een pointer waar je niks aan hebt.
[/mierenneuker-modus]

[tofus]

IceManX schreef op zondag 02 januari 2005 @ 15:56:
[...]
[mierenneuker-modus]
Waarom return je hier een waarde? Als p NULL is dan return je NULL, anders return je een pointer naar geheugenruimte die je net hebt gefreed. In beide gevallen dus een pointer waar je niks aan hebt.
[/mierenneuker-modus]

Hehe...omdat in de declaratie van de functie een return-type wordt aangegeven, isset zeg maar 'netjes' om dan ook een waarde terug te geven in dat datatype. Alleen de verzameling functies met als return-type 'void' behoeft geen return() statement.

Natuurlijk hebben compilers een stuk minder moeite met het weglaten van return() statements, maar professoren in de informatica helaas niet

Eigenlijk mierenneuk ik dus nog meer dan jij

PS: de reden dat dit 'netjes' is, is bijv. omdat de free() functie die gebruikt wordt in deze code makkelijk kan worden vervangen door een andere implementatie, zonder dat de code voor de linked list hoeft worden aangepast; deze geeft immers gewoon het resultaat van de free() functie door; wijzigd dit resultaat, dan wijzigd de return-waarde van list_destroy automatisch mee... Niet dat dit in dit specifieke geval nou zo nodig is, maar wel zo netjes (helemaal als je 't op andere plaatsen in je code, met andere functies, ook doet)...

BTW: jouw kritiek zou ook opgaan voor de free() functie zelf; waarom returned die een pointer en geen void? Blijkbaar kan de return-waarde van free() dus weldegelijk zinnige info bevatten. Nou, precies die info wordt op deze manier ook door list_destroy() doorgegeven.

[ Voor 43% gewijzigd door tofus op 02-01-2005 17:29 ]

[Onno]

tofus schreef op zondag 02 januari 2005 @ 17:19:
Hehe...omdat in de declaratie van de functie een return-type wordt aangegeven,

Ja, en dan is de vraag dus waarom dat zo is.

BTW: jouw kritiek zou ook opgaan voor de free() functie zelf; waarom returned die een pointer en geen void? Blijkbaar kan de return-waarde van free() dus weldegelijk zinnige info bevatten. Nou, precies die info wordt op deze manier ook door list_destroy() doorgegeven.

free() geeft geen pointer terug.

[tofus]

free() geeft geen pointer terug.

ehhh...weird; ik verkeer al jaren in de veronderstelling dat free() een void* teruggeeft; maar het is inderdaad gewoon een void. Bennik vast in de war met ObjectPascal (er staat me in ieder geval iets bij van een free() functie die een null-pointer returned als de pointer die je meegeeft als parameter geen geldige (als in: op te schonen) pointer bevat)....

maar inderdaad, de free() uit stdlib.h doet dat dus absoluut niet...

En in dat geval is mijn code dus gewoonweg foutief: ik return een waarde die er niet is, en kan ik je hartelijk bedanken voor je mierenneukerij

...ik zal 't meteen ff fixen

[MSalters]

Wat fouter is, je retourneert een ongeldige pointer. Dat kan in theorie een segfault oid veroorzaken. Een pointerwarde die je gefree'd hebt mag je daarna niet meer kopieren. De reden is dat je C lib dat adres teruggegeven kan hebben aan het OS, met als gevolg dat het adres niet meer bestaat.

[Verwijderd]

Aangezien dit topic over een zelfde probleem gaat, reageer ik hier.

C:

class Man *ptr = (class Man *) malloc( spelers * sizeof(class Man *));

Ik ben bezig met een mini game. Ik heb een klasse Man en een klasse Vrouw die worden afgeleid uit een klasse Ai. Wanneer ik deze code als hierboven gebruik dan gaat er iets niet helemaal goed. Wanneer ik

C:

        Man *blaat = new Man;

Gebruik, dan gaat het wel goed. Ik krijg dan ook de class met het een bepaalde afbeelding op mijn scherm te zien. Gebruik ik die manier zoals hier in het topic dan krijg ik niets te zien. Hij zal dus misschien de ruimtes wel vrijmaken maar nog niet vullen?

Iemand die iets weet?

Alvast bedankt

[Verwijderd]

dat komt omdat je klassen moet instantieren met de new operator.

[Verwijderd]

Verwijderd schreef op dinsdag 04 januari 2005 @ 15:44:
dat komt omdat je klassen moet instantieren met de new operator.

De vraag van mij aan jou is nu dus geworden: Hoe kan ik een variable aantal klassen aanmaken onder runtime? Ben nog niet zo lang bezig met klassen namelijk.

Ik dank u

[Woy]

In c heb je toch geen Classes? Dus dan zal het wel c++ zijn. Dan doe je dat gewoon op de volgende manier

C++:

Man *blaat = new Man[ aantal ];
for( int i =0; i < aantal; i++ )
{
    blaat[ i ] = new Man();
}

Maar mijn c++ is op het moment niet helemaal up to date dus ik kan het verkeerd hebben.

[Woy]

tofus schreef op zondag 02 januari 2005 @ 15:18:
[...]

Niet echt minder efficient dan niet-sequentieel door een array van elementen lopen...

Maar inderdaad, linked lists hebben natuurlijk ook nadelen. Het is een wat complexere struktuur dan bijv. arrays, dus is het doorzoeken van zo'n struktuur ook iets ingewikkelder. Maar als je je code goed in elkaar zet, geven linked lists (mits correct gebruikt) weldegelijk performance (en code-maintainance) voordelen.

Het is wel degelijk een stuk minder efficient als je er niet-sequentieel doorheen loopt. aangezien je gemiddeld n/2 elementen langsmoet voordat je bij het goede element bent. Bij een array heb je in een keer het goede element te pakken.

Een linked list heeft inderdaad een hoop voordelen, maar juist de snelheid van het benaderen van elementen is een van de voordelen van een Array.

[Soultaker]

tofus schreef op zondag 02 januari 2005 @ 15:08:
Volgens mij is de enige nette manier om dynamisch lijsten van dit soort records op te slaan, de manier die gebruik maakt van zgn. 'linked list'.

Er zijn talloze geschikte datastructuren. Met een linked list kun je makkelijk queues en stacks implementeren en daarom worden ze in besturingssystemen veel gebruikt, maar er zijn meer opties; denk aan allerei boomstructuren, gesorteerde lijsten, hash tables, dynamische arrays enzovoorts.

Een dynamische array is naar mijn mening ongeveer net zo simpel als een linked list: je houdt simpelweg de grootte en de capaciteit van je datastructuur bij en alloceert om de zoveel tijd een groetere array:

C:

// Declaratie
typedef struct data { 
  int foo, bar;
} data_t;   // type van de elementen in de array

struct array {
  unsigned size, capacity;
  data_t *elements;
} array;

// Initialisatie
array.size = 0;
array.capacity = 16; // willekeurige zinnige waarde
array.elements = (data_t*)mallloc(array.capacity * sizeof(data_t));

void add_element(data_t *data)
{
  if(array.size == array.capacity) {
    array.capacity *= 2;
    array.elements = (data_t*)realloc(array.capacity * sizeof(data_t));
  }
  array.elements[array.size] = *data;
  ++array.size;
}

Andere operaties worden op vergelijkbare wijze geimplementeerd. Een dynamische array heeft een aantal voordelen ten opzichte van linked lists:
• array.elements is een array, waar je dus op kunt indexeren;
• een dynamische array is vaak efficienter in geheugengebruik dan een linked list, ook al alloceer je maximaal twee keer (en gemiddeld anderhalf keer) zoveel elementen als je daadwerkelijk gebruikt;
• een dynamische array hoeft maar een logaritmisch aantal allocaties uit te voeren, terwijl een linked list lineaire aantal allocaties uitvoert;
• een dynamische array is vaak sneller, zeker als je 'm lineair doorloopt, omdat je dan geen pointers hoeft te volgen en opvolgende elementen naast elkaar in het geheugen staan, waardoor de efficiëntie van de cache (erg belangrijk op moderne processoren) aanzienlijk groter is.
Nadelen zijn dat het toevoegen en verwijderen van elementen in het midden van een grote array kostbaar is (en daarom doe je dat ook meestal niet).

of je moet gaan vloeken in de kerk door realloc() te gebruiken op zulke kleine data-strukturen..

Wat is daar vloeken in de kerk aan? Waarom zou je beter 1000 keer malloc kunnen aanroepen dan 10 keer realloc?

edit:
Meer voordelen en nadelen van linked lists ten op zichte van arrays zijn te vinden op Wikipedia: Linked lists vs. arrays.

[ Voor 13% gewijzigd door Soultaker op 04-01-2005 16:20 ]

[Soultaker]

rwb schreef op dinsdag 04 januari 2005 @ 15:56:
In c heb je toch geen Classes? Dus dan zal het wel c++ zijn. Dan doe je dat gewoon op de volgende manier

C++:

Man *blaat = new Man[ aantal ];
for( int i =0; i < aantal; i++ )
{
    blaat[ i ] = new Man();
}

Maar mijn c++ is op het moment niet helemaal up to date dus ik kan het verkeerd hebben.

Klopt inderdaad geen fluit van, je hebt zeker Java zitten programmeren.

Op het moment dat je een array van objecten alloceert, worden de objecten ook al geinitialiseerd. (En je kunt zo dus alleen de default constructor, zonder argumenten, gebruiken.) Regel 1 van jouw code is dus al correct.

Natuurlijk kun je daarna wel alsnog andere objecten over de elementen heen kopiëren; zo bijvoorbeeld:

C++:

Man *blaat = new Man[aantal];
for(int i = 0; i < aantal; ++i)
    blaat[i] = Man();    // let op: hier staat dus GEEN 'new' bij!
delete[] blaat;    // let op: je gebruikt hier dus 'delete[]' en GEEN 'delete'!

Maar dat is dus eigenlijk alleen zinnig als je specifieke argumenten aan de constructors wilt meegeven (en bovendien roep je technisch gezien voor elk object eerst de default constructor aan, daarna een specifieke constructor, daarna de assignment operator, en dan nog een destructor; dat zou relatief kostbaar kunnen zijn, maar in veel gevallen kan de compiler dat aardig optimaliseren).

[ Voor 24% gewijzigd door Soultaker op 04-01-2005 16:24 ]

[Woy]

Soultaker schreef op dinsdag 04 januari 2005 @ 16:15:
[...]

Klopt inderdaad geen fluit van, je hebt zeker Java zitten programmeren.

offtopic:
Hehe, ja tijdens het typen twijfelde ik al daarom zette ik het er nog maar even bij. Ben idd een beetje in de war met C#. Werk zelf eigenlijk nooit met c++ maar alleen met c/ c#

[ Voor 67% gewijzigd door Woy op 04-01-2005 17:03 ]

[Onno]

Verwijderd schreef op dinsdag 04 januari 2005 @ 15:34:
Aangezien dit topic over een zelfde probleem gaat, reageer ik hier.

C:

class Man *ptr = (class Man *) malloc( spelers * sizeof(class Man *));

Afgezien van alles wat al gezegd is, is er natuurlijk nog iets heel erg fout aan deze code, iets wat mensen vrij vaak fout doen in C (maar wat je C compiler waarschijnlijk nooit als fout zal zien): je vraagt om geheugen voor pointers naar Man, in plaats van geheugen voor Man instanties zelf.

Dit zou of (en hierbij maak ik er maar even een struct van om het geldige C te maken )

C:

struct Man *ptr = (struct Man *) malloc(spelers * sizeof(struct Man));

of

C:

struct Man **ptr = (struct Man **) malloc(spelers * sizeof(struct Man *));

moeten zijn.

[Verwijderd]

het kan wel met malloc though... gaat misschien wat ver....

het volgende is voldoende om 10 Man instanties te krijgen:

code:

Man* mannen = new Man[10];

het kan dus ook met malloc, maar dan moet je de constructor min of meer met de hand uitvoeren, dit kan als volgt:

code:

Man* mannen = reinterpret_cast<Man*>(malloc(10 * sizeof(Man));
for (int i=0; i<10; i++)
{
    ::new(mannen+i) Man();
}

[MSalters]

rwb schreef op dinsdag 04 januari 2005 @ 15:56:
In c heb je toch geen Classes? Dus dan zal het wel c++ zijn. Dan doe je dat gewoon op de volgende manier

C++:

Man *blaat = new Man[ aantal ];
for( int i =0; i < aantal; i++ )
{
    blaat[ i ] = new Man();
}

Maar mijn c++ is op het moment niet helemaal up to date dus ik kan het verkeerd hebben.

Er zijn syntactisch juistere oplossingen, maar dat is al eerder gezegd (nou ja, ik heb de opmerking dat je delete[] mist nog niet gezien). Erger is, dat je de zaak fundamenteel niet zo wil aanpakken. Veel beter is:

C++:

std::vector<Man> blaat ( aantal );

Ja, dat is alles. Niet new, new[], delete[] etcetera. Wel desgewenst vector::resize( ) of vector::clear( ), en switchen naar std::list<Man> blaat( aantal ) is ook triviaal.