3. Suchfunktion in einer Klasse mit mehreren Instanzen

Suchfunktion in einer Klasse mit mehreren Instanzen

  • B

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Vielen Dank euch! Ich werde mir das zu Gemüte führen ...

    Und ja, ich bin noch so "doof", in Sachen C++. 😕

    Guck ma an, war doch gar nicht so schwer ...
    Und nein! Das ist keine Schande!

    0
  • T

    Dieser Beitrag wurde gelöscht!
    0
  • *

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Fangen wir mal simpel an, compilieren wir Dein Programm.

    g++ -std=c++20 -Wpedantic -Wall -Wextra -g fragender_doubly_linked_list.cc -o fragender_doubly_linked_list
fragender_doubly_linked_list.cc: In function ‘int main(int, const char**)’:
fragender_doubly_linked_list.cc:68:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
   68 | int main(int argc, char const * argv[]) {
      |          ~~~~^~~~
fragender_doubly_linked_list.cc:68:33: warning: unused parameter ‘argv’ [-Wunused-parameter]
   68 | int main(int argc, char const * argv[]) {
      |                    ~~~~~~~~~~~~~^~~~~~

    Erste Unsauberkeit fällt auf, da main nicht sinnvoll definiert ist.

    valgrind --leak-check=full ./fragender_doubly_linked_list 
==121870== Memcheck, a memory error detector
==121870== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==121870== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==121870== Command: ./fragender_doubly_linked_list
==121870== 
0
0
200 , 100 , 1500
299 , 350 , 1900
325 , 500 , 1800
312 , 390 , 1555
4
0
200 , 100 , 1500
299 , 350 , 1900
325 , 500 , 1800
312 , 390 , 1555
4
299 , 350 , 1900
325 , 500 , 1800
312 , 390 , 1555
3
==121870== 
==121870== HEAP SUMMARY:
==121870==     in use at exit: 176 bytes in 11 blocks
==121870==   total heap usage: 13 allocs, 2 frees, 74,928 bytes allocated
==121870== 
==121870== 48 (16 direct, 32 indirect) bytes in 1 blocks are definitely lost in loss record 9 of 10
==121870==    at 0x4849013: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==121870==    by 0x109552: MyList::insert(DataElement*) (fragender_doubly_linked_list.cc:32)
==121870==    by 0x109666: MyList::filterByAttributeHorsepower(MyList*, int, int) (fragender_doubly_linked_list.cc:51)
==121870==    by 0x10938D: main (fragender_doubly_linked_list.cc:81)
==121870== 
==121870== 128 (16 direct, 112 indirect) bytes in 1 blocks are definitely lost in loss record 10 of 10
==121870==    at 0x4849013: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==121870==    by 0x109552: MyList::insert(DataElement*) (fragender_doubly_linked_list.cc:32)
==121870==    by 0x1092AD: main (fragender_doubly_linked_list.cc:74)
==121870== 
==121870== LEAK SUMMARY:
==121870==    definitely lost: 32 bytes in 2 blocks
==121870==    indirectly lost: 144 bytes in 9 blocks
==121870==      possibly lost: 0 bytes in 0 blocks
==121870==    still reachable: 0 bytes in 0 blocks
==121870==         suppressed: 0 bytes in 0 blocks
==121870== 
==121870== For lists of detected and suppressed errors, rerun with: -s
==121870== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

    So gehen wir mal etwas über den Code

    #include <iostream>
#include <string>
#include <stdexcept>
#include <map>
#include <cstdlib>
#include <memory>

using namespace std;

class Data {
public:
	int topspeed, horsepower;
	double weight;

	Data () : topspeed(-1), horsepower(-1), weight(-1) {}
	Data(int topspeed, int horsepower, double weight): topspeed(topspeed), horsepower(horsepower), weight(weight) {};
};

std::ostream& operator<< (std::ostream& o, const Data& d) {
	o << d.topspeed << " , " << d.horsepower << " , " << d.weight << "\n";

	return o;
}

struct Node {
	Node *previous_, *next_;
	std::unique_ptr<Data> data_;

	explicit Node(Data *d) : previous_(nullptr), next_(nullptr), data_(d) {}
	Node(Data *d, Node *previous, Node *next) : previous_(previous), next_(next), data_(d) {}
};

struct MyList {
	Node *head_, *tail_;

	~MyList() {
		this->reset();
	}

	MyList () : head_(nullptr), tail_(nullptr) {}

	void reset() {
		if (nullptr != head_) {
			Node *current = head_;

			do {
				Node *next = current->next_;
				current->next_= nullptr;
				current->previous_ = nullptr;
				delete current;
				current = next;
			} while (nullptr != current);

		}		
	}

	void insertHead(Data *d) {
		if (nullptr == head_) {
			head_ = new Node(d);
			tail_ = head_;
		} else {
			Node *old = head_;
			head_ = new Node(d, nullptr, old);
			old->previous_ = head_;
		}
	}
};

void filterByAttributeHorsepower(const MyList& ml, int minIncl, int maxIncl, MyList& result) {
	result.reset();
	Node* current = ml.head_;

	while (nullptr != current) {
		if ((current->data_->horsepower >= minIncl) && (current->data_->horsepower <= maxIncl)) {
			result.insertHead(new Data(*(current->data_)));
		}

		current = current->next_;
	}
	
}

std::ostream& operator<< (std::ostream& o, const MyList& ml) {
	size_t counter = 0;
	Node *t = ml.head_;

	while (nullptr != t) {
		counter++;
		o << *(t->data_);
		t = t->next_;
	}

	o << counter << "\n";

	return o;
}

int main() {
	MyList ml1;
	MyList ml2;
	MyList result;

	std::cout << ml1 << ml2;

	ml1.insertHead(new Data(200, 100, 1500));
	ml1.insertHead(new Data(299, 350, 1900));
	ml1.insertHead(new Data(325, 500, 1800));
	ml1.insertHead(new Data(312, 390, 1555));

	std::cout << ml1 << ml2;

	filterByAttributeHorsepower(ml2, 350, 699, result);

	std::cout << ml1 << ml2;

	return EXIT_SUCCESS;
}

    Dieser Code ist noch weit davon entfernt die Rule-of-Five einzuhalten, oder gar die STL Eigenschaften für eine Container Klasse zu erfüllen, aber er leaked nun nicht mehr beim Code in main. Der Rest ist todo für den Leser.

    g++ -std=c++20 -Wpedantic -Wall -Wextra -g fragender_doubly_linked_list_mod.cc -o fragender_doubly_linked_list_mod

    valgrind ./fragender_doubly_linked_list_mod 
==124934== Memcheck, a memory error detector
==124934== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==124934== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==124934== Command: ./fragender_doubly_linked_list_mod
==124934== 
0
0
312 , 390 , 1555
325 , 500 , 1800
299 , 350 , 1900
200 , 100 , 1500
4
0
312 , 390 , 1555
325 , 500 , 1800
299 , 350 , 1900
200 , 100 , 1500
4
0
==124934== 
==124934== HEAP SUMMARY:
==124934==     in use at exit: 0 bytes in 0 blocks
==124934==   total heap usage: 10 allocs, 10 frees, 74,912 bytes allocated
==124934== 
==124934== All heap blocks were freed -- no leaks are possible
==124934== 
==124934== For lists of detected and suppressed errors, rerun with: -s
==124934== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
    0
  • C
    Gesperrt

    @john-0 Du hast irgendwo einen Fehler drin, die Semantik und die Ausgaben stimmen nun nicht mehr überein (es werden zu viele Elemente gefunden, die Filterfunktion stimmt nicht). Das hängt vermutlich mit Node zusammen.

    Zudem würde ich:

    if (nullptr != head_) {

    so nicht schreiben, sondern umgekehrt - das stört sonst den Lesefluss. Du willst eine Variable auf Validität prüfen, nicht ein Schlüsselwort. In fast allen westlichen Ländern wird von links nach rechts gelesen, nicht von rechts nach links.

    Außerdem ... kommt man echt nicht ohne so eine Pointer-Akrobatik aus? Was ist, wenn std::unique_ptr seitens der Aufgabenstellung ausgeschlossen ist?

    Es soll ja zum Beispiel eingebettete Systeme geben, deren Compiler std::-Funktionen nicht unterstützen/ implementiert haben. Für so einen Anwendungsfall bräuchte man wohl eine eigene, einfach verkettete Liste ...

    0
    B
    *
     2 Antworten
  • B

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Zudem würde ich:

    if (nullptr != head_) {

    so nicht schreiben, sondern umgekehrt - das stört sonst den Lesefluss.

    Diese Reihenfolge gewöhnt man sich ganz bewusst an.
    Häufig hat man ja eine Prüfung auf Gleichheit:
    if (nullptr == head_) {
    Hier verhindert diese Reihenfolge den Flüchtigkeitsfehler:
    if (nullptr = head_) {
    der sich unter Umständen hartnäckig verstecken kann.

    1
    C
     1 Antwort
  • *

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    so nicht schreiben, sondern umgekehrt - das stört sonst den Lesefluss.

    Die Konstante kommt auf die linke Seite, weil dann Fehler auffallen, falls man aus Versehen eine Zuweisung schreibt.

    Außerdem ... kommt man echt nicht ohne so eine Pointer-Akrobatik aus?

    Ja, und der Sinn und Zweck des Codes war zu zeigen, wie man die Zeiger bei einer doppelt verlinkten Liste korrekt umsetzt. Der Code ist nur ein Basisgerüst, da noch sehr viel fehlt. Das wichtigste zuerst, die Rule-of-Five ist bisher nicht umgesetzt, d.h. nur mit dem Code aus dem Beispiel läuft das ohne Leaks. Sobald man die Listen kopiert kracht es, weil CopyConstructor, MoveConstructor, CopyAssigment und MoveAssignment nicht vorhanden sind, und die Default Versionen leaken. Dann fehlt natürlich das Interface für Allocatoren, es fehlt das Interface für Iteratoren, die Liste sollte als Template formuliert sein, …

    Was ist, wenn std::unique_ptr seitens der Aufgabenstellung ausgeschlossen ist?

    Dann muss man für die Node Klasse entweder ein Template nutzen, oder halt auch dort korrekt mit den Zeigern auf die Daten Klassen hantieren. Auch da gilt wieder Rule-of-Five einhalten.

    Es soll ja zum Beispiel eingebettete Systeme geben, deren Compiler std::-Funktionen nicht unterstützen/ implementiert haben. Für so einen Anwendungsfall bräuchte man wohl eine eigene, einfach verkettete Liste ...

    Man nimmt mittlerweile meist Vektoren, weil moderne CPUs Code bevorzugen, der auf Cache Hits optimiert ist. Früher wurde auf die absolute Zahl der Schreib-/Lesevorgänge optimiert, da damals überall im Speicher der Zugriff gleich schnell war. Mit Caches änderte sich das. Daher sind Listen nicht mehr so beliebt, und Vektoren sind meist schneller.

    0
  • C
    Gesperrt

    @Belli sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Häufig hat man ja eine Prüfung auf Gleichheit:
    if (nullptr == head_) {
    Hier verhindert diese Reihenfolge den Flüchtigkeitsfehler:
    if (nullptr = head_) {
    der sich unter Umständen hartnäckig verstecken kann.

    Interessant, wusste ich (noch) nicht.

    @john-0 Aber irgendwo muss ein logischer Fehler enthalten sein ... oder du hast bei der Ausgabe geschummelt ... wenn man nach 350 <= horsepower <= 699 filtert, sollte es nur drei Elemente geben.

    result.insertHead(new Data(*(current->data_)));

    wieso wird hier mit * dereferenziert? Ich versuche mir gerade das durchzulesen: https://stackoverflow.com/questions/4955198/what-does-dereferencing-a-pointer-mean-in-c-c

    0
  • C
    Gesperrt

    🤦♂

    ach ... dämlich. Deine Funktion filterByAttributeHorsepower hat vier Parameter, braucht aber nur drei. Das Ergebnis wird in den vierten Parameter getan. Bei der Ausgabe wird dieser aber gar nicht berücksichtigt. Das war der Fehler.

    Vermutlich ist der Rest richtig.^^

    0
  • C
    Gesperrt

    Bitte mit Folgendem einmal Valgrind füttern:

    #include <iostream>
#include <string>
#include <stdexcept>
#include <map>
#include <cstdlib>
#include <memory>

using namespace std;

class Data {
public:
	int topspeed, horsepower;
	double weight;

	Data () : topspeed(-1), horsepower(-1), weight(-1) {}
	Data(int topspeed, int horsepower, double weight): topspeed(topspeed), horsepower(horsepower), weight(weight) {};
	
	friend ostream& operator<< (ostream& o, const Data& d) {
	    o << d.topspeed << " , " << d.horsepower << " , " << d.weight << "\n";
	    return o;
    }
};

class Node {
public:
    Data * data;
    Node * next;
    
    Node() : data(nullptr), next(nullptr) {}
    Node(Data * d) : data(d), next(nullptr) {}
    Node(Data * d, Node * n) : data(d), next(n) {}
};

class MyList {
private:
    Node * first;
public:
    MyList() : first(nullptr) {}
    ~MyList() {
        Node * tmp = first;
        while (nullptr != tmp) {
            Node * tmp2 = tmp->next;
            delete tmp;
            tmp = tmp2;
        }
    }
    void insert(Data * d) {
        if (nullptr == first) {
            first = new Node(d);
        } else {
            Node * tmp = first;
            while (nullptr != tmp->next) {
                tmp = tmp->next;
            }
            tmp->next = new Node(d);
        }
    }
    void filterByWeight(MyList& second, double wMinIncl, double wMaxIncl) {
        Node * tmp = first;
        while (nullptr != tmp) {
            if (tmp->data->weight >= wMinIncl && tmp->data->weight <= wMaxIncl) {
                second.insert(tmp->data);
            }
            tmp = tmp->next;
        }
    }
    friend ostream& operator<< (ostream& o, const MyList& ml) {
	    size_t counter = 0;
	    Node * t = ml.first;
	    while (nullptr != t) {
		    counter++;
		    o << *(t->data);
		    t = t->next;
	    }
	    o << counter << "\n";
	    return o;
    }
};

int main() {
    MyList ml1, ml2;
    ml1.insert(new Data(1, 2, 3.4));
    ml1.insert(new Data(4, 5, 6.7));
    cout << ml1 << ml2 << "\n";
    
    ml1.filterByWeight(ml2, 3.3, 3.5);
    cout << ml1 << ml2;
    
    return 0;
}
    -1
    *
     1 Antwort
  • *

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Bitte mit Folgendem einmal Valgrind füttern:

    class Node {
public:
    Data * data;
    Node * next;
    
    Node() : data(nullptr), next(nullptr) {}
    Node(Data * d) : data(d), next(nullptr) {}
    Node(Data * d, Node * n) : data(d), next(n) {}
};

    Das Thema war Rule-of-Five. Da hier die Verantwortung fürs Löschen der Data Exemplare an die Klasse Node übergeben wird, wo bitte werden die Data Elemente gelöscht?

    0
  • C
    Gesperrt

    Hast du das gemacht, was ich gesagt habe? Sonst brauchen wir hier gar nicht weiterdiskutieren.

    @john-0 sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Das Thema war Rule-of-Five.

    Nein, war es nicht. Lies noch einmal die Anforderungen.

    -1
    W
    *
     3 Antworten
  • W

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Nein, war es nicht. Lies noch einmal die Anforderungen.

    Doch, das ist natürlich das Thema. Ein sehr wichtiges sogar, wenn man eigene Listen implementieren will. Es ist Basis dafür, dass der Code korrekt wird. Wenn du Basiswissen ignorierst, wirst du nicht weit kommen. Dass Code korrekt sein soll und keine Speicherlücken haben soll, ist IMMER Teil der Anforderung, auch wenn nicht explizit aufgeschrieben.

    0
  • *

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Hast du das gemacht, was ich gesagt habe? Sonst brauchen wir hier gar nicht weiterdiskutieren.

    Dreimal darfst Du raten, weshalb ich auf das Thema Rule-of-Five verwiesen habe. Die Klasse Node hat ein Speicherloch.

    Nachtrag:

    g++ -std=c++20 -Wpedantic -Wall -Wextra -g fragender_singly_linked_list_orig.cc -o fragender_singly_linked_list_orig

    ergibt

    valgrind --leak-check=full ./fragender_singly_linked_list_orig
==3947279== Memcheck, a memory error detector
==3947279== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3947279== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==3947279== Command: ./fragender_singly_linked_list_orig
==3947279== 
1 , 2 , 3.4
4 , 5 , 6.7
2
0

1 , 2 , 3.4
4 , 5 , 6.7
2
1 , 2 , 3.4
1
==3947279== 
==3947279== HEAP SUMMARY:
==3947279==     in use at exit: 32 bytes in 2 blocks
==3947279==   total heap usage: 7 allocs, 5 frees, 74,832 bytes allocated
==3947279== 
==3947279== 16 bytes in 1 blocks are definitely lost in loss record 1 of 2
==3947279==    at 0x4849013: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3947279==    by 0x1092A6: main (fragender_singly_linked_list_orig.cc:82)
==3947279== 
==3947279== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2
==3947279==    at 0x4849013: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3947279==    by 0x1092E0: main (fragender_singly_linked_list_orig.cc:83)
==3947279== 
==3947279== LEAK SUMMARY:
==3947279==    definitely lost: 32 bytes in 2 blocks
==3947279==    indirectly lost: 0 bytes in 0 blocks
==3947279==      possibly lost: 0 bytes in 0 blocks
==3947279==    still reachable: 0 bytes in 0 blocks
==3947279==         suppressed: 0 bytes in 0 blocks
==3947279== 
==3947279== For lists of detected and suppressed errors, rerun with: -s
==3947279== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
    0

  • @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Hast du das gemacht, was ich gesagt habe? Sonst brauchen wir hier gar nicht weiterdiskutieren.

    @john-0 sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Das Thema war Rule-of-Five.

    Nein, war es nicht. Lies noch einmal die Anforderungen.

    Und ich hatte tatsächlich die Hoffnung, dass du Kritik mal ernst nimmst und nicht wieder austeilst, weil du/deine Programmierversuche wieder kritisiert worden sind.

    0
  • C
    Gesperrt

    Ich glaube, dann fehlt in Node und Data jeweils ein Destruktor. (Mehr nich)

    ... zumindest, um Valgrind zufriedenzustellen.

    0
    *
     3 Antworten

  • @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    Ich glaube, dann fehlt in Node und Data jeweils ein Destruktor. (Mehr nich)

    ... zumindest, um Valgrind zufriedenzustellen.

    Und die Kopierkonstruktoren/Zuweisungsoperatoren. Du darfst Speicher auf dem Heap nur ein Mal freigeben, das musst du iwie sicherstellen. Und dafür sind Kopierkonstruktoren/Zuweisungsoperatoren da.

    1

  • @cyborg_beta
    Warum stürzt wohl der folgende Code ab?

    MyList GetList()
{
    MyList ml1;

    ml1.insert(new Data(1, 2, 3.4));
    ml1.insert(new Data(4, 5, 6.7));
    return ml1;
}

int main() {
    MyList ml1 = GetList();
    MyList ml2;

    cout << ml1 << ml2 << "\n";
    ml1.filterByWeight(ml2, 3.3, 3.5);
    cout << ml1 << ml2;
    return 0;
}
    0
  • *

    @cyborg_beta sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

    ... zumindest, um Valgrind zufriedenzustellen.

    Vollkommen falscher Ansatz. Es geht darum, dass das Programm nicht leakt. valgrind ist nur ein Mittel zum Zweck, dies festzustellen. Wenn Du Windows nutzt, kannst Du Dir das Intel oneAPI HPC Toolkit kostenlos herunterladen und den Inspector nutzen, um die Speicherlöcher zu finden. Alternativ kannst Du Dir mit Hilfe von VirtualBox eine Linux VM installieren und darin valgrind nutzen. Man sollte bevor man Code publiziert selbst nachschauen, dass der Code auch funktioniert, d.h. unter anderem nicht leakt. Besonders schlecht ist es, wenn man Anfänger mit schlechtem Code „versorgt“.

    0
    C
     1 Antwort
  • C
    Gesperrt

    @john-0 Das beantwortet meine Frage aber nicht, ob Valgrind jetzt ruhig ist oder nicht. 😉

    Ansonsten wurde doch gesagt, dass die Rule-of-Five für ihn vermutlich zu kompliziert ist, und nicht der Fragestellung angemessen.

    Also, es wäre nett, auf meine Frage einfach mit ja/nein zu antworten.

    0
    *
     3 Antworten

  • @cyborg_beta

    Das trägt doch iwie alles nicht zur Problemlösung bei. In der Aufgabenstellung des TE war doch nie gefordert, eine eigene Liste zu implentieren, das ist doch auf deinem Mist gewachsen.
    Ich sehe das so:

    1. Dem TE wurde std::vector vorgeschlagen, das ist der rundrum-sorglos Container, bei dem man sich um nichts weiter mehr kümmern muss. TE kann sich sofort um die eigentliche Aufgabe kümmern, nämlich den Container nach Elementen mit bestimmten Kriterien zu durchsuchen.

    2. Du hast dem TE die Implementierung einer eigenen Liste empfohlen, bei der nach knapp 3 Wochen noch keine fehlerfreie Variante existiert. Wenn TE diesen Weg gehen möchte, muss man ihm alle Konsequenzen dieser Entscheidung zeigen, und auch wie man die dabei entstehenden Probleme löst. Dazu gehört, dass die Liste alle sinnvollen Operationen korrekt implementiert oder sie verbietet, um Fehlbenutzung zu vermeiden. Eine spezielle Liste, die vor Sonderfällen strotzt und zur Fehlbenutzung einlädt, ist für mich keine Lösung. Wenn TE nicht gezeigt wird, in welchen Situationen die Liste Fehler verursacht, nimmt er sie vllt. in sein Repertoire auf und postet in 2 Monaten einen Thread, in dem er sich über seltsames Programmverhalten und Abstürze wundert, weil er diese Liste benutzt.

    Auf der einen Seite schlägst du TE vor, eine eigene Liste zu implementieren und im nächsten Satz sagst du, dass du ihn dafür zu unerfahren hältst und die Rule of 3/5 für ihn zu fortgeschritten ist. Also was denn jetzt?

    TL;DR: Entweder einen Container der STL, oder eine vollständige, funktionierende Liste, die sich immer korrekt verhält und keine Memoryleaks hinterlässt.

    2
Anmelden zum Antworten