Suchfunktion in einer Klasse mit mehreren Instanzen

cyborg_beta

Das ~~wird~~ ist jetzt nur noch albern @Belli

Quiche Lorraine

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

Bevor der TO Real-World-Problems lösen kann, muss er zunächst die Grundlagen verstehen, und die versteht er durch 1a vorgegebenen Code nicht, nach meiner Meinung.

Und das ist deiner Meinung nach ein Freibrief Anfängern Code hinzurotzen?

hustbaer

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

@hustbaer Jaja, das hätte ich jetzt auch einfach behauptet ... Ist ja auch der einfachere Weg, als das eigene Verhalten mal zu überdenken.

Schauen wir mal, wie's weiter geht. Andere negativ zu bewerten, scheint ja gerade hip zu sein.

Ja, es ist der einfachere Weg, da hast du völlig Recht. Du irrst dich nur darin wer hier gerade den Fehler macht diesen zu beschreiten.

Und mach dir nicht die Mühe zu Antworten. Nach dem ich diesen Beitrag abschicke wandert auch dieser Account von dir auf meine Blocklist. Weil ich besseres zu tun habe als mit trotzigen Kindern zu streiten.

cyborg_beta

Nein, aber ein Freibrief dafür, sich an die Anforderungen zu halten.

Schade, dass @hustbaer auch dem Lager der Realitätsverweigerer angehört.

Quiche Lorraine

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

Nein, aber ein Freibrief dafür, sich an die Anforderungen zu halten.

><((((*>

Quiche Lorraine

@cyborg_beta

So irgentwie habe ich das Gefühl dass du den Code absichtlich schlecht gemacht hast. NIcht damit @Lumberjack etwas lernt, sondern damit du wieder provozieren kannst und so eine DIskussion startet.

Du sprichst von Realitätsverweigerung? Ja das sehe ich. DIch interresiert dein Speicherloch nicht, deinen völlig veralteten Code, die Verwendung von intrinischen Listen, deine Fehler im Code, dein schlechtes Design,...

cyborg_beta

@Quiche-Lorraine sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

DIch interresiert dein Speicherloch nicht,

Darum geht es ja, die Liste wird lediglich einmal zum Testen in der main "angelegt". Danach ist das Programm fertig. Ich sehe da kein Speicherloch.

Provozieren möchte ich gewiss nicht, es war halt nicht wider besseres Wissen.

Und hustbaer schmollt, nicht ich.

Tyrdal

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

@Quiche-Lorraine sagte in Suchfunktion in einer Klasse mit mehreren Instanzen:

DIch interresiert dein Speicherloch nicht,

Darum geht es ja, die Liste wird lediglich einmal zum Testen in der main "angelegt". Danach ist das Programm fertig. Ich sehe da kein Speicherloch.

Und das soll einem Anfänger helfen?

Quiche Lorraine

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

Darum geht es ja, die Liste wird lediglich einmal zum Testen in der main "angelegt". Danach ist das Programm fertig. Ich sehe da kein Speicherloch.

Und damit verstößt du gegen ein Grundprizip der Softwareentwicklung, der Wiederverwendbarkeit.

Denn gerade Anfänger gehen da gerne hin, kopieren den Code und wundern sich warum das System auf einmal instabil wird oder abstürzt (Murphys Gesetz).

cyborg_beta

QnD, aber wäre denn jetzt immer noch ein Speicherloch gegeben?:

#include <iostream>
#include <string>
#include <stdexcept>
#include <map>
using namespace std;

class DataElement {
  public:
  int topspeed = -1;
  int horsepower = -1;
  double weight = -1;
  
  DataElement(int topspeed, int horsepower, double weight): topspeed(topspeed), horsepower(horsepower), weight(weight) {};
  void print() {
    std::cout << topspeed << " , " << horsepower << " , " << weight << std::endl;
  }
};

class LinkElement {
  public:
  DataElement * current = nullptr;
  LinkElement * next = nullptr;
};

class MyList {
  private:
  LinkElement * first = nullptr;
  
  public:
  void insert(DataElement * de) {
    if (first == nullptr) {
      first = new LinkElement();
      first -> current = de;
      first -> next = nullptr;
    } else {
      LinkElement * temp = first;
      while (temp -> next != nullptr) {
        temp = temp -> next;
      }
      LinkElement * newLinkElement = new LinkElement();
      newLinkElement -> current = de;
      newLinkElement -> next = nullptr;
      temp -> next = newLinkElement;
    }
  }
  void filterByAttributeHorsepower(MyList * filterList, int minIncl, int maxIncl) {
    LinkElement * temp = first;
    while (temp != nullptr) {
      if (temp -> current -> horsepower >= minIncl &&
        temp -> current -> horsepower <= maxIncl) {
        filterList -> insert(temp -> current);
      }
      temp = temp -> next;
    }
  }
  void printAll() {
    int counter = 0;
    LinkElement * temp = first;
    while (temp != nullptr) {
      counter++;
      temp -> current -> print();
      temp = temp -> next;
    }
    std::cout << counter << std::endl;
  }
};

int main(int argc, char const * argv[]) {
  MyList ml1;
  MyList ml2;
  ml1.printAll();
  ml2.printAll();

  ml1.insert(new DataElement(200, 100, 1500));
  ml1.insert(new DataElement(299, 350, 1900));
  ml1.insert(new DataElement(325, 500, 1800));
  ml1.insert(new DataElement(312, 390, 1555));
  ml1.printAll();
  ml2.printAll();

  ml1.filterByAttributeHorsepower(&ml2, 350, 699);
  ml1.printAll();
  ml2.printAll();

  return 0;
}

Wenn ja, wie kann ich das ändern?

DocShoe

Der gleiche Mist in grün. Nimm std::vector.

Quiche Lorraine

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

QnD, aber wäre denn jetzt immer noch ein Speicherloch gegeben?:

Bist du wirklich auf diesem Kenntnisstand?

Du allokierst manuell Speicher, doch wer gibt diesen wieder frei? Ich sehe kein delete, kein std::unique_ptr, kein std::shared_ptr, kein std::vector.

Quiche Lorraine

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

Wenn ja, wie kann ich das ändern?

Nimm std::vector

Das Problem is nämlich folgendes. So ein std::list implementiert man nicht so einfach nach. Ressourcenverwaltung, Pointer, Exceptions Safety,... machen die Sache nicht einfach.

Wenn du mal in die Sache hineinschnuppern möchtest, dann würde ich dir den folgenden Link empfehlen.

https://codereview.stackexchange.com/questions/275619/stdlist-implementation-learning-exercise

cyborg_beta

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

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

Belli

@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!

Tyrdal

Dieser Beitrag wurde gelöscht!

*john 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)

cyborg_beta

@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 ...

Belli

@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.

*john 0

@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.