Merging-Vektoren ohne zusätzliche Speicher

Question

I kamen in diesem Codesegment in den zwei Vektoren zusammengefügt werden, in denen Elemente aus einem Vektor für den Fall von Doppel begünstigt werden:

std::vector<String> fields1 = fieldSource1.get(); 
std::vector<String> fields2 = fieldSource2.get(); 
// original 
fields1.insert(std::end(fields1), std::begin(fields2), std::end(fields2)); 
std::stable_sort(std::begin(fields1), std::end(fields1)); 
fields1.erase(std::unique(std::begin(fields1), std::end(fields1)), std::end(fields1)); 
return fields1; 

Da Strings ist einzigartig in ihrem jeweiligen Vektor, und dass Reihenfolge der Strings im Ausgabevektor ist irrelevent, ich denke, dass ich diesen Algorithmus effizienter machen kann.

Ich möchte zusätzliche Speicherzuweisung von Std :: Set_union() und Std :: Set_diff() vermeiden.

(Direkt ist std :: set_diff zu einem ursprünglichen Vektor Einfügen keine Option aufgrund iterator Entwertung während einer Größenänderung)

ich damit endete, das mit einem Iterator std :: set_diff mit einem Index ersetzt ist:

std::sort(std::begin(fields1), std::end(fields1)); 
std::sort(std::begin(fields2), std::end(fields2)); 
// Initialize iterators by index in case of resizing 
size_t index = 0; 
size_t end = std::size(fields1); 
std::remove_copy_if(std::begin(fields2), std::end(fields2), std::back_inserter(fields1), 
[&fields1, &index, end](String field)->bool{ 
    auto begin = std::begin(fields1); 
    found = std::lower_bound(begin+index, begin+end, field); 
    index = std::distance(begin, found); 
    return (*found) == field; 
}); 
return fields1; 

Meine Frage ist: kann ich diesen Zusammenführungsvorgang effizienter machen? Wenn nicht, kann ich es lesbarer machen?

Answer 1

Die Darstellung einer Menge von Strings als Vektor ist ineffizient, wenn Sie sie in einem sortierten oder zusammenführbaren Zustand halten möchten. Es ist besser, einen anderen Container wie std :: set oder std :: unordered_set zu verwenden, der viel bessere Leistungsgarantien bietet.

Beachten Sie, dass jede Lösung, die versucht, Zeichenfolgen an Ort und Stelle zu sortieren, den Speicher wahrscheinlich weiter fragmentiert und den Speicherdruck erheblich erhöht, als überhaupt die richtigen Datenstrukturen zu erstellen.

Wenn Sie sie als Vektor von Zeichenfolgen beibehalten müssen, können Sie eine Hashtabelle aller Zeichenfolgen erstellen, die an jedem Punkt gefunden wurden, und nur Zeichenfolgen zulassen, deren Zeichenfolgen noch nicht angezeigt wurden . Wenn Sie sehr viele Duplikate haben, kann diese Methode leistungsfähiger sein, als jede Liste unabhängig zu sortieren.

typedef std::size_t hash_type; 
typedef std::string value_type; 
typedef std::vector<value_type> values_type; 
typedef std::hash<value_type> value_hash_type; 
typedef std::unordered_set<hash_type> hash_set_type; 

bool is_new_hash(hash_set_type &hash_set, 
    const hash_type one_hash 
    ) 
{ 
    if (hash_set.find(one_hash) == hash_set.end()) 
    { 
     hash_set.insert(one_hash); 
     return true; 
    } 
    return false; 
} 

int main() 
{ 
    values_type str1, str2, dest; 
    str1.push_back("c"); 
    str1.push_back("a"); 
    str1.push_back("b"); 

    str2.push_back("c"); 
    str2.push_back("d"); 

    hash_set_type hash_set; 
    value_hash_type value_hash; 

    for (auto &s : str1) 
    { 
     if (is_new_hash(hash_set, value_hash(s))) 
      dest.push_back(s); 
    } 
    for (auto &s : str2) 
    { 
     if (is_new_hash(hash_set, value_hash(s))) 
      dest.push_back(s); 
    } 
    std::sort(dest.begin(), dest.end()); 
}