Substrings innerhalb eines Strings sortieren

Bibigon

Hallo.
Bin ganz neu in C++.
Wie löse ich am effektivsten folgende Aufgabe:

Mehrere Strings müssen nach Substrings sortiert werden.

Stringsbeispiele:

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

Es gibt mehrere Gruppen von Substrings:

Gruppe:
"[8A]"
"[UKE]"
Gruppe.
"[Dings da]"
"[DingsBums]"
Gruppe.
"[GF]"
"[MOD]"
"[MOD3]"
"[MOD6]"
Gruppe.
"[Weiss]"
"[Rot]"
"[Orange-Blau]"

Die Substrings müssen innerhalb des Stringes nach Gruppenrang sortiert werden. Der String darf nur einen Substring aus einer Gruppe beinhalten.

Beispiele:
"[8A][Dings da][Orange-Blau]" -> "[8A][Dings da][Orange-Blau]"
"[MOD][Weiss][UKE]" -> "[UKE][MOD][Weiss]"
"[GF][MOD3][Dings da]" -> Fehler - [GF] und [MOD3] sind beide aus der Gruppe 3!
"[MOD][Black][UKE]" -> Fehler - [Black] ist nicht in den Substrings vorhanden!

Löse ich die Aufgabe am besten mit einem Container oder C-Array? Falls Container, welcher Art: vector, map, multimap usw.?
Und das wichtigste: wie am effektivsten (Algorithmus)?

Im Voraus besten Dank!

*john 0

Die beste Lösung ist es einen Parser zu schreiben. Wenn es direkt in C++ sein soll, kann man boost Spirit nutzen. Ansonsten flex/bison, antlr, …

SeppJ

Ist es ausgeschlossen, dass es zu Doppeldeutigkeiten oder fehlende Einträgen bei der Zerlegung kommen kann? Ich nehme im folgenden an, dass dies kein Problem darstellt oder es eine definierte Lösung gibt, aber du solltest mal überlegen, ob das vorkommen kann und wie dies ggf. zu lösen ist.

Nimm auf gar keinen Fall jemals C-Strings oder Arrays für irgendwas, wenn std::string & Co. erlaubt sind!

Von hier aus ist ad-hoc im Kopf programmiert, wie ich das ungefähr machen würde. Ich will dir ja nicht die Aufgabe komplett lösen

Du willst im Hintergrund wahrscheinlich eine map<int, vector<string>> haben, wo du deine vorgegebenen Wortgruppen drin gespeichert hast.

Dann beginnst du deinen jeweiligen String zu zerlegen, und merkst dir Paare der Substrings und der Gruppe aus der sie sind. Also vermutlich als vector<pair<string, int>>. Aus deinem Beispiel "[MOD][Weiss][UKE]" wird also die Paarfolge {("[MOD]", 3), ("[Weiss]", 4), ("[UKE]", 1)}. Man kann beim Zerlegen auch Mitzählen (auf allerlei Weise), ob und wie oft jede Gruppe vorkommt. Sobald man eine Gruppe zum 2. Mal sieht, kann man mit einem Fehler abbrechen.

Das kannst du dann mit sort nach dem zweiten Teil des Paars sortieren, du bekommst also die Folge {("[UKE]", 1), ("[MOD]", 3), ("[Weiss]", 4)}

Dann soll daraus ja wieder ein String werden. Dazu hängt man einfach die jeweils erste Hälfte der Paare wieder zu einem String zusammen. Spätestens dabei muss man aber prüfen, ob es Doppelungen gibt, etwa indem man guckt, ob das nächste Paar die gleiche Nummer wie der Vorgänger hat.

Das sind jetzt relative viele unnötige Stringoperationen, weil man bei den Paaren viele neue Strings erzeugt und durch die Gegend verschiebt. Wenn man dies optimieren möchte, kann man statt der Strings den Index der Subgruppe speichern (Also zum Beispiel statt {("[MOD]", 3), ("[Weiss]", 4), ("[UKE]", 1)} merkt man sich {(1, 3), (0, 4), (2, 1)}. Das ist dann eine Abstraktionsschicht mehr, dafür ist es effizienter. Musst du wissen, ob du dir das zutraust. Die naive Methode ist einfacher zu verstehen und einfacher bei eventueller Fehlersuche.

Oder es gibt auch die vollständig andere Methode, dass man sich gar nix zwischenspeichert. Man weiß schließlich, in welcher Reihenfolge die Subgruppen später stehen müssen. Also könnte man einfach gucken, ob ein String aus Subgruppe 1 vorkommt, wenn ja, dann kommt er direkt ganz nach vorne. Falls Nein, dann tut man halt nix. Und falls mehrere vorkommen, dann direkt Fehler. Und dann fährt man immer so fort mit Subgruppe 2 und so weiter. Das ist denkbar simpel und direkt. Aber das fliegt einem um die Ohren, wenn es Doppeldeutigkeiten oder unbekannte Bestandteile gibt. Daher müssen diese ausgeschlossen sein, sonst ist diese Methode nix.

Meine erste Methode ist robust, aber eventuell überkompliziert. Die simple Methode ist zum Angeben, wie gut man darin ist, die einfachste Abstraktion zu finden. Aber wenn dann eine leichte Änderung der Anforderung kommt, steht man dumm da. Im echten Leben würde ich die robuste Methode wählen, die simple Methode ist eher für den Informatikunterricht (Aber ich nehme an, das hier ist aus dem Informatikunterricht?).

Quiche Lorraine

@Bibigon sagte in Substrings innerhalb eines Strings sortieren:

Löse ich die Aufgabe am besten mit einem Container oder C-Array? Falls Container, welcher Art: vector, map, multimap usw.?
Und das wichtigste: wie am effektivsten (Algorithmus)?

Lass die Finger weg von C-Arrays, nimm die STL (std::vector, std::map, ...)! Das nimmt dir jede Menge Arbeit ab!

Anfangs würde ich die Effektivität auch mal nach hinten schieben. Schaue erst einmal dass du das Programm zum laufen bringst. Später kannst du immer noch einen größeren Test machen und ggf. optmieren.

BTW:
Könntest du auch mal ein verständlicheres Beispiel geben, welche dein Problem klarer beschreibt? Evt. so: "Gruppe: Songtitel, Gruppe: Erscheinungsdatum,..." ?

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.

Affe0

Dieser Beitrag wurde gelöscht!