C ++, copie définie sur vecteur

146

J'ai besoin de copier std::setvers 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

Où est le problème?

CrocodileDundee
la source
5
il y a aussi la assign()fonction:output.assign(input.begin(), input.end());
Gene Bushuyev
votre vecteur est vide. Il existe une multitude de façons de remédier à cela, comme les gens le soulignent ci-dessous.
AJG85
@Gene: assign () souhaite réserver () la quantité de stockage nécessaire à l'avance. Il utilisera les itérateurs d'entrée pour déterminer la quantité nécessaire, à moins que les itérateurs ne soient strictement InputIterator, auquel cas il sautera la réservation et entraînera des réallocations à chaque push_back (). À l'extrémité opposée du spectre, les BiderectionalIterators lui permettraient de simplement soustraire fin - commencer. Les itérateurs de std :: set, cependant, ne sont ni l'un ni l'autre (ils sont ForwardIterator), et c'est malheureux: dans ce cas, assign () parcourra tout l'ensemble pour déterminer sa taille - mauvaises performances sur les grands ensembles.
Sergey Shevchenko

Réponses:

213

Vous devez utiliser un back_inserter:

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

std::copyn'ajoute pas d'éléments au conteneur dans lequel vous insérez: il ne peut pas; il n'a qu'un itérateur dans le conteneur. Pour cette raison, si vous passez directement un itérateur de sortie à std::copy, vous devez vous assurer qu'il pointe vers une plage au moins suffisamment grande pour contenir la plage d'entrée.

std::back_insertercrée un itérateur de sortie qui appelle push_backun conteneur pour chaque élément, de sorte que chaque élément est inséré dans le conteneur. Sinon, vous auriez pu créer un nombre suffisant d'éléments dans le std::vectorpour contenir la plage en cours de copie:

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

Ou, vous pouvez utiliser le std::vectorconstructeur de plage:

std::vector<double> output(input.begin(), input.end()); 
James McNellis
la source
3
Salut James, au lieu de votre ligne std :: copy (le premier bloc de code dans votre réponse), ne pourrais-je pas faire à la output.insert(output.end(), input.begin(), input.end());place?
user2015453
ou utilisez simplement la version cbegin et cend: qu'en pensez output.insert(output.cend(), input.cbegin(), input.cend());-vous? Merci.
user2015453
2
Dois-je output.reserve (input.size ()); par moi-même ou puis-je espérer qu'un compilateur le fasse pour moi?
jimifiki
@jimifiki, aucun espoir, j'ai peur.
Alexis Wilke
Votre première initialisation vectorielle est incorrecte. Vous créez un tableau d' input,size()entrées vides, puis ajoutez les ajouts après cela. Je pense que vous voulez utiliser std::vector<double> output; output.reserve(input.size()); std::copy(...);.
Alexis Wilke
121

Utilisez simplement le constructeur du vecteur qui prend des itérateurs:

std::set<T> s;

//...

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

Supposons que vous vouliez juste le contenu de s dans v, et qu'il n'y ait rien dans v avant de copier les données dessus.

Jacob
la source
42

voici une autre alternative utilisant vector::assign:

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

Vous n'avez pas réservé suffisamment d'espace dans votre objet vectoriel pour contenir le contenu de votre ensemble.

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());
Marlon
la source
1
Cela ne mérite pas -1. En particulier, cela permet au vecteur de ne faire qu'une seule allocation (car il ne peut pas déterminer la distance des itérateurs d'ensemble dans O (1)), et, s'il n'était pas défini pour le vecteur de mettre à zéro chaque élément une fois construit, cela pourrait cela vaut la peine de laisser la copie se résumer à un memcpy. Ce dernier pourrait encore valoir la peine si l'implémentation détermine que la boucle dans le ctor du vecteur peut être supprimée. Bien entendu, le premier peut également être réalisé avec réserve.
Fred Nurk
Je ne sais pas. Laisse moi t'aider avec ça.
wilhelmtell
Je vous ai donné un -1, mais c'était une réflexion de ma part. Faites une petite modification pour que je puisse annuler mon vote, et je vous donnerai un +1: c'est en fait une solution très propre en raison de la propriété fail-first.
Fred Foo
Je viens de comprendre que si je modifie la réponse moi-même, je peux faire un vote pour. Fait cela, vous a donné un +1 pour l'allocation de mémoire échouée en premier. Désolé!
Fred Foo
3

Je pense que le moyen le plus efficace est de préallouer puis de mettre en place des éléments:

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;
}

De cette façon, nous n'appellerons le constructeur de copie que pour chaque élément au lieu d'appeler d'abord le constructeur par défaut, puis de copier l'opérateur d'affectation pour les autres solutions répertoriées ci-dessus. Plus de précisions ci-dessous.

  1. back_inserter peut être utilisé mais il invoquera push_back () sur le vecteur ( https://en.cppreference.com/w/cpp/iterator/back_insert_iterator ). emplace_back () est plus efficace car elle évite de créer un temporaire lors de l'utilisation de push_back () . Ce n'est pas un problème avec les types construits de manière triviale, mais sera une implication de performance pour les types construits non trivialement (par exemple std :: string).

  2. Nous devons éviter de construire un vecteur avec l'argument size qui fait que tous les éléments sont construits par défaut (pour rien). Comme avec une solution utilisant std :: copy () , par exemple.

  3. Et, enfin, la méthode vector :: assign () ou le constructeur prenant la plage de l'itérateur ne sont pas de bonnes options car ils invoqueront std :: distance () (pour connaître le nombre d'éléments) sur les itérateurs d' ensemble . Cela entraînera l' itération supplémentaire indésirable par les tous définis éléments , car l'ensemble est une structure de données binaires arbre de recherche et il ne met pas en œuvre itérateurs d'accès aléatoire.

J'espère que cela pourra aider.

dshvets1
la source
s'il vous plaît ajouter une référence à une autorité pourquoi c'est rapide et quelque chose comme pourquoi un back_insertern'a pas besoin d'être utilisé
Tarick Welling
Ajout de plus de clarifications dans la réponse.
dshvets1
1

std::copyne peut pas être utilisé pour insérer dans un récipient vide. Pour ce faire, vous devez utiliser un insert_iterator comme ceci:

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
la source
3
Cela échoue la première fois que le vecteur se réalloue: l'itérateur de output.begin () est invalidé.
Fred Nurk