Template for liste?

[Sigdal]

Jeg trenger en listestruktur der jeg kan legge inn 100 variabelpar "a" og "b" i en liste (en 100*2 array). Jeg vil så at variabelparrene i listen sorteres mhp "a", så jeg kan hente ut variabelparrene i ordnet rekkefølge, vha en indeks med stadig lavere verdier for "a" og den tilhørende verdien av "b" nedover i listen. Det samme variabelparret må kunne hentes ut (aksesseres) flere ganger, om nødvendig. Variablene a skal være av type integer og b bør være av type pointer-til-objekt Node (Node *).

 

Eksempel på Template og metoder som kan brukes for å gjøre dette?

 

/Sigdal

Endret 30. juli 2010 av Sigdal

[Sigdal]

Jøss, ble dette for vanskelig?

[[kami]]

Jeg trenger en listestruktur der jeg kan legge inn 100 variabelpar "a" og "b" i en liste (en 100*2 array). Jeg vil så at variabelparrene i listen sorteres mhp "a", så jeg kan hente ut variabelparrene i ordnet rekkefølge, vha en indeks med stadig lavere verdier for "a" og den tilhørende verdien av "b" nedover i listen. Variablene a skal være en integer og b bør være en pointer-til-objekt Node (Node *).

 

Eksempel på Template og metoder som kan brukes for å gjøre dette?

 

/Sigdal

 

#include <map>
#include <iostream>

typedef std::map<int, Node*> NodeMap_t;

int main ()
{
 NodeMap_t nodeliste;
 for (int i =0; i < 10; i++)
   nodeliste[i] = new Node(123);

 for (int i =0; i < 10; i++)
   std::cout << "Node: " << i << " = " << nodeliste[i]->getName();

 // med iteratorer
 for (NodeMap_t::const_iterator iter = nodeliste.begin(); iter != nodeliste.end(); ++ iter)
   std::cout << "Node: " << iter->first << " = " << iter->second->getName();

 NodeMap_t::iterator iFind = nodeliste.find(5);
 if (iFind != nodeliste.end())
    nodeliste.erase(iFind);
}

 

* dette lagres forøvrig ikke i noe array, men i et balansert tre (red/black tree)

* dvs at elementene ikke ligger plassert etterhverandre i minnet, som med et array, men ligger rundt om kring.

* std::map sorterer automatisk på det første elementet i paret, og krever at den har <> operatorer som funker.

* forøvrig google std::map c++ for mer eksempler.

[Sigdal]

Takker! Jeg hadde håpet det gikk an å gjøre med std::vector og bare bruke sort() metoden på kolonnen av "a" variablene og samtidig få omrokkert på b-variablene, men det går antakelig ikke da.

 

Ps: Jeg måtte editere førsteinnlegget: Jeg glemte å si at jeg må kunne lese ut de samme variabelparrene flere ganger. Jeg må også kunne aksessere elementer tilfeldig basert på ranking, f.eks: lese ut int 'a' og Node * 'b' som er den "8. beste". Gjelder koden over fortsatt da?

 

Ps2: Jeg leser at std::map kan gi problemer om man prøver å legge inn ett par (a,b) der 'a' finnes fra før. Hvordan ville en kodesnutt som sjekker for dette og evt legger til 0,001 til 'a', for å differensiere de ut, se ut i en std::map setting? (Jeg sa feil tidligere: 'a' må være av type double).

 

/Sigdal

Endret 30. juli 2010 av Sigdal

[[kami]]

Jeg må også kunne aksessere elementer tilfeldig basert på ranking, f.eks: lese ut int 'a' og Node * 'b' som er den "8. beste". Gjelder koden over fortsatt da?

 

skjønner ikke helt hva du mener? hvor er rankinga lagret? ligger det i node objektet ditt? isåfall kan det hende du vil bruke flere lister.

 

Ps2: Jeg leser at std::map kan gi problemer om man prøver å legge inn ett par (a,b) der 'a' finnes fra før. Hvordan ville en kodesnutt som sjekker for dette og evt legger til 0,001 til 'a', for å differensiere de ut, se ut i en std::map setting? (Jeg sa feil tidligere: 'a' må være av type double).

Det klarer den ikke. Det er flere alternativer her:

enten lage en:

std::map<int, std::vector<Node*> >

eller bruke noe som kalles multimap

 

i praksis er det nesten samme løsning, men min personlige smak er ofte å lage et map med en vector i.

 

std::map<int, std::vector<Node*> > nodeliste;
nodeliste[1].push_back(new Node(123));
nodeliste[1].push_back(new Node(1234));
nodeliste[0].push_back(new Node(123));

 

if (nodeliste[2].empty()) // finnes ingen elementer for index 2.

merk at å bruke [] operatorene faktisk legger til et element i mappet, om indexen ikke finnes.

nodeliste.size() == 0

nodeliste[0];

nodeliste.size() == 1

 

er dette noe du vil unngå så bruk find, samme som i eksempelet over.

 

for å iterere over mappet, kan du gjøre noe slikt:

std::map<int, std::vector<Node*> > ::iterator iFind = nodeliste.find(123);
if (iFind != nodeliste.end() )
{
  for (std::vector<Node*>::iterator i = iFind->second.begin(); i != iFind->second.end(); ++i)
  {
     Node* node = *i;
     std::cout << node->getName();
  }
}

[Sigdal]

Jeg må også kunne aksessere elementer tilfeldig basert på ranking, f.eks: lese ut int 'a' og Node * 'b' som er den "8. beste". Gjelder koden over fortsatt da?

 

skjønner ikke helt hva du mener? hvor er rankinga lagret? ligger det i node objektet ditt? isåfall kan det hende du vil bruke flere lister.

 

La oss si jeg har 100 slike tallpar som skyves inn i en std::map. Det 8. beste parret er da parret med 8. høyeste verdi i variablel a av disse hundre parrene. Jeg vil helst aksessere både a og b vha indeks (indeks i=7 her med 0-indeksering), helst mest mulig likt det å lese fra en sortert array. De er bare de 30 høyeste verdiene av a ( og tilhørende b) jeg vil lese ut, både suksessivt i serie (f.eks i=0 til i=9) og individuelt (i=5 eller i=29). Med 'rank' mener jeg bare "mhp høyeste verdi av a". Så vil jeg gjerne slette alle elementer i mapen når jeg er ferdig, så jeg kan bruke den på nytt.

/Sigdal

Endret 30. juli 2010 av Sigdal

[[kami]]

Jeg må også kunne aksessere elementer tilfeldig basert på ranking, f.eks: lese ut int 'a' og Node * 'b' som er den "8. beste". Gjelder koden over fortsatt da?

 

skjønner ikke helt hva du mener? hvor er rankinga lagret? ligger det i node objektet ditt? isåfall kan det hende du vil bruke flere lister.

 

(Double) a inneholder ett tall og en (Node *) b . La oss si jeg har 100 slike tallpar som skyves inn in en sånn std::map. Det 8. beste parret er da parret med 8. høyeste verdi i variablel a av disse hundre. Jeg vil helst aksessere både a og b vha indeks (indeks i=7 her når man starter fra i=0), helst mest mulig likt som å lese fra en sortert array. De er bare de 30 høyeste verdiene av a jeg vil lese ut. 'Rank' er mhp høyeste verdi av "a".

/Sigdal

 

ja, det kan du. map er sortert automatisk på 'a' (i ditt tilfelle)

 

da kan du iterere, fra map.begin() enten til du treffer slutten, eller 8 ganger. slik får du da de 8 "beste" verdiene.

 

map sorterer fra bunnen og opp. Må du lese andre veien, må du bruke riterator og rbegin() og rend().

[Sigdal]

Jeg synes det ble litt tungvint. Hva om jeg bare lager en egen klasse som dette:

 

class Individ {

public:

double a;

Node * b;

}

 

Så putter jeg dette i en std::vector og finner en måte å sortere disse objektene mhp "a", går ikke det?

[[kami]]

Jeg synes det ble litt tungvint. Hva om jeg bare lager en egen klasse som dette:

 

class Individ {

public:

double a;

Node * b;

}

 

Så putter jeg dette i en std::vector og finner en måte å sortere disse objektene mhp "a", går ikke det?

 

jo.

 

om du lager < operatorene så kan du sortere mhp a. (husker ikke om du også må ha > operatoren)

 

class Individ {
 public:
    double a;
    Node * b;
    inline bool operator<(const Individ & rhs) const {
     return a < rhs.a;
   }
    inline bool operator>(const Individ & rhs) const {
     return a > rhs.a;
   }
    inline bool operator==(const Individ & rhs) const {
     return a == rhs.a;
   }
}  

 

nå kan du bruke standard algoritmene for å sortere. eller du kan lage din egen.

[Zolo]

Jeg synes det ble litt tungvint. Hva om jeg bare lager en egen klasse som dette:

 

class Individ {

public:

double a;

Node * b;

}

 

Så putter jeg dette i en std::vector og finner en måte å sortere disse objektene mhp "a", går ikke det?

 

 

Du må lage kopi konstruktor for at Node *b skal bli riktig satt inn. std::vector setter inn objektene via deres kopi konstruktor.

[Sigdal]

Hvordan ville koden se ut om jeg har tre Individobjekter som ligger i en array I[1], I[2] og I[3], og disse skal leses inn i denne std::vector, sorteres mhp 'a', og tilslutt kunne hentes ut igjen (ikkedestruktivt) mhp 'a'?

 

F.eks om I[1].a=2,5, I[2].a=-2 og I[3].a=0, så skal de ligge i std::vector som {I[1], I[3], I[2]} etter sortering.

 

Klassen ser slik ut:

 

class Individ {

public:

double a;

Node * b;

int c;

}

Endret 2. august 2010 av Sigdal

[[kami]]

Hvordan ville koden se ut om jeg har tre Individobjekter som ligger i en array I[1], I[2] og I[3], og disse skal leses inn i denne std::vector, sorteres mhp 'a', og tilslutt kunne hentes ut igjen (ikkedestruktivt) mhp 'a'?

 

F.eks om I[1].a=2,5, I[2].a=-2 og I[3].a=0, så skal de ligge i std::vector som {I[1], I[3], I[2]} etter sortering.

 

Klassen ser slik ut:

 

class Individ {

public:

double a;

Node * b;

int c;

}

 

bruk lower bound for å sette inn elementet (dermed er vectoren din alltid sortert og du slipper å resortere etter hvert insert)

vector<int> nums;
nums.push_back( -242 );
nums.push_back( -1 );
nums.push_back( 0 );
nums.push_back( 5 );
nums.push_back( 8 );
nums.push_back( 8 );
nums.push_back( 11 );

vector<int>::iterator result;
int new_val = 7;

result = lower_bound( nums.begin(), nums.end(), new_val );

nums.insert( result, new_val );

rekkefølge etter insert er:-242 -1 0 5 7 8 8 11

[Sigdal]

Det skulle være vector::<Individ> og hva med copyconstructor (hvordan ser klassedeklarasjonen ut). Dtete skjønte jeg ingenting av:)

[[kami]]

class Individ
{
   Individ(double aa, Node* bb, int cc) : a(aa), b(bb), c(cc) {}
   Individ() : a(0), b(NULL), c(0) {}
   Individ(const Individ& rhs)
   {
     a = rhs.a;
     b = rhs.b;
     c = rhs.c;
   }
   Individ_c& operator = (const Individ_c& rhs)
   {
     a = rhs.a;
     b = rhs.b;
     c = rhs.c;      
   }

   inline bool operator<(const Individ & rhs) const {
     return a < rhs.a;
   }
   inline bool operator>(const Individ & rhs) const {
     return a > rhs.a;
   }
   inline bool operator==(const Individ & rhs) const {
     return a == rhs.a;
   }
   // vars
   double a;
   Node * b;
   int c;
};

int main ()
{
 vector<Individ> nums;
 nums.push_back( Individ(0, new Node(...), 0) );
 nums.push_back( Individ(1, new Node(...), 0) );
 nums.push_back( Individ(2, new Node(...), 0) );
 nums.push_back( Individ(2, new Node(...), 0) );
 nums.push_back( Individ(4, new Node(...), 0) );
 nums.push_back( Individ(5, new Node(...), 0) );
 // rekkefølge 0, 1, 2, 2, 4, 5

 vector<int>::iterator result;
 Individ ny(3, new Node(....), 0);
 // finner plassen der 'ny' skal settes inn og lagrer dette i result
 result = lower_bound( nums.begin(), nums.end(), ny );

 // setter inn 'ny' inn i vectoren i ca midten.
 nums.insert( result, ny );
 // rekkefølge 0, 1, 2, 2,3, 4, 5

 return 0;
}

 

* hakke testa å compile koden over, så kan hende det er noe jall du må fikse.

* Råder deg til å finne andre variabelnavn enn a,b & c. kall dem det de er, ie. poengsum, ranking, etc.

[Sigdal]

Leser i Deitel&Deitel boken (C++ how to program), "Performance tip: Applications with frequent insertions and deletions in the middle and/or at the extremes of a container normally use a LIST, due to its efficient implementation of insertion and deletion anywhere in the data structure."

 

Nå blir lengden på denne maksimalt ca 500 objekter(dvs 125.000 omrokkeringer internt i en std::vector worst case eller forventning på 62.500 omrokkeringer for å sortere, når alle tall for a er like sannsynlige.) Spørsmål er om det ikke da er mer effektivt å legge Individ-objektene innn i en std::liste istedenfor std::vector? Beklager at det blir mye fram og tilbake her nå. Hvordan ville koden isåfall se ut?

Endret 4. august 2010 av Sigdal

[[kami]]

Leser i Deitel&Deitel boken (C++ how to program), "Performance tip: Applications with frequent insertions and deletions in the middle and/or at the extremes of a container normally use a LIST, due to its efficient implementation of insertion and deletion anywhere in the data structure."

 

Nå blir lengden på denne maksimalt ca 500 objekter. Spørsmål er om det ikke er mer effektivt da å legge Individ-objektene innn i en std::liste istedenfor std::vector? Beklager at det blir mye fram og tilbake her nå. Hvordan ville koden da se ut?

 

bytt ut <std::vector> med <std::list> og koden ovenfor skal funke. Merk at du ikke kan bruke liste[123] = 123, du må bruke iteratorer.

 

Om lengden forandrer seg mye, og du hele tiden setter inn i midten er liste nok lurere med liste (mye insert & erase). Men om størrelsen holder seg noenlunde konstant er vector best.

Grunnen til dette er at objektene ligger etterhverandre i minnet med vector, så om du sletter noe i midten, må den flytte halvparten av elementene i vecoren en posisjon mot starten for å oppnå dette (dette skjer automatisk, forresten). Dette slipper du med en liste, for her ligger ting spredd rundt om kring.

 

Uansett bør du ikke overtenke dette for mye;

du vil antagligvis uansett ikke merke forskjell på performance på dagens maskiner så lenge dette er noe som ikke kjører flere tusen ganger i sekundet. Mitt råd til deg er å lage noe som funker, og kjører det tregt da, kan du optimere det.

Endret 4. august 2010 av [kami]

[Sigdal]

Beklageligvis funker det ikke i VC6++ (Det er vel '98 versjonen av ANSI C++ som gjelder her). Ja, jeg burde oppgradere :-/

[[kami]]

Beklageligvis funker det ikke i VC6++ (Det er vel '98 versjonen av ANSI C++ som gjelder her). Ja, jeg burde oppgradere :-/

 

 

burde fortsatt funke.. hmm, hvilke feilmeldinger får du, som du ikke hadde med vector?

 

uansett, vc6 er evig gammel, hent ned 2010 gratis fra microsoft

http://www.microsoft.com/express/windows/

[Sigdal]

Jeg kompilerte ikke eksempelet med std::vector. Jeg får 10 feilmeldinger bare når jeg kompilerer deklarasjonen for Individklassen og Nodeklassen. Ca 40 feil med hele koden. Hm.. det blir vel at jeg må skrive rutinen selv vha arrays og pointere da, selvom det blir uelegant..

[Sigdal]

Det ble en funksjon som dette:

void storenode(Individ Ind){
Individ Temp[size] = {0}; //Lager en array av Node-objekter initialisert til 0.
int k,l, i=0, j=0;
while (I[i].a > Ind.a) i++;
if (I[i].a == Ind.a) i++; 
l=i;
for (k=i; k<size-l; k++){ //copy remaining elements to Temp[]
	Temp[j]=I[k];
	j++;
}
I[i] = Ind; i++; j=0;
for (i; i<size; i++){ //copy back to I[]
	I[i]=Temp[j];
	j++;
}

}

 

Det blir mye kopiering og sletting, men tar bare ca 1 sekund å kalle 500 ganger, så det er ikke så ille. Som du også sa.