Le meilleur moyen d'extraire un sous-vecteur d'un vecteur?

StackOverflow https://stackoverflow.com/questions/421573

  •  05-07-2019
  •  | 
  •  

Question

Supposons que j'ai un std::vector (appelons-le myVec) de taille N. Quel est le moyen le plus simple de construire un nouveau vecteur consistant en une copie des éléments de X à Y, où 0 & Lt; = X & Lt; = Y & Lt; = N-1? Par exemple, myVec [100000] à myVec [100999] dans un vecteur de taille 150000.

Si cela ne peut pas être fait efficacement avec un vecteur, y a-t-il un autre type de données STL que je devrais utiliser à la place?

Était-ce utile?

La solution 

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

La construction du nouveau vecteur est une opération O (N), mais il n'y a pas vraiment de meilleur moyen.

Autres conseils

Utilisez simplement le constructeur de vecteur. 

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);

std::vector(input_iterator, input_iterator), dans votre cas foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, voyez par exemple ici

Ces jours-ci, nous utilisons span s! Donc, vous écririez: 

#include <gsl/span>

...
auto start_pos = 100000;
auto length = 1000;
auto my_subspan = gsl::make_span(myvec).subspan(start_pos, length);

pour obtenir une étendue de 1000 éléments du même type que ceux de myvec. Il ne s'agit pas d'une copie, mais d'une vue des données contenues dans le vecteur. Soyez donc prudent. Si vous voulez une copie réelle, vous pouvez faire: 

std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());

Notes:

Si les deux ne vont pas être modifiés (pas d’ajout / suppression d’objets - il est bon d’en modifier des existants tant que vous tenez compte des problèmes de threading), vous pouvez simplement passer data.begin() + 100000 et data.begin() + 101000, et prétendre que ce sont les begin() et end() d'un vecteur plus petit.

Ou, étant donné que le stockage de vecteurs est assuré d'être contigu, vous pouvez simplement faire passer un tableau de 1 000 éléments: 

T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;

Ces deux techniques prennent un temps constant, mais nécessitent que la longueur des données n'augmente pas, ce qui déclenche une réallocation.

Vous n'avez pas mentionné le type std::vector<...> myVec, mais s'il s'agit d'un type simple ou d'une structure / classe n'incluant pas les pointeurs, et que vous souhaitez une efficacité optimale, vous pouvez effectuer une copie directe en mémoire (que je penser sera plus rapide que les autres réponses fournies). Voici un exemple général pour std::vector<type> myVec où type dans ce cas est int: 

typedef int type; //choose your custom type/struct/class
int iFirst = 100000; //first index to copy
int iLast = 101000; //last index + 1
int iLen = iLast - iFirst;
std::vector<type> newVec;
newVec.resize(iLen); //pre-allocate the space needed to write the data directly
memcpy(&newVec[0], &myVec[iFirst], iLen*sizeof(type)); //write directly to destination buffer from source buffer

Vous pouvez utiliser la copie STL avec performances O (M) lorsque M est la taille du sous-vecteur.

La seule façon de projeter une collection qui ne soit pas linéaire est de le faire paresseusement, où le & "vecteur &" résultant; est en fait un sous-type qui délègue à la collection d'origine. Par exemple, la méthode List#subseq de Scala crée une sous-séquence en temps constant. Toutefois, cela ne fonctionne que si la collection est immuable et si le langage sous-jacent utilise la récupération de place.

Ok. C'est une jolie vieille discussion. Mais je viens de découvrir quelque chose de chouette:

slice_array - pourrait-il s'agir d'une alternative rapide ? Je ne l'ai pas testé.

Afficher ce retard uniquement pour les autres..Je parie que le premier codeur est déjà terminé. Pour les types de données simples, aucune copie n'est nécessaire, il suffit de revenir aux anciennes méthodes de code C. 

std::vector <int>   myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;

Ensuite, passez le pointeur p et un len à tout élément nécessitant un sous-vecteur.

notelen doit être !! len < myVec.size()-start

Peut-être que la array_view / span dans la bibliothèque GSL est une bonne option.

Voici également une implémentation de fichier unique: array_view .

Copiez facilement des éléments d'un vecteur à un autre
Dans cet exemple, j’utilise un vecteur de paires pour faciliter la compréhension.
`

vector<pair<int, int> > v(n);

//we want half of elements in vector a and another half in vector b
vector<pair<lli, lli> > a(v.begin(),v.begin()+n/2);
vector<pair<lli, lli> > b(v.begin()+n/2, v.end());


//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
//then a = [(1, 2), (2, 3)]
//and b = [(3, 4), (4, 5), (5, 6)]

//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
//then a = [(1, 2), (2, 3), (3, 4)]
//and b = [(4, 5), (5, 6), (6, 7)]

'
Comme vous pouvez le constater, vous pouvez facilement copier des éléments d’un vecteur à un autre. Par exemple, si vous souhaitez copier des éléments des indices 10 à 16, nous utiliserions 

vector<pair<int, int> > a(v.begin()+10, v.begin+16);

et si vous voulez des éléments de l'index 10 à un index de la fin, alors dans ce cas 

vector<pair<int, int> > a(v.begin()+10, v.end()-5);

espérons que cela vous aidera, mais rappelez-vous que dans le dernier cas v.end()-5 > v.begin()+10

Encore une autre option: Utile par exemple pour passer d'un thrust::device_vector à un thrust::host_vector où vous ne pouvez pas utiliser le constructeur. 

std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));

Devrait également être la complexité O (N)

Vous pouvez combiner ceci avec le code de réponse supérieur 

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));

Vous pouvez simplement utiliser insert 

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top