Wo leake ich hier memory? Dynamic array

Swordfish

@marcel91200 wo ist isSorted()?
Ach so, könntest Du liebenswürdigerweise endlich mal die Aufgabenstellung posten??

std::cin.ignore();

Du weißt nicht was das tut, gell?

marcel91200

@Swordfish
Zur Aufgabenstellung habe ich doch schon etwas geschrieben:
"Die Aufgabe wurde mit uns nur in der Uebung durchgesprochen und dazu gab es dann eben noch die Dateien
(+ne Header-Datei, wo nochmal die Permutationsfunktion und die isSorted beschrieben werden)
Deswegen kann ich schlecht eine Aufgabenstellung schicken."

isSorted und isPermutation hab ich weiter oben schon gepostet, daran hat sich aber nichts geaendert. (Ausser ein fehler der in isSorted war)
Aber hier nochmal:

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

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

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

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

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

//Edit
Zu cin.ignore():
Das stand ein wenig verwirrend bei uns. Habs jetzt aber glaube verstanden. Ich will ja den fehlerhaften Input, nach dem Einlesen des User Inputs, ignorieren und cin.ignore() ueberspringt nur den naechsten char im Buffer. Stattdessen muss ich aber den kompletten Input im Stream ignorieren, damit ich keine Probleme bei getIndizes bekomme.
Also std::cin.ignore(std::numeric_limits<streamsize>::max(), '\n'); damit alles im Buffer uebersprungen wird.

Swordfish

@marcel91200 Dann gibs bitte aus Deinem Gedächtnis wieder.

Swordfish

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

if (!isPermutation(perm, sizeof(perm)/sizeof(int)))

DASDA!! Das ist vorgegeben!?!??? // edit: oder ist das von Dir? Wie gesagt. Formuliere endlich die konkrete Aufgabe. Was hier in diesem Thread betrieben wird ist sonst nur brainf*ck.

marcel91200

@Swordfish
Was genau moechtest du denn wissen?
Es ging darum dass man nacheinander beliebig viele double Werte in ein dynamisches Array einliest, welches zur Laufzeit dann jedes mal die Groesse aendert. (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) Dies macht man solange, bis eine Eingabe folgt, welche keine Zahl ist.
Nun liest man genauso viele Indizes in ein anderes Array ein. Diese Indizes stellen eine Permutation der Daten dar. Wenn ich also nun isSorted mit dem dynamischen Array und den Indizes aufrufe, wird 1 zuerueckgegeben, falls eine Umsortierung der Daten des dynamischen Arrays mit der angegebenen Permutation eine aufsteigend sortierte Folge ergibt. Dabei soll aber das bestehende Array nicht veraendert oder kopiert werden.
IsPermutation ueberprueft noch ob es sich bei den Indizes um eine korrekte Permutation handelt. Also ob alle Werte von 0-size-1 (size vom dynamischen Array/vom Indize array) genau einmal vorkommen.
Und wir duerfen natuerlich keine Datenstrukturen nehmen, welche die Aufgaben trivialisieren wuerden. (Also kein vektor, usw)

Swordfish

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

DASDA!! Das ist vorgegeben!?!??? // edit: oder ist das von Dir?

?

Swordfish

Was genau moechtest du denn wissen?

Das was Du darunter geschrieben hast. Endlich. Nach gefühlten 10 Tagen.

marcel91200

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

@marcel91200 sagte in Wo leake ich hier memory? Dynamic array:
if (!isPermutation(perm, sizeof(perm)/sizeof(int)))
DASDA!! Das ist vorgegeben!?!??? // edit: oder ist das von Dir? Wie gesagt. Formuliere endlich die konkrete Aufgabe. Was hier in diesem Thread betrieben wird ist sonst nur brainf*ck.

Da hab ich ne Testdatei kopiert, so ist das richtig:

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

Der rest muesste aber stimmen

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?