Strings von Objekten vergleichen und ändern

thuering

Moin, ich wünsche ein frohes Fest gehabt zu haben!

Ich habe einen std::vector der Objekte einer Klasse enthält. Die Klasse hat auch den Member "std::string displayName". Ich möchte durch den vector iterieren und displayName abändern, wenn dieser mehrfach vorkommt.
Also z.B.

Player
Orc
Orc
Idiot
Orc
Zombie
Skeleton
Skeleton

zu

Player
Orc (1)
Orc (2)
Idiot
Orc (3)
Zombie
Skeleton (1)
Skeleton (2)

machen. Aus Ablauf-Gründen ist es nicht möglich, dies beim Instanziieren / Initialisieren der Objekte zu machen, sondern muss später erfolgen, also in einer eigenen Funktion.
Ich habe bereits einiges mit zwei Schleifen versucht, aber das passt bisher nicht. Da ist ja nicht nur die Nummerierung an sich, sondern auch verschiedene Nummerierungen für verschiedene displayName.

std::vector<Creature*> creatures;

std::vector<int> participants;

void Battle::checkParticipantsName()
{
	int nameCounter = 1;
	for (size_t i = 0; i < participants.size(); ++i)
	{
		for (size_t j = 0; j < participants.size(); ++j)
		{		
			if (game.world.creatures[participants[i]]->displayName == game.world.creatures[participants[j]]->displayName && game.world.creatures[participants[i]]->cID != game.world.creatures[participants[j]]->cID)
			{
				game.world.creatures[participants[i]]->displayName = game.world.creatures[participants[i]]->GetName() + " (" + std::to_string(nameCounter) + ")";
				nameCounter++;
			}
		}
	}
}

Habt ihr Ideen? Gerne auch moderne Lösungen mit C++23 / 26.

Erhard Henkes

@thuering sagte in Strings von Objekten vergleichen und ändern:
...

Habt ihr Ideen? Gerne auch moderne Lösungen mit C++23 / 26.

#include <string>
#include <string_view>
#include <unordered_map>
#include <vector>

void Battle::checkParticipantsName()
{
    // 1) Häufigkeiten pro Basisname zählen
    std::unordered_map<std::string, int> total;
    total.reserve(participants.size());

    for (int idx : participants)
    {
        auto* c = game.world.creatures[idx];
        const std::string base = c->GetName();     // stabiler "Rohname"
        ++total[base];
    }

    // 2) Laufende Nummern pro Basisname vergeben
    std::unordered_map<std::string, int> seen;
    seen.reserve(total.size());

    for (int idx : participants)
    {
        auto* c = game.world.creatures[idx];
        const std::string base = c->GetName();

        if (total[base] <= 1)
        {
            // einzigartig -> ohne Suffix
            c->displayName = base;
        }
        else
        {
            // Duplikat -> (1), (2), ...
            int n = ++seen[base];
            c->displayName = base + " (" + std::to_string(n) + ")";
        }
    }
}

Wichtig: O(n) statt O(n²)

Lennox

@Erhard-Henkes sagte in Strings von Objekten vergleichen und ändern:

++total[base];

Wieso diese Schreibweise und nicht total[base]++;?

Total von Basis um 1 erhöhen, liest sich für mich fluenter als die andere Variante.

thuering

@Erhard-Henkes
Richtig, richtig gut. Vielen Dank, guten Rutsch!

Erhard Henkes

@Lennox
https://www.tutorialspoint.com/pre-increment-and-post-increment-concept-in-c-cplusplus#:~:text=Pre-increment (%2B%2Bi) %3A,variable%2C the value is incremented.

Finnegan

@thuering sagte in Strings von Objekten vergleichen und ändern:

Habt ihr Ideen? Gerne auch moderne Lösungen mit C++23 / 26.

Als Fan von "Ranges" lass ich mir das nicht zweimal sagen

Hier eine m.E. relativ elegante range-basierte Lösung. Die Idee ist die Teilnehmer nach displayName zu sortieren und an den Elementen zu "splitten", wo sich die Namen unterscheiden. Das resultiert in "Sub-Ranges" mit gleichem Namen bei denen dann bei Bedarf die Namen angepasst werden können (z.B. wenn diese mehr als ein Element haben):

#include <string>
#include <ranges>
#include <vector>
#include <format>
#include <print>
#include <algorithm>

struct Creature
{
    std::string displayName;
};

std::vector<Creature*> creatures = {
    new Creature{ "Orc" },
    new Creature{ "Orc" },
    new Creature{ "Idiot" },
    new Creature{ "Orc" },
    new Creature{ "Zombie" },
    new Creature{ "Skeleton" },
    new Creature{ "Skeleton" }
};

std::vector<int> participants = { 2, 0, 1, 3, 6, 4, 5 };

auto main() -> int
{
    // Kopiert "participants" Array.
    auto sorted_participants = participants;

    // Sortiert "sorted_participants" Array aufsteigend nach Creature::displayName.
    std::ranges::sort(
        sorted_participants,
        [&](int a, int b){
            return creatures[a]->displayName < creatures[b]->displayName;
        }
    );

    // Erzeugt einen Range-View aus Creature&-Elementen, die den nach Namen sortierten Teilnehmern entsprechen.
    auto sorted_creatures_view = sorted_participants | std::views::transform(
        [&](int participant) -> Creature& { return *creatures[participant]; }
    );

    // Dieses for_each itertiert über Ranges von Creature-Ranges, die den selben "displayName" haben.
    std::ranges::for_each(
        // Erzeugt eine Range von Sub-Ranges, indem die Eingabe-Range dort getrennt wird, wo sich
        // benachbarte Elemente unterscheiden (i.e. wo sie unterschiedliche "displayName" haben).
        sorted_creatures_view | std::views::chunk_by(
            // Das ist unsere Bedingung um Sub-Ranges zu erzeugen. Wenn sich benachbarte Elemente
            // im "displayName" unterscheiden, fängt der "chunk_by" View dort eine neue Sub-Range an.
            [&](const auto& a, const auto& b) { return a.displayName == b.displayName; }
        ),
        [](const auto& equal_name_range)
        {
            // Alle Elemente in der Range equal_name_range haben den selben "displayName".

            // Wir wollen einen Zähler nur dann anhängen, wenn es mehr als ein Element mit dem Namen gibt.
            if (std::ranges::size(equal_name_range) <= 1)
                return;

            // In dem Fall zählen wir die Range mit "enumerate" auf, das gibt uns eine Range aus 2-Tupeln
            // der Form [index, Creature&], der Index "zählt" unsere Elemente mit dem gleichen Namen.
            for (auto [index, creature] : std::views::enumerate(equal_name_range))
            {
                // Wenn wir schon modernes C++ schreiben, können wir auch gleich std::format verwenden,
                // das macht es später einfacher, die Formatierung anzupassen, wenn sie uns nicht gefällt.
                std::format_to(std::back_inserter(creature.displayName), " ({})", index + 1);
            }
        }
    );

    // Erzeugt einen Range-View Creature&-Elementen, die den Teilnehmern entsprechen, so wie sie im 
    // "participants"-Array stehen (unsortiert).
    auto creatures_view = participants | std::views::transform(
        [&](int participant) -> Creature& { return *creatures[participant]; }
    );

    for (const auto& creature : creatures_view)
        std::println("{}", creature.displayName);
}

Live im Compiler Explorer: https://godbolt.org/z/467rKb7GE

Das erfordert natürlich ein Sortieren. Allerdings wird hier nur das participants Array sortiert und nicht das Creatures Array. Das ist nicht sonderlich teuer (wenn man mal von der etwas cache-unfreundlichen Indirektion absieht, um an den displayName zu kommen).

Alternativ kann man auch den Ansatz von @Erhard-Henkes mit Ranges formulieren:

#include <string>
#include <ranges>
#include <vector>
#include <format>
#include <print>
#include <algorithm>
#include <unordered_map>

struct Creature
{
    std::string displayName;
};

std::vector<Creature*> creatures = {
    new Creature{ "Orc" },
    new Creature{ "Orc" },
    new Creature{ "Idiot" },
    new Creature{ "Orc" },
    new Creature{ "Zombie" },
    new Creature{ "Skeleton" },
    new Creature{ "Skeleton" }
};

std::vector<int> participants = { 2, 0, 1, 3, 6, 4, 5 };

auto main() -> int
{
    auto creatures_view = participants | std::views::transform(
        [&](int participant) -> Creature& { return *creatures[participant]; }
    );

    std::unordered_map<std::string_view, int> total;
    std::ranges::for_each(
        creatures_view,
        [&](const auto& creature) { ++total[creature.displayName]; }
    );

    std::unordered_map<std::string_view, int> seen;
    std::ranges::for_each(
        creatures_view,
        [&](auto& creature)
        {
            if (total[creature.displayName] <= 1)
                return;
            std::format_to(std::back_inserter(creature.displayName), " ({})", ++seen[creature.displayName]);
        }
    );

    for (const auto& creature : creatures_view)
        std::println("{}", creature.displayName);
}

Live im Compiler Explorer: https://godbolt.org/z/W4To3sdbY

Das ist jetzt nicht großartig anders als die Variante von @Erhard-Henkes, nur dass es eben std::ranges::for_each statt klassisches Range-based-For verwendet. Was einem besser gefällt ist letztendlich Geschmackssache. Der Erzeugte Code dürfte ziemlich identisch sein.

Welches von beiden effizienter ist, hängt denke ich stark von der Anzahl der Elemente ab. std::unordered_map ist leider berüchtigt dafür, nicht besonders performant zu sein, da der Standard für diese "Hash Map" de facto Chaining vorschreibt (mehr Indirektionen) anstatt cache-freundlichere offene Adressierung. Von dem $\mathcal{O}(1)$ profitiert man daher vermutlich erst bei sehr vielen Spielern.

Ein Problem ist auch die spezielle Formatierung, die du haben möchtest (kein Suffix wenn es keine Duplikate gibt). Daher muss man die Duplikate auch erstmal in einem zusätzlichen Durchgang zählen, damit man hinterher weiß, wo man überhaupt ein Suffix anfügen muss und wo nicht.

Vermutlich ist die Performance aber auch relativ egal, da diese Namens-Anpassung wahrscheinlich nur einmal zu Spielbeginn gemacht wird. Nimm daher am besten die Lösung, die dir am besten gefällt und/oder die du am besten nachvollziehen kannst

Lennox

@Erhard-Henkes sagte in Strings von Objekten vergleichen und ändern:

@Lennox
https://www.tutorialspoint.com/pre-increment-and-post-increment-concept-in-c-cplusplus#:~:text=Pre-increment (%2B%2Bi) %3A,variable%2C the value is incremented.

Das beantwortet meine Frage aber nicht... ich weiß selber, was das ist...

Intelligenz ist, sich an immer ändernde Bedingungen anpassen zu können.

Aber ich sehe schon... um clean code geht es hier nicht... Macht's gut!

Finnegan

@Lennox sagte in Strings von Objekten vergleichen und ändern:

@Erhard-Henkes sagte in Strings von Objekten vergleichen und ändern:

@Lennox
https://www.tutorialspoint.com/pre-increment-and-post-increment-concept-in-c-cplusplus#:~:text=Pre-increment (%2B%2Bi) %3A,variable%2C the value is incremented.

Das beantwortet meine Frage aber nicht... ich weiß selber, was das ist...

Intelligenz ist, sich an immer ändernde Bedingungen anpassen zu können.

Aber ich sehe schon... um clean code geht es hier nicht... Macht's gut!

Bei ++total[base] ist es relativ egal, aber bei dem hier ist es essentiell:

int n = ++seen[base];
c->displayName = base + " (" + std::to_string(n) + ")";

... sonst hat man den falschen Zähler-Wert. Es ist ja offenbar ein Zähler gewünscht, der mit 1 beginnt. Insofern finde ich ++[total[base] hier etwas konsistenter, auch wenn es bei einer int&, die man von der unordered_map zurückbekommt von der Performance her letztendlich keinen Unterschied macht.

Und btw: Es schadet nicht "per Default" ++i zu schreiben. Es ist die selbe Tipparbeit und wenn i z.B. ein komplexerer Typ ist, kann es in einigen Fällen sogar effizienter sein, da keine temporäre Kopie erforderlich ist (intern in der Operator-Implementierung). Und wenn man mit Iteratoren arbeitet, dann kann es sogar sein, dass die gar keinen Post-Inkrement haben.

Lennox

Dieser Beitrag wurde gelöscht!

Lennox

@Finnegan
Wie gesagt, an dieser Stelle ist es wichtig, aber an den anderen nicht. Das ist schlicht seiner Copy&Past-Bequemlichkeit geschuldet. Siehe meine Aussage zur Intelligenz.

Finnegan

@Lennox sagte in Strings von Objekten vergleichen und ändern:

@Finnegan sagte in Strings von Objekten vergleichen und ändern:

aber bei dem hier ist es essentiell:

Nein, auch Du übersiehst etwas. Er hat das assignment doch extra in eine eigene Variable gesteckt.

Sei seen[base] = 0, dann ist Der Ausdruck ++seen[base] gleich 1 und seen[base]++ gleich 0. D.h. dass mit int n = seen[base]++; n == 0. Es ist also mindestens noch ein n + 1 erforderlich, da der erste Spieler ja die Nummer 1 bekommen soll. Das ++seen[base] vermeidet das.

Edit: Ja, gesehen dass du es dir schon selbst aufgefallen ist

Aber wie ich oben schrieb: ++i "per Default" zu verwenden ist nicht verkehrt. Es kann in manchen Fällen effizienter sein und ist immer mindestens genau so gut wie i++. Auch gibt es Iterator-Konzepte, die nur ++i kennen. Pre-increment ist daher meines Erachtens generell die "bessere" Lösung. Auch wenn es für einen int oder eine int& wie hier effektiv keinen Unterschied macht.

Lennox

@Erhard-Henkes sagte in Strings von Objekten vergleichen und ändern:

for (int idx : participants)
{
    auto* c = game.world.creatures[idx];
    const std::string base = c->GetName();     // stabiler "Rohname"
    ++total[base];
}

@Finnegan Ich erwarte hier, also in der letzten Anweisung der for-each-Schleife, keine esoterischen oder kryptischen Konstrukte.

Finnegan

@Lennox sagte in Strings von Objekten vergleichen und ändern:

@Erhard-Henkes sagte in Strings von Objekten vergleichen und ändern:
for (int idx : participants)
{
    auto* c = game.world.creatures[idx];
    const std::string base = c->GetName();     // stabiler "Rohname"
    ++total[base];
}
@Finnegan Ich erwarte hier, also in der letzten Anweisung der for-each-Schleife, keine esoterischen oder kryptischen Konstrukte.

Das ist Ansichtssache. Ich finde das absolut normalen Code und keineswegs "esoterisch". Da haben ich schon ganz andere Konstrukte gesehen, bei denen ich dann auch zustimmen würde

Was mir hier eher etwas aufstößt sind die String-Kopien, die man z.B. mit String Views oder meinentwegen einer Referenz vermeiden könnte. Besonders wenn die Lebensdauer dieser Variablen ohnehin nur diese kompakten Schleifen sind (Ja, ich kenne die Gefahr von Dangling References)

Lennox

@Finnegan siehe hier: https://stackoverflow.com/questions/4445706/post-increment-and-pre-increment-concept

Viele Leute glauben fälschlicherweise, dass die Inkrementierung zuerst erfolgen muss, und kommen daher oft zu dem Schluss, dass bestimmte Ausdrücke eine klar definierte Wirkung haben müssen, obwohl sie tatsächlich ein undefiniertes Verhalten aufweisen.

Lennox

@Finnegan sagte in Strings von Objekten vergleichen und ändern:

und keineswegs "esoterisch"

Ich habe es jetzt nur kurz überflogen, aber es sieht so aus, als wäre es "besser" (bzw. übersichtlicher), die total map mit 1 anstatt 0 zu initialisieren, also 1 einzufügen, wenn leer, oder ansonsten zu erhöhen. Dieser spezielle "Inkrement-Schritt" könnte in einer eigenen Funktion stehen, damit es übersichtlich bleibt.

Finnegan

@Lennox sagte in Strings von Objekten vergleichen und ändern:

@Finnegan sagte in Strings von Objekten vergleichen und ändern:

und keineswegs "esoterisch"

Ich habe es jetzt nur kurz überflogen, aber es sieht so aus, als wäre es "besser" (bzw. übersichtlicher), die total map mit 1 anstatt 0 zu initialisieren, also 1 einzufügen, wenn leer, oder ansonsten zu erhöhen. Dieser spezielle "Inkrement-Schritt" könnte in einer eigenen Funktion stehen, damit es übersichtlich bleibt.

Dann muss man aber explizit initialisieren. Ein Grund, weshalb die Implementierug so kompakt ist, ist, dass ein neu eingefügter int-Wert automatisch mit 0 initialisiert wird (unordered_map::operator[] garantiert Value Initialization und diese ist für primitive Typen wie int eine Zero-Initialization). Daher kann man einfach ++total[base] schreiben, auch wenn total[base] noch nicht existiert. Der Wert ist danach garantiert 1.

Man muss auch an die Wartbarkeit des Code denken. Hier eine zusätzliche Funktion zum Initialisieren neuer Map-Elemente einzuführen, nur um i++ statt ++i schreiben zu können, finde ich ein wenig Overkill und alles andere als "übersichtlich". Da würde ich stattdessen lieber so was machen, wenns unbedingt i++ sein soll

int n = seen[base]++;
c->displayName = base + " (" + std::to_string(n + 1) + ")";

Lennox

seen[base]++;
c->displayName = base + " (" + std::to_string(seen[base]) + ")";

fände ich besser.

Lennox

@all: Irgendwie sind die ersten Postings in diesem Thema jetzt weg... Bei euch auch?

e: Sind wieder da.