liste speicher reservieren und wieder freigeben

AbsoluterBeginner

hallo, ich soll eine klasse schreiben welche eine beliebeige anzahl an zeilen einliest und diese speichert. dieses sollen mit einem index angesprochen ausgegeben werden.
ebenso soll mit einem index und einem string, der string an der bestimmten position geaendert werden.
und die klasse soll die eingelesenen zeilen sortieren koennen (auf und absteigend) sowie auch wieder unsortieren. (ursprung herstellen)
dazu einige fragen:
1.)
ich dachte an list, da die werte sortiert werden koennen, aber es nicht standardmaessig von alleine sortiert wird und ich mittels index die liste durchgehen kann (auslesen und aenern bestimmter zeilen)
oder wuerdet ihr einen anderen containertyp empfehlen?

2.)
denke ich nicht dass ich daran vorbei kommen werde dass ich in der klasse zwei listen haben werde.
eine fuer den originalen zustand und eine fuer den aktuellen (koennen gleich sein aber eben auch verschieden, wenn der aktuelle sortiert wurde)
oder wuerde jemandem was einfacheres einfallen?

3.)
mache ich das erste mal was mit containern und denke ich sollte auch den speciher selbst verwalten.
also habe ich einmal ein testprogramm gemacht um zu sehen ob es kompiliert:

list<string>* lp = new list<string>;

 delete lp;

wuerde sowas in ner klasse funktionieren?

also die erste zeile im konstruktor, die zweite im destruktor.
bin mir nicht sicher ob mit dem delte der komplette speicher wieder freigegeben wird (und somit die liste komplett geloescht wird)

vielen dank fuer dir hilfe!!

Nexus

AbsoluterBeginner schrieb:

1.)
ich dachte an list, da die werte sortiert werden koennen, aber es nicht standardmaessig von alleine sortiert wird und ich mittels index die liste durchgehen kann (auslesen und aenern bestimmter zeilen)
oder wuerdet ihr einen anderen containertyp empfehlen?

Du hast Random Access (wahlfreier Zugriff über einen Index), was std::list ungeeignet macht. Zu empfehlen sind std::vector und std::deque .

AbsoluterBeginner schrieb:

2.)
denke ich nicht dass ich daran vorbei kommen werde dass ich in der klasse zwei listen haben werde.
eine fuer den originalen zustand und eine fuer den aktuellen (koennen gleich sein aber eben auch verschieden, wenn der aktuelle sortiert wurde)
oder wuerde jemandem was einfacheres einfallen?

Du kannst in einem Container auch nur die Indizes speichern. Also wenn du eine Liste sortierst, bringst du parallel einen Container in die entsprechende Reihenfolge. Dann kannst du den Urprungszustand rekonstruieren. Eine Alternative zu Indizes wären auch Zeiger.

AbsoluterBeginner schrieb:

3.)
mache ich das erste mal was mit containern und denke ich sollte auch den speciher selbst verwalten.

Nein, ein Vorteil der Container besteht ja gerade darin, dass dir die Arbeit der Speicherverwaltung abgenommen wird. Du kannst also den Container ganz normal auf dem Stack deklarieren, im Destruktor wird alles aufgeräumt.

Beispielsweise (auf www.cplusplus.com findest du mehr Infos zur STL):

std::deque<std::string> Deque;
Deque.push_back("hallo");

AbsoluterBeginner

Du kannst in einem Container auch nur die Indizes speichern. Also wenn du eine Liste sortierst, bringst du parallel einen Container in die entsprechende Reihenfolge. Dann kannst du den Urprungszustand rekonstruieren. Eine Alternative zu Indizes wären auch Zeiger.

erst ein mal danke fuer deine tips, schaue gerade ob ich vector oder deque verwenden werde.
zu dem oben zitierten, weiß ich nicht ob ich dich richtig verstehe.
du meinst damit ich nicht die strings von einem kontainer in den anderen kopieren muss (was ja der zeitaufwendigere teil ist) kann ich einen zweiten container verwenden welcher mir die originalen indizes speichert.
also koennte dann ca. so aussehen:
container mit strings:
1...Hallo Welt
2...Zweite Zeile
3...Drei

container mit indizes:
1...1
2...2
3...3
(nur hier muesste ich ja irgendwie gleich auf die adressen der zeilen (von container eins) kommen oder?) irgenwie mit pointer oder so denke ich waere geschickt.
denn wenn ich die zweite zeile (im ersten container) aendere, muss ich dies ja in diesem container auch aendern - was in wirklichkeit ja nur eine andere speicher adresse ist.
oder ist es in einem vector, wenn ich den wert (wie zb gesagt von zeile zwei aendere) die neue zeile an der gleichen position steht wie zuvor, nur ein anderer text??

nun sortiere ich ersteren container:
1...Drei
2...Hallo Welt
3...Zweite Zeile
habe aber in meinem zweiten container immer noch die original sortierung.

ich denke so hast du es gemeint, nun meine fragen dazu
1. sehe ich weder bei vector noch bei deque eine sort funktion, wie sollte ich dann auf / absteigend sortieren?

2. wie oben schon gefragt wie speichere ich die adressen der stings von container eins in container zwei?

danke!!

Nexus

AbsoluterBeginner schrieb:

1. sehe ich weder bei vector noch bei deque eine sort funktion, wie sollte ich dann auf / absteigend sortieren?

Du solltest auch die globale Funktion std::sort (zu finden im Header <algorithm> ) verwenden.

AbsoluterBeginner schrieb:

2. wie oben schon gefragt wie speichere ich die adressen der stings von container eins in container zwei?

Das wird ein wenig mühsamer.

Grundsätzlich gibt es mehrere Möglichkeiten. Das einfachste wäre, du würdest eine Struktur/Klasse schreiben, die sowohl einen std::string als auch einen int aufnehmen würde. Der Container würde dann diesen Typen enthalten. Am Anfang füllst du den Container mit entsprechenden Strings und schaust, dass jedes Objekt richtig nummeriert ist (über den int -Member).

Dann hast du einen Container mit folgendem Inhalt (fett ist der Index, in Klammern das jeweilige Objekt der Klasse):

[b]0:[/b] (0, Hallo Welt)
[b]1:[/b] (1, Zweite Zeile)
[b]2:[/b] (2, Drei)

Wenn du das nun nach den Strings sortierst, hast du Folgendes:

[b]0:[/b] (2, Drei)
[b]1:[/b] (0, Hallo Welt)
[b]2:[/b] (1, Zweite Zeile)

Schlussendlich kannst du den Container wieder nach den int s sortieren und erhältst die ursprüngliche Reihenfolge.

Um zwei mögliche Sortierkriterien für das gleiche Objekt zu definieren, schaust du dir am besten das Konzept der Funktionszeiger bzw. Funktoren (=Funktionsobjekten) an. In diesem Thread habe ich das kurz erklärt.

AbsoluterBeginner

vielen dank fuer die tipps.
habe mich entschieden vector mit pairs zu nehmen.
habe einen code gebastelt (ohne klasse nur um zu testen)
dieser sieht folgender massen aus:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/*

*/

bool sortAsc(pair<int, string> a, pair<int, string> b) 
{
   return (a.second < b.second);
}

bool sortDsc(pair<int, string> a, pair<int, string> b) 
{
   return (a.second > b.second);
}

bool sortOrig(pair<int, string> a, pair<int, string> b) 
{
   return (a.first < b.first);
}

int main()
{   
   vector<pair<int, string> > vec;   
   pair<int, string> element;

   string str;
   int elidx = 0;
   for(int i = 0; i<5; ++i)
   {
     cin >> str;
     element = make_pair (elidx, str);
     vec.push_back (element);
     ++elidx;
   }

   cout << "ALL ELEMENTS:\n";
   for (size_t i=0; i<vec.size(); ++i)
    cout << vec.at(i).first << " " << vec.at(i).second << endl;

   sort (vec.begin(), vec.end(), sortAsc);

   cout << "ALL ELEMENTS ASC:\n";
   for (size_t i=0; i<vec.size(); ++i)
    cout << vec.at(i).first << " " << vec.at(i).second << endl;

   sort (vec.begin(), vec.end(), sortOrig);

   cout << "ALL ELEMENTS ORIGINAl:\n";
   for (size_t i=0; i<vec.size(); ++i)
    cout << vec.at(i).first << " " << vec.at(i).second << endl;

   sort (vec.begin(), vec.end(), sortDsc);

   cout << "ALL ELEMENTS DESC:\n";
   for (size_t i=0; i<vec.size(); ++i)
    cout << vec.at(i).first << " " << vec.at(i).second << endl;

   return 0;

}

funktioniert auch so weit.
nur habe ich es nicht geschafft eine sortier funktion zu schreiben die sowohl asc als auch desc sortiert.

habe versucht bei desc so zu machen:
ich habe diese funktion

bool sortAsc(pair<int, string> a, pair<int, string> b) 
{
   return (a.second < b.second);
}

und rufe sort dann mittels:

sort (vec.begin(), vec.end(), !sortAsc);

auf.

geht aber leider nicht, ich verstehe nicht warum ich will einfach das zureuckgegebene von der funktion invertieren.
bin durch deinen anderen post leider nicht schlauer geworden wie ich das effektiv loesen koennte.

sollte doch mit einer sortier funktion gehen oder?

(die zweite, welche nach int sortiert werde ich mir nicht ersparen koennen denke ich)

vielen dank, werde ggn abend mal die loesung mittels klasse versuchen (aber zuerst warte ich ein mal ob mein ansatz gut ist :))

danke!

Nexus

AbsoluterBeginner schrieb:

vielen dank fuer die tipps.
habe mich entschieden vector mit pairs zu nehmen.

Gute Idee. Damit du nicht jedes Mal den ganzen Typ aufschreiben musst, empfehle ich ein Typedef:

typedef std::pair<int, std::string> MyPair; // halt passender Name

AbsoluterBeginner schrieb:

geht aber leider nicht, ich verstehe nicht warum ich will einfach das zureuckgegebene von der funktion invertieren.

Du übergibst einen Funktionszeiger, und dieser kann natürlich nicht invertiert werden. Du kommst nicht darum herum, eine zweite Funktion zu schreiben. Aber diese kann ja auch die erste aufrufen:

bool SortDsc(const MyPair& Left, const MyPair& Right) // besser Const-Referenz!
{
    return !SortAsc(Left, Right);
}

AbsoluterBeginner schrieb:

(die zweite, welche nach int sortiert werde ich mir nicht ersparen koennen denke ich)

Nicht wirklich... Aber das hast du ja schnell.

AbsoluterBeginner

gut gut, dann mach ich mal die klasse hehe
bis dennsen - danke fuer die schnelle antwort!

AbsoluterBeginner

ok hier mein resultat:

lines.ih

#include "lines.h"

using namespace std;

lines.h

#ifndef _INCLUDED_LINES_
#define _INCLUDED_LINES_

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

typedef std::pair<int, std::string> Elements;

class Lines
{   
   vector<Elements > d_allLines;
   size_t d_elementIdx;
   std::string d_empty;

    public:
        enum Type
        {
            ORIGINAL,
            ASCENDING,
            DESCENDING,
            CASE_ASCENDING,
            CASE_DESCENDING,
        };

        Lines();
        ~Lines();
        size_t size() const;
        void set(size_t idx, std::string const &str);
        std::string const &at(size_t idx) const;
        void sort(Type t);

    private:
        void read();
        void unsort();
};

inline size_t Lines::size() const
{
    return d_allLines.size();
}

inline std::string const &Lines::at(unsigned idx) const
{
    return idx < d_allLines.size() ? d_allLines.at(idx) : d_empty;
}

#endif

lines1.cc (std konstruktor)

#include "lines.ih"

Lines::Lines()
//:
{
   d_elementIdx = 0;
   d_empty = "";
   read();
}

read.cc

#include "lines.ih"

void Lines::read()
{
    string line;
    while (getline(cin, line))
    {
       //make a pair out of the inserted line and
       //the generated index and insert it to the vector
       d_allLines.push_back (make_pair (d_elementIdx++, line));
    }
}

sort.cc

#include "lines.ih"

bool ascending(const Elements& left, const Elements& right)
{
   return (left.second < right.second);
}

bool descending(const Elements& left, const Elements& right)
{
   return -ascending(left, right);
}

//only two functions have to be implemented at the moment
int (*call[])(const Elements, const Elements) = 
{
    0,
    ascending,
    descending,
    0,
    0,
};

void Lines::sort(Type type) 
{
    if (type == ORIGINAL)
        unsort();
    else
    	sort (d_allLines.begin(), d_allLines.end(), call[type]);
}

unsort.cc

#include "lines.ih"

bool original(const Elements& left, const Elements& right)
{  //check the first element of the pair (the generated index)
   return (left.first < right.first);
}

void Lines::unsort() 
{	
    sort (d_allLines.begin(), d_allLines.end(), original);
}

set.cc

#include "lines.ih"

void Lines::set(size_t idx, std::string const &str)
{
	//check all elements from the beginning to the 
	//end if the element id equals the idx if found
	//change the stored string at this position
    for (size_t i = 0; i < d_allLines.size(); ++i)
    {
      if(d_allLines.at(i).first == idx)
      		d_allLines.at(i).second = str;
    }
}

versuchte gerade zu kompilieren, bekomme aber schon einen fehler bei der klasse an sich (lines.h).

[quote]...es ist verboten einen vector ohne typ zu deklarieren[code]

kA was das sein soll, gebe ja den typ vom typdef an - was mache ich falsch?

muss jetzt mal weg bin dann am abend zurueck...

bin auch fuer hinweise zu den diversen funktionen dankbar, was ist nicht gut implementiert usw.

danke!

Nexus

Inkludier mal <utility> für std::pair ...

Einige Dinge, die mir noch aufgefallen sind:

Das mit dem Header "lines.ih" und using namespace std; würde ich nicht so machen. Ich selber schreibe std:: meistens bei jedem Bezeichner davor. Aber wenn du darauf verzichten willst, kannst du den Namensraum auch in der Implementierungsdatei (bzw. den Dateien) bekannt machen.
Soviele Implementierungsdateien halte ich für unnötig. Es ist nicht selten der Fall, dass eine Datei ein wenig länger wird. Aber dann brauchst du auch keinen "Zwischenheader". Und wenn jeder Header mehrere Implementierungsdateien erhält, hat man sehr schnell sehr viele Dateien, die man nicht mehr genau zuordnen kann.
Das Funktionszeiger-Array hat bei dir die Signatur int (const Elements, const Elements) . Sollte diese nicht bool (const Elements&, const Elements&) sein?
Wieso behandelst du unsort() als Spezialfall? Du könntest die Funktion doch auch als Zeiger in call speichern.
Sei vielleicht ein wenig konsistenter mit den Grössentypen. Manchmal verwendest du int , manchmal unsigned int und zum Teil size_t .

AbsoluterBeginner

Inkludier mal <utility> für std::pair ...
hat nichts gebracht
wundert mich auch, denn wie ich das ganze in nem anderenprogram (ohne klasse) getestet habe hat es funktioniert...

Das mit dem Header "lines.ih" und using namespace std; würde ich nicht so machen. Ich selber schreibe std:: meistens bei jedem Bezeichner davor. Aber wenn du darauf verzichten willst, kannst du den Namensraum auch in der Implementierungsdatei (bzw. den Dateien) bekannt machen.

unser prof macht das so, habs einfach uebernommen

Soviele Implementierungsdateien halte ich für unnötig. Es ist nicht selten der Fall, dass eine Datei ein wenig länger wird. Aber dann brauchst du auch keinen "Zwischenheader". Und wenn jeder Header mehrere Implementierungsdateien erhält, hat man sehr schnell sehr viele Dateien, die man nicht mehr genau zuordnen kann.

verstehe nicht ganze was du meinst sorry

Das Funktionszeiger-Array hat bei dir die Signatur int (const Elements, const Elements) . Sollte diese nicht bool (const Elements&, const Elements&) sein?

mein fehler, waere ich dann vermutlich beim weiteren kompliieren drauf gekommen (wollte zuerst ein mal die klasse fertig bekommen)

Wieso behandelst du unsort() als Spezialfall? Du könntest die Funktion doch auch als Zeiger in call speichern.

stimmt mache ich

Sei vielleicht ein wenig konsistenter mit den Grössentypen. Manchmal verwendest du int , manchmal unsigned int und zum Teil size_t .[/list]

jop mach ich auch sorry habs nur schnell mal geschrieben...

wenn mir jemand mit meinem vector problem helfen koennnte waere es super, schaffe es nicht die klasse zu kompilieren

danke euch!!

AbsoluterBeginner

hier die fehlermeldungen:

lines.h:13: error: ISO C++ forbids declaration of vector' with no type lines.h:13: error: expected;' before '<' token
lines.h: In member function size_t Lines::size() const': lines.h:40: error:d_allLines' undeclared (first use this function)
lines.h:40: error: (Each undeclared identifier is reported only once for each function it appears in.)
lines.h: In member function const std::string& Lines::at(unsigned int) const': lines.h:45: error:d_allLines' undeclared (first use this function)

weiß nicht warum, hab zum spaß mal den typ auf int geandert, also:

vector<int> d_allLines;

statt

vector<Elements > d_allLines;

gleicher fehler - was mache ich falsch?

Nexus

AbsoluterBeginner schrieb:

unser prof macht das so, habs einfach uebernommen

Nicht gut. Als Programmierer solltest du selber denken.

AbsoluterBeginner schrieb:

verstehe nicht ganze was du meinst sorry

Du hast fünf (!) Implementierungsdateien (.cc-Dateien), die einem einzigen Header zugeordnet sind.

AbsoluterBeginner schrieb:

wenn mir jemand mit meinem vector problem helfen koennnte waere es super, schaffe es nicht die klasse zu kompilieren

vector liegt natürlich im Namensraum std ...

AbsoluterBeginner

ja, hatte schon bei meiner letzten frage jemand der mir gesagt hat ich soll es nicht so machen (5 .cc datein) aber mein prof will es so also muss ich es so machen

danke fuer den std:: tipp, echt zu dumm - was solls

jetzt hab ich mich schon gefreut das alles passt, doch in der letzten datei die ich kompiliere fehler

geht um die sort.cc hier noch ein mal:

#include "lines.ih"

bool ascending(const Elements& left, const Elements& right)
{
return left.second < right.second;
}

bool descending(const Elements& left, const Elements& right)
{
return -ascending(left, right);
}

bool original(const Elements& left, const Elements& right)
{ //check the first element of the pair (the generated index)
return left.first < right.first;
}

//only three functions have to be implemented at the moment
bool (*call[])(const Elements&, const Elements&) =
{
original,
ascending,
descending,
0,
0,
};

void Lines::sort(Type type)
{
sort (d_allLines.begin(), d_allLines.end(), call[type]);
}

folgende fehlermeldung:

20:37 thomas:~/c++/set3/17/lines g++ -Wall -c sort.cc
sort.cc: In member function void Lines::sort(Lines::Type)': sort.cc:31: error: no matching function for call toLines::sort(__gnu_cxx::__normal_iterator<Elements*, std::vector<Elements, std::allocator<Elements> > >, __gnu_cxx::__normal_iterator<Elements*, std::vector<Elements, std::allocator<Elements> > >, bool (*&)(const Elements&, const Elements&))'
sort.cc:30: note: candidates are: void Lines::sort(Lines::Type)

leider werde ich nicht schlau daraus
bin mir nicht sicher ob ich dass mit pointern zu funktionen richtig verstanden habe. ich behandle dieses codestueck:

bool (*call[])(const Elements&, const Elements&) =
{
original,
ascending,
descending,
0,
0,
};

hier definiere ich doch ein array mit pointern zu funktionene. das array heiss call. der rueckgabe typ der funktionen ist bool und die funktionene erwarten als argumente zwei elemente (vom typ pair<size_t, string>)
mit call[0] rufe ich original aus, call[1] = asc, call[2] = desc.
rest noch nicht implementiert.
falls nicht richtig bitte korigieren

danke!!!

AbsoluterBeginner

hab es geschafft, das problem war dass beide funktionen sort geheissen haben...

alles laess ich kompilieren - sehr gut
nur testen laesst es sich noch nicht wie gewuncht, hier mein code:

#include "lines.ih"

int main()
{
   Lines line;

   cout << "Number o flines read: " << line.size() << endl;

   for(size_t i = 0; i < line.size(); ++i)
   		cout << line.at(i) << endl;

   //  line.sortLines(ASCENDING);  HIER MEIN PROBLEM
   cout << "Absteigend:\n";
   for(size_t i = 0; i < line.size(); ++i)
   		cout << line.at(i) << endl;

   cout << "\nENDE" << endl;
   return 0;
}

nochmal die klasse selbst:

#ifndef _INCLUDED_LINES_
#define _INCLUDED_LINES_

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

typedef std::pair<size_t, std::string> Elements;

class Lines
{
   std::vector<Elements > d_allLines;
   size_t d_elementIdx;
   std::string d_empty;

    public:
        enum Type
        {
            ORIGINAL,
            ASCENDING,
            DESCENDING,
            CASE_ASCENDING,
            CASE_DESCENDING,
        };

        Lines();
        ~Lines();
        size_t size() const;
        void set(size_t idx, std::string const &str);
        std::string const &at(size_t idx) const;
        void sortLines(Type type);

    private:
        void read();
};

inline size_t Lines::size() const
{
    return d_allLines.size();
}

inline std::string const &Lines::at(size_t idx) const
{
    return idx < d_allLines.size() ? d_allLines.at(idx).second : d_empty;
}

#endif

wie uebergebe ich die art der sortierung, habe in der klasse eine public enum, nur schaff es nicht diese zu verwenden

kann mir da jemand helfen?

danke...

jencas

line.sortLines(Lines::ASCENDING);  // HIER WAR DEIN PROBLEM

AbsoluterBeginner

hmm was macht das :: genau??
leuchtet mir nicht ganz ein, dachte irgendwie dass das Typ (name vom enum) vorkommen muesste...

und ein problem habe ich mit dem verkehrt sortieren:
habe die funktionen folgendermassen implementiert:

bool ascending(const Elements& left, const Elements& right)
{  //sort the lines ascending
   return left.second < right.second;
}

bool descending(const Elements& left, const Elements& right)
{  //sort the lines descending (inverted result from ascending)
   return -ascending(left, right);

}

hat nicht funktioniert, also habe ich es geaendert:

bool ascending(const Elements& left, const Elements& right)
{  //sort the lines ascending
   return left.second < right.second;
}

bool descending(const Elements& left, const Elements& right)
{  //sort the lines descending 
   return left.second > right.second;
}

so funktioniert es, ich verstehe aber nicht warum nicht auch die vorherige methode funktioniert...

Nexus

AbsoluterBeginner schrieb:

so funktioniert es, ich verstehe aber nicht warum nicht auch die vorherige methode funktioniert...

Wie sieht der logische Negations-Operator aus? Nein, - ist es nicht...

AbsoluterBeginner

hehe stimmt, bool sollte man schon mit ! negieren
danke!!
nur noch die frage bezgl. der enum offen

Dravere

AbsoluterBeginner schrieb:

hmm was macht das :: genau??
leuchtet mir nicht ganz ein, dachte irgendwie dass das Typ (name vom enum) vorkommen muesste...

Man kann damit auf verschiedene Scopes zugreifen. Lines::ASCENDING sagt dem Kompiler, dass er ASCENDING im Scope der Klasse Lines suchen soll, sonst weiss dieser nicht, was ASCENDING ist.

Grüssli

AbsoluterBeginner

aha also so wie namespace std zum beispiel?

und da der typ in der klasse public ist kann ich daruaf zugreifen ohne ein element davon zu erzeugen?!
das hat mich ein bisschen verwundert, denn normal mache ich ja von einer enum ein objekt (weiß nicht ob man hier objekt oder variable oder wwi sagt :D) welchem ich dann die verfuegbaren werte geben kann.

bp:

enum FARBE
{
  ROT,
  GELB,
  GRUEN
};

FARBE bla;

bla = ROT;