C ++, Kopie auf Vektor gesetzt

146

Ich muss kopieren std::setnach std::vector:

std::set <double> input;
input.insert(5);
input.insert(6);

std::vector <double> output;
std::copy(input.begin(), input.end(), output.begin()); //Error: Vector iterator not dereferencable

Wo ist das Problem?

Crocodile Dundee
quelle
5
Es gibt auch assign()Funktion:output.assign(input.begin(), input.end());
Gene Bushuyev
Ihr Vektor ist leer. Es gibt eine Vielzahl von Möglichkeiten, dies zu beheben, wie die Leute unten zeigen.
AJG85
@Gene: assign () möchte () die erforderliche Speichermenge im Voraus reservieren. Mithilfe der Eingabe-Iteratoren wird bestimmt, wie viel benötigt wird, es sei denn, die Iteratoren sind ausschließlich InputIterator. In diesem Fall wird die Reservierung übersprungen und bei jedem push_back () werden Neuzuweisungen vorgenommen. Am anderen Ende des Spektrums würden BiderectionalIterators es erlauben, nur end - begin zu subtrahieren. Die Iteratoren von std :: set sind jedoch keine (sie sind ForwardIterator), und das ist bedauerlich: In diesem Fall wird assign () nur den gesamten Satz durchlaufen, um seine Größe zu bestimmen - schlechte Leistung bei großen Sätzen.
Sergey Shevchenko

Antworten:

213

Sie müssen Folgendes verwenden back_inserter:

std::copy(input.begin(), input.end(), std::back_inserter(output));

std::copyfügt dem Container, in den Sie einfügen, keine Elemente hinzu: es kann nicht; Es hat nur einen Iterator im Container. Wenn Sie einen Ausgabe-Iterator direkt an übergeben std::copy, müssen Sie daher sicherstellen, dass er auf einen Bereich verweist, der mindestens groß genug ist, um den Eingabebereich aufzunehmen.

std::back_inserterErstellt einen Ausgabe-Iterator, der push_backfür jedes Element einen Container aufruft , sodass jedes Element in den Container eingefügt wird. Alternativ könnten Sie eine ausreichende Anzahl von Elementen in erstellt haben std::vector, um den zu kopierenden Bereich aufzunehmen:

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

Oder Sie können den std::vectorBereichskonstruktor verwenden:

std::vector<double> output(input.begin(), input.end()); 
James McNellis
quelle
3
Hallo James, könnte ich anstelle Ihrer std :: copy-Zeile (dem ersten Codeblock in Ihrer Antwort) nicht einfach output.insert(output.end(), input.begin(), input.end());stattdessen etwas tun ?
user2015453
oder benutze einfach die cbegin and cend version: output.insert(output.cend(), input.cbegin(), input.cend());Was denkst du? Vielen Dank.
user2015453
2
Sollte ich output.reserve (input.size ()); alleine oder kann ich hoffen, dass ein Compiler das für mich macht?
Jimifiki
@ Jimifiki, keine Hoffnung, ich fürchte.
Alexis Wilke
Ihre erste Vektorinitialisierung ist falsch. Sie erstellen ein Array mit input,size()leeren Einträgen und hängen die Anhänge danach an. Ich denke du willst es benutzen std::vector<double> output; output.reserve(input.size()); std::copy(...);.
Alexis Wilke
121

Verwenden Sie einfach den Konstruktor für den Vektor, der Iteratoren benötigt:

std::set<T> s;

//...

std::vector v( s.begin(), s.end() );

Angenommen, Sie möchten nur den Inhalt von s in v und nichts in v, bevor Sie die Daten darauf kopieren.

Jacob
quelle
42

Hier ist eine andere Alternative mit vector::assign:

theVector.assign(theSet.begin(), theSet.end());
TeddyC
quelle
24

Sie haben nicht genügend Speicherplatz in Ihrem Vektorobjekt reserviert, um den Inhalt Ihres Sets aufzunehmen.

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());
Marlon
quelle
1
Dies verdient -1 nicht. Dies ermöglicht insbesondere, dass der Vektor nur eine Zuordnung vornehmen kann (da er den Abstand der gesetzten Iteratoren in O (1) nicht bestimmen kann), und wenn nicht definiert wurde, dass der Vektor jedes Element bei der Konstruktion auf Null setzt, könnte dies möglich sein Es lohnt sich, die Kopie auf ein Memcpy reduzieren zu lassen. Letzteres könnte sich noch lohnen, wenn die Implementierung herausfindet, dass die Schleife im ctor des Vektors entfernt werden kann. Ersteres kann natürlich auch mit Vorbehalt erreicht werden.
Fred Nurk
Ich weiß es nicht. Lass mich dir damit helfen.
Wilhelmtell
Ich habe dir eine -1 gegeben, aber es war ein Thinko von meiner Seite. Nehmen Sie eine kleine Änderung vor, damit ich meine Stimme rückgängig machen kann, und ich gebe Ihnen eine +1: Dies ist aufgrund der Fail-First-Eigenschaft eine sehr saubere Lösung.
Fred Foo
Ich habe gerade erst herausgefunden, dass ich eine positive Bewertung abgeben kann, wenn ich die Antwort selbst bearbeite. Haben Sie das getan, haben Sie eine +1 für die Fail-First-Speicherzuweisung erhalten. Es tut uns leid!
Fred Foo
3

Ich denke, der effizienteste Weg besteht darin, Elemente vorab zuzuweisen und dann zu platzieren:

template <typename T>
std::vector<T> VectorFromSet(const std::set<T>& from)
{
    std::vector<T> to;
    to.reserve(from.size());

    for (auto const& value : from)
        to.emplace_back(value);

    return to;
}

Auf diese Weise rufen wir nur den Kopierkonstruktor für jedes Element auf, anstatt zuerst den Standardkonstruktor aufzurufen und dann den Zuweisungsoperator für andere oben aufgeführte Lösungen zu kopieren. Weitere Erläuterungen weiter unten.

  1. back_inserter kann verwendet werden, ruft jedoch push_back () für den Vektor auf ( https://en.cppreference.com/w/cpp/iterator/back_insert_iterator ). emplace_back () ist effizienter, da bei Verwendung von push_back () keine temporären Elemente erstellt werden . Dies ist bei trivial konstruierten Typen kein Problem, wird jedoch eine Leistungsimplikation für nicht trivial konstruierte Typen (z. B. std :: string) sein.

  2. Wir müssen vermeiden, einen Vektor mit dem Größenargument zu konstruieren, wodurch alle Elemente standardmäßig konstruiert werden (für nichts). Wie zum Beispiel bei einer Lösung mit std :: copy () .

  3. Und schließlich sind die Methode vector :: assign () oder der Konstruktor, der den Iteratorbereich verwendet, keine guten Optionen, da sie std :: distance () (um die Anzahl der Elemente zu kennen) für festgelegte Iteratoren aufrufen . Dies führt zu unerwünschten zusätzlichen Iterationen durch alle Set- Elemente, da es sich bei dem Set um eine Datenstruktur des binären Suchbaums handelt und keine Iteratoren mit wahlfreiem Zugriff implementiert werden.

Hoffentlich hilft das.

dshvets1
quelle
Bitte fügen Sie einen Verweis auf eine Behörde hinzu, warum dies schnell ist und warum ein back_inserternicht verwendet werden muss
Tarick Welling
Weitere Erläuterungen in der Antwort hinzugefügt.
dshvets1
1

std::copykann nicht zum Einfügen in einen leeren Behälter verwendet werden. Dazu müssen Sie einen insert_iterator wie folgt verwenden:

std::set<double> input;
input.insert(5);
input.insert(6);

std::vector<double> output;
std::copy(input.begin(), input.end(), inserter(output, output.begin())); 
Bradley Swain
quelle
3
Dies schlägt bei der ersten Neuzuweisung des Vektors fehl: Der Iterator von output.begin () wird ungültig.
Fred Nurk