Entfernen Sie Doppelte Einträge in einem C++ - Vektor

Wollen einfach nur, um Duplikate entfernen. Pool ist vector<pair<string, int>> aber ich glaube, ich vermisse einige Elemente zu Beginn der Vektor-irgendwie. Kann jemand überprüfen, die Logik der Entfernung? Danke 🙂

Pool Master::eliminateDuplicates(Pool generation)
{
    for(int i = 0; i < generation.size(); i++)
    {
        string current = generation.at(i).first;

        for(int j = i; j < generation.size(); j++)
        {
            if(j == i)
            {
                continue;
            }
            else
            {
                string temp = generation.at(j).first;
                if(current.compare(temp) == 0)
                {
                    Pool::iterator iter = generation.begin() + j;
                    generation.erase(iter);
                }
            }
        }
    }

    return generation;
}
  • Tun Sie etwas dagegen, wenn es wird sortiert?
  • Eww, diese Kopien...
  • Ein einfacher (und wahrscheinlich schneller Weg, als die O(n^2) Weise, dass es zur Zeit dauert), dies zu tun ist das hinzufügen aller Elemente, die zu einer std::set und dann wieder zu einem std::vector.
  • Auch, ich nehme an, du meinst Pool ist ein vector<pair<string, int>>?
  • Ich dachte die setzt nur funktionieren würde, basierend auf den integer-Datentyp? Ich Vergleiche bei string-Duplikate. EDIT ja, sorry Tippfehler 😉
  • Ist diese Anweisung if(j == i){continue;} notwendig? Sie können einfach starten Sie die Schleife von i+1.
  • Führen könnte ein segmentation fault, wenn ich das Letzte element.
  • std::set arbeiten auf der Grundlage entweder operator< oder geben Sie einen Vergleich-Funktion verwenden kann. Es wäre ein ziemlich nutzloses gesetzt, wenn es funktioniert nur für Ganzzahlen!
  • In jedem Fall, Sie don nicht verwenden. Sie können Sortieren Sie Ihre Vektorgrafik und verwenden std::unque. Das wäre O(Nlog(N))

InformationsquelleAutor Jarrod Cabalzar | 2013-05-10
  1. 4

    Dies ist ein sehr häufiges Problem.

    Da nach dem löschen ein element der position j darauf springen Sie ein element durch die j++ auf die for-Schleife.
    die einfachste Lösung um das problem zu lösen, basierend auf deinem code ist das hinzufügen von j-- generation.erase(iter):

      generation.erase(iter);
  j--;
    • Danke, das war es. 😀
    InformationsquelleAutor Gisway
  2. 19

    Wenn Euch das nichts ausmacht Sortierung des Vektors, dann können Sie std::unique. Das wäre O(Nlog(N))

    #include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); 
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    for (const auto& i : v)
      std::cout << i << " ";
    std::cout << "\n";
}
    • +1 sollte Jemand schreiben, ein wiki / FAQ-Eintrag für alle die Brot-und-butter-Vektor-Verwendungen.
    • vereinbart.
    • SO sollten pflegen eine Liste der am häufigsten gestellten Fragen zu populären Themen, wie die Top-10-C++ - Fragen oder so. Das wäre praktisch. 😀
    • Ich Frage mich, warum in all den Antworten, die über die Verwendung std::unique niemand scheint es Wert zu erwähnen, dass unique berücksichtigt nicht das Letzte element ist.
    • Ich weiß nicht wirklich verstehen, was Sie hier bedeuten. std::unique's Verhalten scheint sehr intuitiv für mich.
    • aus der Dokumentation "entfernt alle aufeinander folgende doppelte Elemente aus dem Bereich [first, last)", also (1,2,3,1) werden (1,2,3,1). Wie ist das intuitiv? Ich weiß, warum ist die Reichweite der rechten Maustaste öffnen, und warum es sein muss, aber es sei denn, Sie sind sicher, dass es kein dupe auf die Letzte position, einzigartig scheint nutzlos.
    • Da alle standard-Bibliothek mit algorithmen arbeiten, die auf offene Bereiche, und in der Regel übergeben wir beginnen, Ende offen so.
    • Wenn Sie gehen, um zu Sortieren, warum nicht std::sort?

    InformationsquelleAutor juanchopanza
Schreibe einen Kommentar