Dynamiske datastruktuter: pekerlister[LØST]

[abcd423417984]

alikevel får du advarsel da du tar:

 

bool noe1 = true;

BOOL noe2 = noe1;

 

årsaken er som sagt at de er bygd opp litt forskjellig. bool er 1 byte, mens BOOL er 4 byte.

[Dead_Rabbit]

Heisan!

Nå har jeg jammen fått skaffa meg enda et problem jeg ,jeje!

 

#include <iostream>
using namespace std;
struct node
 {
 char navn[11];
 node* nestpkr;
 };
int main()
 {
 node* pkr;
 node* pkr2;
 node* pkr3;

 pkr = new node;
 strcpy(pkr->navn, "OLA");

 pkr2 = new node;
 strcpy(pkr2->navn, "Per");

 pkr3 = new node;
 strcpy(pkr3->navn, "KARI");

 pkr->nestpkr = pkr2;
 pkr2->nestpkr = pkr3;
 pkr3->nestpkr = pkr;

 delete pkr2;     //Dette funker ikke
 delete pkr3;     //Heller ikke dette

 cout << pkr->nestpkr->nestpkr->navn << endl;
 cout << pkr->nestpkr->navn << endl;
 cout << pkr->navn << endl;

 cin.get();

 delete pkr;
 // Her tillater kompilatoren at frigjør pkr2
 // Her også.	
 return (0);
 }	

Her er mitt lille problem og

slik er koden, når den funker. Jeg har også lagt til komentarer som viser hvordan koden funker som dere ser.

Jeg lurer nå på hvorfor den ikke funker, boka forklarer noe sånt som at dette burde gå ann, men jeg har ikke skrevet rett av noe kodeeksempel i boka så det er vel derfor det ikke går(oversett noe ?).

next er jo av typen node så jeg skjønner ikke hvorfor den ikke tilater dette(burde jo gå ann om jeg ikke hadde lagra adressen til nodene noe annet sted heller ifølge boka, men det ville isåfall vært dumt av meg

 

PS: Si ifra hvis klønete forklart

[☀ ❄]

Når du skriver pkr->nestepkr bruker du pkr2, og når du skriver pkr->nestepkr->nestepkr bruker du pkr3. Du kan ikke slette pkr2 og pkr3 før du er ferdig med å bruke dem.

[Dead_Rabbit]

Men jeg har jo lagra verdien i nestepkr som er av samme datatype, hvorfor fungerer ikke det da?

pkr->nestepkr

i nestepkr har jeg jo lagra adressen til pkr2.

Edit:

Hvis jeg f.eks har en peker som vi kaller a(en peker av typen int sier vi) som jeg setter til å peke på b(også da selfølgelig av type int). Da går det jo fint ann å opprette en ny peker som vi kaller c, sette den til å peke på b og sletter a. Vi kan da fortsatt skrive ut verdien som a pekte på.

Mulig jeg har missforstått totalt her nå azz, har noen lyst til å forklare??

Endret 18. april 2004 av zirener

[søppel]

delete deallkoerer ikke selve pekeren; den deallokerer det som pekes på.

 

#include <iostream>

using namespace std;


int main() 
{
int* a = new int(123);
int* b = new int(456);
int* c = new int(789);

// ..en peker som vi kaller a(en peker av typen int sier vi) som jeg setter til å peke på b..
a = b;

// ..Da går det jo fint ann å opprette en ny peker som vi kaller c, sette den til å peke på b..
c = b;

// og sletter a.    (det er altså verdien, det a peker på (dataene til b), som deallokeres)
delete(a);

// Vi kan da fortsatt skrive ut verdien som a pekte på
cout << *a << endl;
cout << *b << endl;
cout << *c << endl;

return(0);
} // main()

 

Hva som kommer ut her er m.a.o. ikke godt å si. Både a, b og c peker på samme data; og disse dataene er blitt deallokert via delete(a).

 

..så igjen..

 

delete deallkoerer ikke selve pekeren; den deallokerer det som pekes på.

 

Edit:

Legg merke til at adressene til dataene som a og c orginalt pekte på er "tapt for altid" .. og vi har en potensiell minnelekasje. Altså, vi får ikke deallokert dem (delete) etter vi har sagt a = b; og c = b; ..

Endret 18. april 2004 av søppel

[Steinbitglis]

Hvorfor bruker bool 1 hel byte/ 4 byte? hvis den bare kan være 0 eller 1/ false eller true, ville det være logisk at den brukte 1 bit?

[Dead_Rabbit]

Ble ikke så mye klokere ved første øyekast men skal studere det litt bedre .

Takk for svar!

[kjetil7]

Hvorfor bruker bool 1 hel byte/ 4 byte? hvis den bare kan være 0 eller 1/ false eller true, ville det være logisk at den brukte 1 bit?

Det har med effektivitet å gjøre (med hensyn til hvordan prosessoren jobber med heltall). Noe av det samme skjer når f.eks. structer blir rettet til å passe inn i 32-bits "celler".

 

F.eks:

 

typedef unsigned short Uint16;
typedef unsigned int Uint32;

struct Dummy
{
Uint16 _num1;
Uint32 _num2;
};

//...

cout << sizeof(Dummy) << endl;

 

Dette vil sannsynligvis gi 8 som resultat på en PC (har ikke sjekket selv). Søk etter "memory alignment" på google hvis du ønsker mer informasjon om emnet

[A_N_K]

Det kan nevnes at det finnes en spesialisering av std::vector for bool, mener den lagrer verdiene bitwise.

[☀ ❄]

Special Case

 

Vectors of bit values, that is boolean 1/0 values, are handled as a special case by the standard library, so that they can be efficiently packed several elements to a word. The operations for a boolean vector, vector<bool>, are a superset of those for an ordinary vector, only the implementation is more efficient.

 

Two member functions are available to the boolean vector data type. One is flip(), which inverts all the bits of the vector. Boolean vectors also return as reference an internal value that also supports the flip() member function. The other vector<bool>-specific member function is a second form of the swap() function.

[søppel]

Eller man kan bruke "Fields":

 

#include <iostream>

using namespace std;


int main() 
{
struct Test1 {
 bool bs;
};

struct Test2 {
 bool bs : 1; // Denne tar bare opp én bit!
};

Test1 t1;
Test2 t2;

t1.bs = true;
t2.bs = true;

return(0);
} // main()

 

..men husk at selv om en bit tar mindre plass .. tar koden for å jobbe mot enkelt-biter mer plass (så man sparer kanskje ikke så mye alikevell?):

 

7 {

- 0x8048604 <main>:  push  %ebp

- 0x8048605 <main+1>:  mov    %esp,%ebp

- 0x8048607 <main+3>:  sub    $0x8,%esp

- 0x804860a <main+6>:  and    $0xfffffff0,%esp

- 0x804860d <main+9>:  mov    $0x0,%eax

- 0x8048612 <main+14>:  sub    %eax,%esp

8  struct Test1 {

9  bool bs;

10  };

11

12  struct Test2 {

13  bool bs : 1; // Denne tar bare opp én bit!

14  };

15 

16  Test1 t1;

17  Test2 t2;

18

19  t1.bs = true;

- 0x8048614 <main+16>:  movb  $0x1,0xffffffff(%ebp)

20  t2.bs = true;

- 0x8048618 <main+20>:  lea    0xfffffffe(%ebp),%eax

- 0x804861b <main+23>:  orb    $0x1,(%eax)

21 

22  return(0);

- 0x804861e <main+26>:  mov    $0x0,%eax

23 } // main()

 

Man kan altså ende opp med programmer som går tregere og er større når man bruker fields. Jeg har aldri brukt dem.

[☀ ❄]

Så vidt jeg vet blir de fortsatt "aligned", så i realiteten opptar de like stor plass som en byte (minst). Så vidt jeg vet, som sagt.

[søppel]

#include <iostream>

using namespace std;


int main() 
{
struct Test {
 bool bs1 : 1;
 bool bs2 : 1;
 bool bs3 : 1;
 bool bs4 : 1;
 bool bs5 : 1;
 bool bs6 : 1;
};

Test* t = new Test;

t->bs1 = true;
t->bs2 = false;
t->bs3 = true;
t->bs4 = false;
t->bs5 = false;
t->bs6 = true;

delete(t);

return(0);
} // main()

 

GDB:

(gdb) break 16

Breakpoint 1 at 0x8048623: file test.cpp, line 16.

(gdb) run

Starting program: /mnt/home/lars/tests/test

 

Breakpoint 1, main () at test.cpp:17

17  t->bs1 = true;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000000

(gdb) step

18  t->bs2 = false;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000001

(gdb) step

19  t->bs3 = true;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000001

(gdb) step

20  t->bs4 = false;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000101

(gdb) step

23  t->bs5 = false;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000101

(gdb) step

24  t->bs6 = true;

(gdb) x/1t t

0x804a050: 00000000000000000000000000000101

(gdb) step

26  return(0);

(gdb) x/1t t

0x804a050: 00000000000000000000000000100101

 

Edit:

Altså hver enkelt tar én bit.

Endret 19. april 2004 av søppel

[☀ ❄]

Ja, men om du har to Test'er etter hverandre blir det vel et to-bits mellomrom? (Jeg er som sagt litt usikker)

[søppel]

Hm, navnet Test er en type; den tar ikke opp plass.

[kjetil7]

struct Test2 {
bool bs : 1; // Denne tar bare opp én bit!
};

Et instans av Test2 vil strengt tatt fortsatt ta opp en 1 eller 4 bytes siden den minste datatypen C++ har er char (1 byte).

 

Eks:

struct TestComp
{
  Test2 bs[6];
};
cout << sizeof(TestComp) << endl;

Resultat: 6 (hvis bool er 1 byte på din platform).

Men bs i Test2 består av kun 1 bit mens resten av structen blir "padda". Det blir kanskje tydligere hvis du bruker noe annet enn bool, slik:

 

struct MySmallInt
{
unsigned int val : 1;
};

MySmallInt i;
i.val = 43; //ooops... val i MySmallInt består av kun 1 bit
cout << i.val << endl;
cout << sizeof(i) << endl;

Resultat:

1

4 (siden int er 4 bytes på min platform)

 

 

For en enkel innføring i bit fields anbefaler jeg MSDN her:

 

MSDN: C++ Bit Fields

[søppel]

Jupp, det er m.a.o. lite vitts hvis det bare er snakk om én variabel.

[☀ ❄]

Ja, men om du har to Test'er etter hverandre blir det vel et to-bits mellomrom? (Jeg er som sagt litt usikker)

Hm, navnet Test er en type; den tar ikke opp plass.

 

Jeg mente to Test structs (det burde vel vært ganske klart?). Altså:

 

struct bit_struct {
   unsigned itsbit : 1;
};

bit_struct a;
bit_struct b;

 

gir et mellomrom på 7 (e.l.) bits mellom a og b.