Quel est le meilleur moyen pour concaténer deux vecteurs?

Je suis en utilisant multitreading et souhaitez fusionner les résultats. Par exemple:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

Je veux AB avoir à la table des matières de l'Un et le contenu de B dans cet ordre. Quel est le moyen le plus efficace de faire quelque chose comme ça?

Si la recherche de l'efficacité lorsque vous travaillez avec de grands contenants de taille, il peut être plus efficace d'utiliser la liste, où vous pouvez épissure de l'un à l'autre avec plusieurs opérations de pointeur. Mais la liste a de l'espace, les frais généraux (pensez à utiliser seule liste chaînée).

InformationsquelleAutor jmasterx | 2010-07-05

c++vector

295
```
AB.reserve( A.size() + B.size() ); //preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );
```
- Merci! N'aurais pas pensé à la réserve.
- qu'est-ce que la complexité du temps pour une telle opération? Est-il temps constant O(n)?
- il faut copier chaque élément, il est donc O(n)
- Mais après amortissement constant complexité lorsqu'il est correctement mis en œuvre. http://en.cppreference.com/w/cpp/container/vector/push_back
- Pas sûr que ce soit pour poser une nouvelle question, ou pas, mais cela peut-il être amélioré lors de la prise de la sémantique de déplacement en compte? Est-il une manière que je peux attendre/demander au compilateur de faire un seul mémoire de déplacement à la place d'une boucle sur tous les éléments?
- Pas de. Il est amorti de la constante de temps pour push_back un élément. Pour repousser les éléments n est O(n)
- Je n'implique pas le contraire, mais merci pour la clarification. Note de la complexité d'une opération d'insertion n'est jamais donné, en termes de nombre d'éléments insérés - qui feront toujours O(n) -, mais en termes de nombre d'éléments déjà le conteneur, depuis que donne la mesure de son évolutivité.
- Pourquoi ne pas faire de l'AB.insert() après la déclaration d'AB assez bon. Pourquoi avons-nous besoin de préallouer de la mémoire?
- Agrawal AB.insert() pour insérer de nouveaux éléments, un par un, et cela peut conduire à l'inefficacité de l'allocation de la mémoire (la séquence de la mémoire des réaffectations).
- Ce qui impliquerait que le vecteur de la mise en œuvre ne fait pas parti du fait que les itérateurs sont à accès aléatoire (et donc de l'avant) itérateurs. Tout bon vecteur de mise en œuvre permettra de réaffecter une seule fois (pour chaque opération d'insertion sur les itérateurs), à moins que le itérateur est un itérateur d'entrée.
- Droit, mais il y a deux insert opérations ici.
- Oui comme je l'ai dit via "une fois (pour chaque opération d'insertion [...])". Je ne reçois pas votre point de vue. Je pense juste que le commentaire au sujet de l' -insert() l'insertion d'éléments, un par un, conduisant à une séquence de la mémoire des réaffectations- il est quelque peu trompeuse (au moins dans la commune ainsi que les OP cas). C'est pourquoi, ai-je commenté. Je n'implique pas que l'utilisation de la réserve est la mauvaise chose à faire. Il est tout à fait justifié, afin d'éviter une réaffectation des.
- Le droit, et je n'ai pas dit que vous implicites qui. Je suis juste en observant que, dans cet exemple particulier, la reserve n'ont de mérite. Donc vous êtes tous les deux droit à un certain degré.
- Je suis peut être en retard sur le bateau, mais ce qui est la logique derrière en utilisant l'inverse?
- ce n'est pas "inverse", c'est "la réserve". Le commentaire indique qu'il se réserve de la mémoire pour les nouveaux éléments.
- Vous pouvez utiliser std::move_iterator (voir ici) qui est un itérateur adaptateur qui renvoie une référence rvalue quand déréférencement il. Qui permet (mais pas de garanties) que la source des éléments sont déplacés.
InformationsquelleAutor Kirill V. Lyadvinsky
56

C'est précisément ce que la fonction de membre de std::vector::insert est pour
```
std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
```
- Sauf std::vector::insert est godawful lente lorsque vous essayez de faire est de concaténer deux vecteurs. C'est là que <algorithm> est échouer et vous voulez vraiment std::vector::extend était une vraie méthode.
- Lent par rapport à quoi?
- Peut-être qu'il vérifie assez d'espace sur chaque insertion de l'élément? À l'aide de réserver à l'avance permettra d'accélérer.
- C'est lent comparé à savoir comment préallouer la taille finale.
- Je ne serais pas surpris si tous les stdlib mise en œuvre spécialisé insert sur random-access itérateurs et réservés à l'avant.
- C'est juste un point, puisque nous savons que la source est également un vecteur (où itérateur distance a O(1) de la complexité). Encore, la garantie de la performance de insert sont quelque chose d'être conscient de quand vous pouvez souvent faire mieux en planifiant à l'avance.
- vérification de l'espace est à seulement quelques instructions: capacité de charge, de les comparer à la taille, par un saut conditionnel, qui est un coût négligeable pour la plupart des cas. Depuis size < capacity la plupart du temps, direction de la prévision sera probablement entraîner la non-réaffectation de la direction générale des instructions dans le pipeline d'instruction, la minimisation de la branche induite par la latence, sauf pour un faible nombre d'itérations. Cela suppose un bon vecteur de mise en œuvre, en plus de CPU instruction pipeline & [bon] direction de la prévision, mais ceux-ci sont assez fiables hypothèses pour une moderne suite d'outils et de machines de bureaux. Ne sais pas sur les smartphones mais..
InformationsquelleAutor Shirik
27

Dépend si vous en avez vraiment besoin de se concaténer les deux vecteurs ou vous voulez donner l'apparence de la concaténation de l'intérêt de l'itération. Le boost::rejoignez la fonction

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/utilities/join.html

vous donnera cette.
```
std::vector<int> v0;
v0.push_back(1);
v0.push_back(2);
v0.push_back(3);

std::vector<int> v1;
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
...

BOOST_FOREACH(const int & i, boost::join(v0, v1)){
    cout << i << endl;
}
```
devrait vous donner
```
1
2
3
4
5
6
```
Note boost::joignez-vous à ne pas copier les deux vecteurs dans un nouveau conteneur
mais génère une paire d'itérateurs (gamme) qui couvrent la durée de
les deux récipients. Il y aura des conséquences sur les performances, mais peut-être
moins que la copie de toutes les données dans un nouveau conteneur d'abord.
- Belle idée. Après avoir réfléchi pendant un certain temps j'ai réalisé cet objectif peut également être accompli sans l'aide de bibliothèques boost. J'ai posté une réponse expliquant comment.
InformationsquelleAutor bradgonesurfing
8

Basé sur Cyrille V. Lyadvinsky répondre, j'ai fait une nouvelle version. Cet extrait de l'utilisation modèle et la surcharge. Avec elle, vous pouvez écrire vector3 = vector1 + vector2 et vector4 += vector3. J'espère que ça peut aider.
```
template <typename T>
std::vector<T> operator+(const std::vector<T> &A, const std::vector<T> &B)
{
    std::vector<T> AB;
    AB.reserve( A.size() + B.size() );                //preallocate memory
    AB.insert( AB.end(), A.begin(), A.end() );        //add A;
    AB.insert( AB.end(), B.begin(), B.end() );        //add B;
    return AB;
}

template <typename T>
std::vector<T> &operator+=(std::vector<T> &A, const std::vector<T> &B)
{
    A.reserve( A.size() + B.size() );                //preallocate memory without erase original data
    A.insert( A.end(), B.begin(), B.end() );         //add B;
    return A;                                        //here A could be named AB
}
```
- Entendez-vous d'ajouter les éléments de chaque vecteur à l'autre? Ou tu veux ajouter? C'est clair maintenant, mais pour les 5 prochaines années..? Vous ne devriez pas la surcharge de l'opérateur si le sens est ambigu.
- Je veux concate. J'ai écrit cette réponse il y a 3 ans. Je sais encore ce que Cela signifie. Pas de problème. Si C++ pourrait fournir sa propre surcharge, il sera encore meilleur. (et oui :: est pris 😉
- Certainement pas clair que, en général, v1 + v2 ne représente pas plus.
- href="https://tio.run/##K6gsycjPM/7/P1HBViHaUMcolisJxDLWMYnl4iooyswr0UhU0FZI0vz/HwA" title="Python 3 – Essayer en Ligne" >bien
- Alternative serait d'utiliser @ comme en F#
InformationsquelleAutor aloisdg says Reinstate Monica
3

Dans la direction de Bradgonesurfing, en réponse, de nombreuses fois, on n'a pas vraiment besoin pour concaténer deux vecteurs (O(n)), mais plutôt juste travailler avec eux comme s'ils étaient enchaînés (O(1)). Si c'est votre cas, il peut être fait sans la nécessité de bibliothèques Boost.

L'astuce est de créer un vecteur de proxy: une classe wrapper qui manipule références de deux vecteurs de l'extérieur, vu comme une seule, contigus, qui peut ensuite être consulté/parcouru exactement comme vous le feriez sur un réel vecteur.

UTILISATION
```
std::vector<int> A{ 1, 2, 3, 4, 5};
std::vector<int> B{ 10, 20, 30 };

VecProxy<int> AB(A, B);  //----> O(1). No copies performed!

for (size_t i = 0; i < AB.size(); i++)
    std::cout << AB[i] << " ";  //----> Output: 1 2 3 4 5 10 20 30

std::cout << AB[6]; //----> Output: 20
```
Mise en ŒUVRE
```
template <class T>
class VecProxy {
private:
    std::vector<T>& v1, v2;
public:
    VecProxy(std::vector<T>& ref1, std::vector<T>& ref2) : v1(ref1), v2(ref2) {}
    const T& operator[](const size_t& i) const;
    const size_t size() const;
};

template <class T>
const T& VecProxy<T>::operator[](const size_t& i) const{
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};

template <class T>
const size_t VecProxy<T>::size() const { return v1.size() + v2.size(); };
```
PRINCIPAL AVANTAGE

Il est O(1) (constante de temps) pour la créer, et avec un minimum de supplément d'allocation de mémoire. Dans la pratique, c'est une opération rapide, même lorsque l'on considère les énormes vecteurs, puisque vous remplacez |B| (ou |A|+|B|) de l'élément de copies par zéro. Aussi, il offre exactement le comportement souhaité.

Vecteurs de concaténation est au moins O(|B|) (lorsque B est ajouté à Un), quelle que soit la technique employée. Dans votre cas, puisque vous avez l'intention de travailler avec une 3ème vecteur AB, il est O(|A|+|B|). En fonction des vecteurs de la taille et du nombre de concaténation des opérations nécessaires, cela peut être un goulot d'étranglement. L'astuce ci-dessus, il aborde.

CERTAINES CHOSES À CONSIDÉRER
- Vous ne devriez aller pour elle si vous savez vraiment ce que vous faites lorsque vous traitez avec des références. Cette solution est conçu pour le but spécifique de la question, pour qui cela fonctionne assez bien. Pour l'utiliser dans un autre contexte peut conduire à un comportement inattendu si vous n'êtes pas sûr de la manière de références de travail.
- Dans cet exemple, AB ne pas fournir un non-const
  l'accès de l'opérateur ([ ]). N'hésitez pas à inclure, mais gardez à l'esprit: puisque AB contient des références, de lui attribuer
  les valeurs vont également affecter les éléments d'origine, à l'intérieur de A et/ou B. Si oui ou non ce est un
  caractéristique souhaitable, c'est une application spécifique de la question que l'on doit
  examiner attentivement.
- Tout changement effectué directement à A ou B (comme l'affectation de valeurs,
  le redimensionnement, etc.) aussi à "modifier" AB. Ce n'est pas nécessairement mauvais
  (en fait, il peut être très pratique: AB n'a jamais besoin d'être explicitement
  mis à jour pour tenir lui-même synchronisé à la fois à A et à B), mais il est
  certainement un comportement, il faut être conscient.
- Parce que chaque accès à un élément est précédé par un test (à savoir, "je
  < v1.taille()"), VecProxy temps d'accès, bien que constante, est également
  plus lente que celle des vecteurs. Il peut donc ne pas être la voie à suivre si
  vous devez, par exemple, à effectuer des millions de accès d'opérations par seconde,
  c'est à dire si le goulot d'étranglement se situe dans les opérations d'accès.
- Cette approche peut être généralisée à n vecteurs. Je n'ai pas essayé, mais
  il ne devrait pas être un gros problème.
- Il n'a pas de sens (à mes yeux) de fournir une copie des constructeurs pour
  ces procurations (puisqu'ils ne sont pas des vecteurs, après tout).
- Il n'est pas possible (ou au moins trop facile) à à l'échelle mondiale trier un
  VecProxy, car pas tous les éléments appartiennent à la même conteneur.
InformationsquelleAutor Ronald Chiesse

Un plus simple variante qui n'était pas encore mentionné:

copy(A.begin(),A.end(),std::back_inserter(AB));
copy(B.begin(),B.end(),std::back_inserter(AB));

Et à l'aide d'algorithme de fusion:


 

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
#include <sstream>
#include <string>

template<template<typename, typename...> class Container, class T>
std::string toString(const Container<T>& v)
{
    std::stringstream ss;
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(ss, ""));
    return ss.str();
};


int main()
{
    std::vector<int> A(10);
    std::vector<int> B(5);  //zero filled
    std::vector<int> AB(15);

    std::for_each(A.begin(), A.end(),
            [](int& f)->void
            {
                f = rand() % 100;
            });

    std::cout << "before merge: " << toString(A) << "\n";
    std::cout << "before merge: " << toString(B) << "\n";
    merge(B.begin(),B.end(), begin(A), end(A), AB.begin(), [](int&,int&)->bool {});
    std::cout << "after merge:  " << toString(AB) << "\n";

    return 1;
}

InformationsquelleAutor D. Alex

-1

Si vos vecteurs sont triés*, découvrez set_union de <algorithm>.
```
set_union(A.begin(), A.end(), B.begin(), B.end(), AB.begin());
```
Il y a une plus approfondie exemple dans le lien

*grâce rlbond
- aussi, il ne fait pas la même chose que la droite ajoutez - les éléments dans la plage de sortie est unique, ce qui peut ne pas être ce que l'OP voulait (ils pourraient même ne pas être comparables). Ce n'est certainement pas le moyen le plus efficace de le faire.
InformationsquelleAutor Cogwheel
-1

Toutes les solutions sont correctes, mais je l'ai trouvé plus facile il suffit d'écrire une fonction pour mettre en œuvre cette. comme ceci:
```
template <class T1, class T2>
void ContainerInsert(T1 t1, T2 t2)
{
    t1->insert(t1->end(), t2->begin(), t2->end());
}
```
De cette façon, vous pouvez éviter le placement temporaire comme ceci:
```
ContainerInsert(vec, GetSomeVector());
```
InformationsquelleAutor user3360767

Vous devez vous connecter pour publier un commentaire.