Substrings innerhalb eines Strings sortieren

[Bibigon]

@SeppJ
Danke dir! Genau an dieser Art von Hilfe habe ich gedacht.
Die Aufgabe ist nicht aus der Informatikunterricht.
Brauche jetzt nur ein Paar Stunden freier Zeit zum Code schreiben.
Auf jeden Fall, vielen Dank voresrt!

[Bibigon]

@Quiche-Lorraine

Danke für die Tipps!
So werde ich auch weiter vorgehen.

Zum Beispiel:
Man hat z. B. als Schmuck-CADler im Laufe des Jahres einige CAD-Modelle im Archiv.

Schmuckart: Ring, Armband, Collier, Ohrstecker, Ohrhänger, Anhänger usw
Legierung: 750 Gelbgold, 750 Weissgold, 585... , Plating, Silber usw
Steinart: Diamant, Smaragd, Rubin, ...
Steinanzahl: 1, 2, 3, ..
Perlenart: FWP, SCP, Akoya, ...
Perlenanzahl: 1, 2, ...
Ringweite: 48, 49, ...
Länge: 40, 42, 45...
Zusätzliches: Handgravur, Lasergravur, Guilloche, ...
.
.
.
Ich überlege wie ich die Modelle am effektivsten archiviere und die im Archiv dann am schnellsten finde.

[Quiche Lorraine]

@Bibigon sagte in Substrings innerhalb eines Strings sortieren:

Ich überlege wie ich die Modelle am effektivsten archiviere und die im Archiv dann am schnellsten finde.

Ah ok!

Mal eine weitere Frage: Wären dann auch Abfragen der Form "Zeige mir mal bitte jedes Schmuckstück aus Silber" wünschenswert?

[Bibigon]

@Quiche-Lorraine
Die Abfragen sind vorerst zweitrangig. Mir geht es in der erste Linie gerade um Archivstardardisierung.

[Quiche Lorraine]

@Bibigon
Naja, ich frage mich halt bloß ob du eine Datenbank ala SQL benötigst.

Ist das ein Hobby-Projekt für dich oder musst du wirklich Daten archivieren?

[suboptimal]

Dieser Beitrag wurde gelöscht!

[Sündenbock]

Dieser Beitrag wurde gelöscht!

[Bibigon]

@SeppJ

Habe deinem Tipp gefolgt:

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};

int main() {
    std::ifstream ifsDatei("Zu_Sortieren.txt");
    std::string strZeile, strTeilstring;
    bool Gefunden=true; // für Fehler "unbekannter Substring"
    bool GruppenDuplikat; // für "Gruppenduplikat"-Fehler

    if (ifsDatei.is_open()) { // Datei öffnen
        while (std::getline(ifsDatei, strZeile)) { // Datei zeilenweiser einlesen
            std::stringstream strstrmZeile(strZeile); // Stringstream zum Aufteilen
            std::map<int, std::string> mSortierteString; // Container für sortierten String
            GruppenDuplikat = false;
            std::cout << strZeile << "  ->  ";
            while(std::getline(strstrmZeile, strTeilstring, ']') && (Gefunden || !GruppenDuplikat)) { // Aufteilung in Substrings
                strTeilstring += ']';
                Gefunden = false;
                for (auto const& [keyPosition, vTeilstrings] : mTeilstrings) { // Suche nach dem Substring in der Liste
                    auto it = std::find(vTeilstrings.begin(), vTeilstrings.end(), strTeilstring); // Suche nach dem Substring in der Gruppe
                    if (it != vTeilstrings.end()) {
                        Gefunden = true;
                        if (!mSortierteString.count(keyPosition)) { // falls kein Substring aus der gleichen Gruppe bereits im Container
                            mSortierteString.insert({keyPosition, strTeilstring}); // füge dem Container zu
                        }
                        else {
                            GruppenDuplikat=true;
                            std::cout << "Fehler: Gruppenmitglied bereits vorhanden! " << strTeilstring << " & " << mSortierteString[keyPosition] << std::endl;
                            break;
                        }
                    }
                }
                if ( !Gefunden ) { // falls ein unbekannter Substring
                    std::cout << "Fehler: unbekannter Substring " << strTeilstring << "!";
                }
            }
            if (Gefunden && ! GruppenDuplikat ) // Ausgabe fehlerfreien sortierten String
                for (const auto& [schluessel, wert] : mSortierteString) {
                    std::cout << wert;
                }
            std::cout << std::endl;
        }
        ifsDatei.close(); // Datei schließen
    } else {
        std::cerr << "Datei konnte nicht geöffnet werden." << std::endl;
        return 1;
    }
    return 0;
}

Zu_Sortieren.txt

[8A][Dings da][Orange-Blau]
[MOD][Weiss][UKE]
[GF][MOD3][Dings da]
[MOD][Black][UKE]
[GF][MOD3][Dings da][GF][MOD3][Dings da]

Funktioniert noch nicht zufriedenstellend.
Was ich zum Verrecken nicht hinkriege, ist die Umschreibung der for-Schleife:

for (auto const& [keyPosition, vTeilstrings] : mTeilstrings) { // Suche nach dem Substring in der Liste

in eine while-Schleife, damit ich die Schleife nach dem ersten Fehler unterbrechen kann.

while(Iterator!=mTeilstring.end() && (Gefunden || !GruppenDuplikat)) {
...
}

Ich verstehe es einfach nicht (auch Googlen hiflt nicht ), wie kriege ich den keyPosition-Wert heraus.

Die etwas holprige Ausgabe sieht zur Zeit folgendermassen aus:

[8A][Dings da][Orange-Blau] -> [8A][Dings da][Orange-Blau]
[MOD][Weiss][UKE] -> [UKE][MOD][Weiss]
[GF][MOD3][Dings da] -> Fehler: Gruppenmitglied bereits vorhanden! [MOD3] & [GF]

[MOD][Black][UKE] -> Fehler: unbekannter Substring [Black] [UKE][MOD]
[GF][MOD3][Dings da][GF][MOD3][Dings da] -> Fehler: Gruppenmitglied bereits vorhanden! [MOD3] & [GF]
Fehler: Gruppenmitglied bereits vorhanden! [GF] & [GF]
Fehler: Gruppenmitglied bereits vorhanden! [MOD3] & [GF]
Fehler: Gruppenmitglied bereits vorhanden! [Dings da] & [Dings da]

Vielen Dank im Voraus!

[Quiche Lorraine]

@Bibigon
Schau mal Sepp wollte ein vector<pair<string, int>>. Was spricht also gegen mTeilstrings ala {[8A], 1}, {[UKE], 1}, {[Dings da], 2}... Dein Integer Wert entspricht hier ja einer Kategorien ID.

Dann liest du deine Eingabe (z.B. "[8A][Dings da][Orange-Blau]") ein und zerlegt diese in einzelne Tokens ("[8A]", "[Dings da]", "[Orange-Blau]")

Dann suchst du zu jedem Token einen Eintrag in mTeilstrings. Gebe eine Fehlemeldung aus, wenn du keinen Eintrag gefunden hast. Ansonsten füge das Ergebnis einer Result = vector<string, int> Variable hinzu.

Wenn du damit fertig bist, sortiere Result nach der Kategorien-ID (int Wert).

Danach überprüfst du das Ergebnis. Per Definition darf eine Kategorien-ID nicht doppelt vorkommen. Und durch die Sortierung ist es garantiert dass im Falle eines Falles diese aufeinanderfolgt.

Und danach gibst du das Ergebnis aus.

[SeppJ]

Genau. Du versuchst da einen Schritt abzukürzen, den ich bewusst nicht abgekürzt habe, da du versuchst direkt beim Lesen an die richtige Stelle des Ergebnisses zu schreiben, anstatt erst einmal zu sammeln. Was löblich ist — wahrscheinlich sogar machbar wenn man ein bisschen tüftelt —, aber macht es halt schwieriger. Ich würde mich erst einmal genau Schritt für Schritt an meinen Vorschlag halten. Da kann man auch gut jeden Teilschritt nacheinander programmieren und jeweils das Zwischenergebnis angucken, ob es noch passt. Derzeit hast du 7 Ebenen Einrückung. Verwirrend. Stattdessen lieber so programmieren, dass man 7 Mal 1-2 Ebenen Einrückung hat, auch wenn's ein paar Zeilen länger wird.

[SeppJ]

Ich brauche gerade mal eine entspannte Kaffeepause. Da kann ich auch mal ein bisschen Informatikunterricht spielen und das Schritt für Schritt entwickeln.

Fangen wir mit dem Grundgerüst an. Nur die Teilstringdefinition und die Eingabe (Auf ideone.com von stdin):

#include <iostream>
#include <vector>
#include <map>
#include <string>

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};

int main()
{
	for(std::string line; std::getline(std::cin, line);)
	{
		std::cout << line << '\n';
	}
}

https://ideone.com/8xFxh5

Jetzt wollen wir anhand der Teilstrings unsere Eingabezeilen in einen vector<pair<string, int>> zerlegen. Mir ist bewusst, dass die hier in diesem Beispiel naturgemäß immer schon in der richtigen Reihenfolge rauskommen, und ich an dieser Stelle auch gucken könnte, ob es Doppelungen gibt. Das geht aber nur so gut, weil ich alle Problematik bezüglich Doppelungen, Uneindeutigkeiten, oder fehlender Definitionen vernachlässige. Ich nehme an, dass das Zerlegen in Wahrheit komplizierter ausfallen könnte. Nach jeder Zerlegung gucken wir uns das Ergebnis an, ob es den Erwartungen entspricht!

#include <iostream>
#include <vector>
#include <map>
#include <string>

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};


auto parse_line(std::string line, 
	   		   const std::map<int, std::vector<std::string>> &substring_groups)
{
	std::vector<std::pair<std::string, int>> result;
	for (auto const& kv : substring_groups)
	{
		for (auto const &substring:  kv.second)
		{
			if (line.find(substring) != std::string::npos)
				result.push_back(std::make_pair(substring, kv.first));
		}
	}
	return result;
}

int main()
{
	for(std::string line; std::getline(std::cin, line);)
	{
		auto substring_pairs = parse_line(line, mTeilstrings);
		std::cout << "Zeile \"" << line << "\" wird zerlegt in '";
		for (auto pair: substring_pairs)
			std::cout << "{\"" << pair.first << "\", " << pair.second << "}, ";
		std::cout << '\n';
	}
}

Zeile "[8A][Dings da][Orange-Blau]" wird zerlegt in {("[8A]", 1), ("[Dings da]", 2), ("[Orange-Blau]", 4), }
Zeile "[MOD][Weiss][UKE]" wird zerlegt in {("[UKE]", 1), ("[MOD]", 3), ("[Weiss]", 4), }
Zeile "[GF][MOD3][Dings da]" wird zerlegt in {("[Dings da]", 2), ("[GF]", 3), ("[MOD3]", 3), }
Zeile "[MOD][Black][UKE]" wird zerlegt in {("[UKE]", 1), ("[MOD]", 3), }
Zeile "[GF][MOD3][Dings da][GF][MOD3][Dings da]" wird zerlegt in {("[Dings da]", 2), ("[GF]", 3), ("[MOD3]", 3), }

https://ideone.com/HsyN2N
Ideone kann nur C++14 so richtig, daher Entschuldigung für den altertümlichen Stil. Besonders mit C++17 und neuer gehen die ganzen Schleifen sehr viel schöner, wie du in deiner Lösung schon korrekt vormachst.

Hoppla, da haben wir ja auch gleich mehrere Fehler im Ergebnis!

Zeile "[MOD][Black][UKE]" wird zerlegt in {("[UKE]", 1), ("[MOD]", 3), }

Da fehlt [Black], weil es nicht in der Teilstringdefinition vorkommt. Das ignoriere ich jetzt wie gesagt erst einmal, da es in der Vorgabe nicht definiert ist, was passieren soll. Aber das hier:

Zeile "[GF][MOD3][Dings da][GF][MOD3][Dings da]" wird zerlegt in {("[Dings da]", 2), ("[GF]", 3), ("[MOD3]", 3), }

Da fehlen die Doppelungen von [MOD3] und [Dings da]. Da müssen wir beim Zerlegen gründlicher sein:

#include <iostream>
#include <vector>
#include <map>
#include <string>

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};


auto parse_line(std::string line, 
	   		   const std::map<int, std::vector<std::string>> &substring_groups)
{
	std::vector<std::pair<std::string, int>> result;
	for (auto const& kv : substring_groups)
	{
		for (auto const &substring:  kv.second)
		{
			std::string::size_type pos = 0;
			while ((pos = line.find(substring, pos)) != std::string::npos) 
			{
				result.push_back(std::make_pair(substring, kv.first));
				pos += substring.length();
			}
		}
	}
	return result;
}

int main()
{
	for(std::string line; std::getline(std::cin, line);)
	{
		auto substring_pairs = parse_line(line, mTeilstrings);
		std::cout << "Zeile \"" << line << "\" wird zerlegt in '";
		for (auto pair: substring_pairs)
			std::cout << "{\"" << pair.first << "\", " << pair.second << "}, ";
		std::cout << '\n';
	}
}

Zeile "[8A][Dings da][Orange-Blau]" wird zerlegt in '{"[8A]", 1}, {"[Dings da]", 2}, {"[Orange-Blau]", 4}, 
Zeile "[MOD][Weiss][UKE]" wird zerlegt in '{"[UKE]", 1}, {"[MOD]", 3}, {"[Weiss]", 4}, 
Zeile "[GF][MOD3][Dings da]" wird zerlegt in '{"[Dings da]", 2}, {"[GF]", 3}, {"[MOD3]", 3}, 
Zeile "[MOD][Black][UKE]" wird zerlegt in '{"[UKE]", 1}, {"[MOD]", 3}, 
Zeile "[GF][MOD3][Dings da][GF][MOD3][Dings da]" wird zerlegt in '{"[Dings da]", 2}, {"[Dings da]", 2}, {"[GF]", 3}, {"[GF]", 3}, {"[MOD3]", 3}, {"[MOD3]", 3}, 

Passt. https://ideone.com/jV4pWL
Man könnte an dieser Stelle natürlich trivial prüfen, ob es Doppelungen gibt. Wir müssen bloß Mitzählen beim Suchen der Teilstrings in jeder Gruppe. Aber wie gesagt, nehme ich an, dass das später komplizierter werden kann, also ignoriere ich das jetzt erst einmal und mache das erst später.

Nächster Schritt: Sortieren! Hier eigentlich nicht nötig, aber in komplizierteren Fällen schon. Ist sowieso ein Einzeiler.

Spaßeshalber kann ich die Reihenfolge ja umdrehen, so dass man sieht, dass auch etwas passiert.

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

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};


auto parse_line(std::string line, 
	   		   const std::map<int, std::vector<std::string>> &substring_groups)
{
	std::vector<std::pair<std::string, int>> result;
	for (auto const& kv : substring_groups)
	{
		for (auto const &substring:  kv.second)
		{
			std::string::size_type pos = 0;
			while ((pos = line.find(substring, pos)) != std::string::npos) 
			{
				result.push_back(std::make_pair(substring, kv.first));
				pos += substring.length();
			}
		}
	}
	return result;
}

int main()
{
	for(std::string line; std::getline(std::cin, line);)
	{
		auto substring_pairs = parse_line(line, mTeilstrings);
		std::sort(substring_pairs.begin(), substring_pairs.end(), 
		          [](auto left_pair, auto right_pair){return left_pair.second > right_pair.second;});
		std::cout << "Zeile \"" << line << "\" wird zerlegt in '";
		for (auto pair: substring_pairs)
			std::cout << "{\"" << pair.first << "\", " << pair.second << "}, ";
		std::cout << '\n';
	}
}

Zeile "[8A][Dings da][Orange-Blau]" wird zerlegt in '{"[Orange-Blau]", 4}, {"[Dings da]", 2}, {"[8A]", 1}, 
Zeile "[MOD][Weiss][UKE]" wird zerlegt in '{"[Weiss]", 4}, {"[MOD]", 3}, {"[UKE]", 1}, 
Zeile "[GF][MOD3][Dings da]" wird zerlegt in '{"[GF]", 3}, {"[MOD3]", 3}, {"[Dings da]", 2}, 
Zeile "[MOD][Black][UKE]" wird zerlegt in '{"[MOD]", 3}, {"[UKE]", 1}, 
Zeile "[GF][MOD3][Dings da][GF][MOD3][Dings da]" wird zerlegt in '{"[GF]", 3}, {"[GF]", 3}, {"[MOD3]", 3}, {"[MOD3]", 3}, {"[Dings da]", 2}, {"[Dings da]", 2}, 

Passt. https://ideone.com/qOMpob

Und jetzt setzen wir die Einzelteile wieder zusammen. Und spätestens jetzt müssen wir prüfen, ob es Doppelungen gibt, also vergleichen wir jeweils mit dem Vorgänger.

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

// Liste der bekannten Substrings
const std::map<int, std::vector<std::string>> mTeilstrings = {
    {1, {"[8A]", "[UKE]"}},
    {2, {"[Dings da]", "[DingsBums]"}},
    {3, {"[GF]", "[MOD]", "[MOD3]", "[MOD6]"}},
    {4, {"[Weiss]", "[Rot]", "[Orange-Blau]"}}
};


auto parse_line(std::string line, 
	   		   const std::map<int, std::vector<std::string>> &substring_groups)
{
	std::vector<std::pair<std::string, int>> result;
	for (auto const& kv : substring_groups)
	{
		for (auto const &substring:  kv.second)
		{
			std::string::size_type pos = 0;
			while ((pos = line.find(substring, pos)) != std::string::npos) 
			{
				result.push_back(std::make_pair(substring, kv.first));
				pos += substring.length();
			}
		}
	}
	return result;
}

std::string reconstitute_line(std::vector<std::pair<std::string, int>> const& substring_pairs)
{
	std::string result;
	int last_group;
	if (not substring_pairs.empty())
	{
		last_group = substring_pairs[0].second;
		result = substring_pairs[0].first;
	}
	for (std::size_t i = 1; i < substring_pairs.size(); ++i)
	{
		int current_group = substring_pairs[i].second;
		if (current_group == last_group)
			return "Zeile enthält illegale Doppelungen";
		result += substring_pairs[i].first;
	}
	return result;
}

int main()
{
	for(std::string line; std::getline(std::cin, line);)
	{
		auto substring_pairs = parse_line(line, mTeilstrings);
		std::sort(substring_pairs.begin(), substring_pairs.end(), 
		          [](auto left_pair, auto right_pair){return left_pair.second > right_pair.second;});
		std::string sorted_line = reconstitute_line(substring_pairs);
		std::cout << "Zeile \"" << line << "\" wird sortiert zu \"" << sorted_line << "\"\n";
	}
}

Zeile "[8A][Dings da][Orange-Blau]" wird sortiert zu "[Orange-Blau][Dings da][8A]"
Zeile "[MOD][Weiss][UKE]" wird sortiert zu "[Weiss][MOD][UKE]"
Zeile "[GF][MOD3][Dings da]" wird sortiert zu "Zeile enthält illegale Doppelungen"
Zeile "[MOD][Black][UKE]" wird sortiert zu "[MOD][UKE]"
Zeile "[GF][MOD3][Dings da][GF][MOD3][Dings da]" wird sortiert zu "Zeile enthält illegale Doppelungen"

Passt. https://ideone.com/M25huJ

Es ist eigentlich falsch, Fehler als Rückgabewert zurück zu geben, aber ich hatte jetzt keine Lust für das Beispiel auch noch eine ausgiebige Fehlerbehandlung zu programmieren. Zumal ich gar nicht weiß, was die Anforderung für den Fehlerfall ist.

Das sind noch reichlich Verbesserungen möglich. Wurden ja auch schon genannt, oder du bist selber drauf gekommen. Und auch so triviale Dinge, wie das Vermeiden von unnötigen Kopien, sind noch nicht getan. Aber so hast du erst einmal eine Basis, die funktioniert, und wo die Funktionalitäten aufgetrennt sind. Von da aus ist es leichter, diese Verbesserungen vorzunehmen, anstatt alles auf einmal in einer siebenfach verschachtelten Schleife zu machen.