Wo leake ich hier memory? Dynamic array

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

(Wobei ich immer noch nicht verstehe warum man die Groesse nicht einfach 1,5mal so gross macht oder so, damit man diese nicht jedes mal anpassen muss)

Ja, das wäre eine gängige Optimierung für eine dynamisch wachsende Datenstruktur um die Reallokationen so selten wie möglich machen zu müssen weil teuer (langsam). Aber damit sollten wir uns hier eher nicht belasten.

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

if (!isPermutation(perm, dataCount))
{
return 0;
}

Gut. Weiter im Text.

In isPermutation():

        if ((perm[i] >= count) | (perm[i] < 0))

Erstens sollte das ein logisches or sein: ||. Zweitens stimmt die Bedingung nicht.
0 inklusive: perm[i] < 0 || count < perm[i]
0 exklusive: perm[i] < 1 || count <= perm[i]

Wenn Du Code postest dann schreib' bitte in eine Zeile vor Deinen Code ```cpp und in eine Zeile nach Deinem Code ```. Alternativ markiere Deinen Code und klicke auf das </> in der Symbolleiste über dem Bearbeitungsfeld. Du kannst Deine Beiträge auch im Nachhinein noch bearbeiten. Den Menüpunkt bearbeiten findest Du in dem Drei-Punkte-Menü rechts unter Deinen Beiträgen.

Als nächstes count und dataCount (warum heißen die unterschiedlich obwohl sie das selbe bezeichnen?) in std::size_t ändern. Die Schleifenvariable i jeweils auch. Der Typ std::size_t ist garantiert groß genug um die Größe jedes Objekts zu fassen. int fehlt diese Garantie.

marcel91200

@Swordfish Wieso stimmt meine Bedingung nicht? perm[i] darf nur Werte von 0 bis count-1 enthalten. Also return false wenn perm[i] >= count oder perm[i] < 0 ist.

Warum die Parameter der Funktion unterschliedlich heissen, kann ich dir leider auch nicht sagen. Die waren vorgegeben.

Das mit size_t hab ich aber geaendert, merk ich mir in Zukunft

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

@Swordfish Wieso stimmt meine Bedingung nicht? perm[i] darf nur Werte von 0 bis count-1 enthalten. Also return false wenn perm[i] >= count oder perm[i] < 0 ist.

Sorry, mein Fehler.

Swordfish

Ich habe jetzt

#include <memory>

bool isPermutation(int *perm, int count)
{
    auto cmp = std::make_unique<bool[]>(count);

    for (int i = 0; i < count; ++i)
        if (perm[i] < 0 || perm[i] >= count)
            return false;
        else cmp[perm[i]] = true;

    for (int i = 0; i < count; ++i)
        if (!cmp[i])
            return false;

    return true;
}

bool isSorted(double *data, int dataCount, int *perm)
{
    if (!isPermutation(perm, dataCount))
        return false;

    for (int i = 0; i < dataCount - 1; ++i)
        if (data[perm[i]] > data[perm[i + 1]])
            return false;

    return true;
}

einverstanden? (die Parametertypen zähneknirschend so gelassen wie sie waren)

marcel91200

@Swordfish Sollte ich nicht eben noch die Schleifenvariable int i in std::size_t i aendern ^^
Aber ja sieht gut aus, cmp werd ich auch in bool aendern, reicht ja fuer den Zweck.

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

@Swordfish Sollte ich nicht eben noch die Schleifenvariable int i in std::size_t i aendern ^^

Richtig^tm wäre std::size_t für die Parameter count und countData sowie die Schleifenvariablen. Aber wenn vorgegeben ...

Einlesen der doubles:

#include <cstdlib>  // std::realloc(), std::free()
#include <memory>   // std::make_unique<>()
#include <iostream> // std::cin, std::cout

bool isPermutation(int *perm, int count)
{
    auto cmp = std::make_unique<bool[]>(count);

    for (int i = 0; i < count; ++i)
        if (perm[i] < 0 || perm[i] >= count)
            return false;
        else cmp[perm[i]] = true;

    for (int i = 0; i < count; ++i)
        if (!cmp[i])
            return false;

    return true;
}

bool isSorted(double *data, int dataCount, int *perm)
{
    if (!isPermutation(perm, dataCount))
        return false;

    for (int i = 0; i < dataCount - 1; ++i)
        if (data[perm[i]] > data[perm[i + 1]])
            return false;

    return true;
}

int main()
{
    double *data = nullptr;
    int data_size = 0;  // nein, eigentlich std::size_t
    double input;

    while (std::cin >> input) {
        double *tmp = static_cast<double*>(std::realloc(data, (data_size + 1) * sizeof(*data)));
        if (!tmp) {
            std::cerr << "Not enough memory :(\n\n";
            std::free(data);
            return EXIT_FAILURE;
        }
        data = tmp;
        data[data_size] = input;
        ++data_size;
    }

    for (int i = 0; i < data_size; ++i)
        std::cout << i + 1 << ": " << data[i] << '\n';

    std::free(data);
}

bist noch dabei? Fragen?

Swordfish

Wenn Du den Index vor jeder einzulesenden Zahl ausgeben willst könnte man

    while (std::cout << data_size + 1 << ": ", std::cin >> input) {

marcel91200

@Swordfish
Bei der Zeile:

   double *tmp = static_cast<double*>(std::realloc(data, (data_size + 1) * sizeof(*data)));

Muesste man nicht erst den Speicher mit malloc alloziieren?
//Edit: Nein muss man nicht, dass macht realloc automatisch wenns nen null pointer ist

So wie du es gerade machst, hab ich es ja urspruenglich auch versucht, aber kam da ziemlich durcheinander weil ich die einzelnen Teile alle in Funktionen auslagern wollte. Ist das so besser oder sollte ich allgemein fuer sowas lieber einzelne Methoden schreiben?

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

Muesste man nicht erst den Speicher mit malloc alloziieren?

Wenn der erste Parameter von std::realloc() ein nullptr ist verhält sich std::realloc() genauso wie std::malloc().

So wie du es gerade machst, hab ich es ja urspruenglich auch versucht, aber kam da ziemlich durcheinander weil ich die einzelnen Teile alle in Funktionen auslagern wollte. Ist das so besser oder sollte ich allgemein fuer sowas lieber einzelne Methoden schreiben?

Ehrlich?
"Schönes" C++ oder vernünftiges Softwaredesign lernst Du in diesem Kurs sowieso nicht. Mach die Aufgaben, versuch Dir nicht zu viel Blödsinn (wie int für Speichergrößen, manuelle Speicherverwaltung, ...) anzugewöhnen und lerne aus den Fehlern deines Lehrers.

Weiter im Text? Als nächstes die Standardeingabe wieder benutzbar machen und die Indices einlesen:

#include <limits>   // std::numeric_limits<>
#include <cstdlib>  // std::realloc(), std::free(), EXIT_FAILURE
#include <memory>   // std::make_unique<>()
#include <iostream> // std::cin, std::cout, std::cerr

bool isPermutation(int *perm, int count)
{
    auto cmp = std::make_unique<bool[]>(count);

    for (int i = 0; i < count; ++i)
        if (perm[i] < 0 || perm[i] >= count)
            return false;
        else cmp[perm[i]] = true;

    for (int i = 0; i < count; ++i)
        if (!cmp[i])
            return false;

    return true;
}

bool isSorted(double *data, int dataCount, int *perm)
{
    if (!isPermutation(perm, dataCount))
        return false;

    for (int i = 0; i < dataCount - 1; ++i)
        if (data[perm[i]] > data[perm[i + 1]])
            return false;

    return true;
}

int main()
{
    double *data = nullptr;
    int data_size = 0;  // nein, eigentlich std::size_t
    double input;

    std::cout << "Your values:\n";
    while (std::cout << data_size + 1 << ": ", std::cin >> input) {
        double *tmp = static_cast<double*>(std::realloc(data, (data_size + 1) * sizeof(*data)));
        if (!tmp) {
            std::cerr << "Not enough memory :(\n\n";
            std::free(data);
            return EXIT_FAILURE;
        }
        data = tmp;
        data[data_size] = input;
        ++data_size;
    }

    if (!data_size) {
        std::cerr << "No input :(\n\n";
        return EXIT_FAILURE;
    }

    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::cout << "\nYour indices:\n";
    auto indices = std::make_unique<int[]>(data_size);
    for (int i = 0; i < data_size; ++i) {
        std::cout << i + 1 << ": ";
        if (!(std::cin >> indices[i])) {
            std::cerr << "Input error :(\n\n";
            std::free(data);
            return EXIT_FAILURE;
        }
    }

    std::free(data);
}

Swordfish

Wichtig: Frag bitte. Frag bitte bei jeder Zeile die unklar ist oder Dir auch nur komisch erscheint nach!!

marcel91200

@Swordfish Was bedeutet denn:

if (!data_size)

Also dann hat man keinen Input eingegeben, aber man initialisiert doch data_size mit nem Wert, was hat das "!" da zu suchen?

Swordfish

@marcel91200 Wenn kein input dann hat data_size den Wert 0 mit dem es initialisiert wurde. !0 gibt true. Kurz für data_size == 0.

marcel91200

@Swordfish Achso, wusste nicht dass das geht ^^
Wenn man es aber jetzt "richtig" machen muesste, wuerde man doch gar nicht mit free und so ausserhalb von nem Destruktor arbeiten oder? Damit man sich nicht selbst staendig um die Speicheralloziierung kuemmern muss

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

Wenn man es aber jetzt "richtig" machen muesste, wuerde man doch gar nicht mit free und so ausserhalb von nem Destruktor arbeiten oder? Damit man sich nicht selbst staendig um die Speicheralloziierung kuemmern muss

Nein. Man würde std::vector<> oder std::deque<> nehmen. (Nein, man würde so einen Container nicht selbst schreiben.)

@Swordfish sagte in Wo leake ich hier memory? Dynamic array:

//edit: Diskussion über eine halbwegs no-bullshit Vectorimplementierung in dem Thread: https://www.c-plusplus.net/forum/topic/351034/run-time-check-failure-2

Deswegen nicht.

Auch die C-Reliquien sind in C++ mit äußerster Vorsicht zu genießen weil malloc() und co für alles was nicht POD ist nicht funktionieren.

marcel91200

Gibt es keine Faelle in denen es sinnvoll waere sowas selbst zu implementieren? Was ist denn sonst der Sinn von dem Ganzen, wenn man es nie benutzen soll? Also natuerlich spart man sich ne Menge Arbeit und Probleme wenn man es nie benutzt, aber trotzdem eigenartig

Swordfish

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:

Gibt es keine Faelle in denen es sinnvoll waere sowas selbst zu implementieren? Was ist denn sonst der Sinn von dem Ganzen, wenn man es nie benutzen soll?

Sinnvoll. Ja, schon irgendwie. Man sollte mal erlebt haben was Speicherverwaltung bedeutet. Sowas relativ am Anfang eines C++-Kurses zu machen halte ich für Bullshit.
Container selbst implementieren? Ja klar. Wenn man ganz spezielle Anforderungen hat. Aber auch dann würde man eher nur einen allocator schreiben. Oder man braucht sowas in die Richtung: https://patents.google.com/patent/US8375062B2/en

Swordfish

Hast Du den Code schon um den trivialen Rest ergänzt und kommt er durch die Validierung eures tollen Servers?

marcel91200

@Swordfish Das werd ich morgen mal ausprobieren, danke dir nochmal fuer die Hilfe und die ganzen Ansaetze die ich noch lernen muss ^^

Swordfish

Kein Problem. Der Thread war ein Trauerspiel zum mitansehen. Willst Du denn wirklich C++ lernen?