Strings von Objekten vergleichen und ändern

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.

Finnegan

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

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

fände ich besser.

Okay. Spielen wir das mal durch. Wenn wir neue Elemente mit 1 initialisieren wollen, müssen wir erst einmal herausfinden, ob wir es überhaupt mit einem neuen Element zu tun haben. Mit std::unordered_map<T>::find ist der Code etwas umständlich, aber ab C++20 gibt es std::unordered_map<T>::contains:

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

wird dann z.B. zu:

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

Jetzt haben wir allerdings das Problem, dass wir 3 Query-Operationen auf der Map haben. Einmal contains und zweimal operator[]. Irgendwie ist das etwas ineffizient, also ist es vielleicht besser mit C++ insert arbeiten:

auto [iter, was_inserted] = seen.insert({ base, 1});
int n = iter->second++;
c->displayName = base + " (" + std::to_string(n) + ")";

Immerhin: Ebenfalls nur eine einzige Operation (insert). Jetzt gehen auch i++ und std::to_string(n). Aber ist das wirklich "übersichtlicher"? Ich weiß ja nicht, ich empfinde eher solche überflüssigen Zeilen als schlechten Stil. Auch die das iter->second statt Subscript-Operator gefällt mir nicht sonderlich. Die Namen der std::pair-Member sind so nichtssagend. Kann man so machen, aber ich bevorzuge es kurz und kompakt. Und du hast ja sogar noch eine extra Funktion vorgeschlagen. Wie würdest du das denn stattdessen "sauber" implementieren, hoffentlich ohne zu viel Code hinzuzufügen, der die Wartungskosten erhöht?