La meilleure façon d'extraire un sous-vecteur d'un vecteur?

Supposons que j'ai une std::vector(appelons-la myVec) de taille N. Quelle est la façon la plus simple de construire un nouveau vecteur composé d'une copie des éléments X à Y, où 0 <= X <= Y <= N-1? Par exemple, myVec [100000]grâce à myVec [100999]un vecteur de taille 150000.

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

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

C'est une opération O (N) pour construire le nouveau vecteur, mais il n'y a pas vraiment de meilleure façon.

Utilisez simplement le constructeur vectoriel.

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

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

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

De nos jours, nous utilisons spans! Vous écririez donc:

#include <gsl/span>

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

pour obtenir une plage de 1000 éléments du même type que ceux myvecde. Ou une forme plus concise:

auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);

(mais je n'aime pas autant cela, car la signification de chaque argument numérique n'est pas entièrement claire; et cela empire si la longueur et start_pos sont du même ordre de grandeur.)

Quoi qu'il en soit, n'oubliez pas que ce n'est pas une copie, c'est juste une vue des données dans le vecteur, alors soyez prudent. Si vous voulez une copie réelle, vous pouvez faire:

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

Remarques:

• gslsignifie Guidelines Support Library. Pour plus d'informations sur gsl, voir: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library .
• Pour une implémentation de gsl, voir: https://github.com/Microsoft/GSL
• C ++ 20 fournit une implémentation de span. Vous utiliseriez std::spanet #include <span>plutôt que #include <gsl/span>.
• Pour plus d'informations sur les étendues, voir: Qu'est-ce qu'une «étendue» et quand dois-je en utiliser une?
• std::vector a un gazillion de constructeurs, il est super facile de tomber dans un que vous n'aviez pas l'intention d'utiliser, alors soyez prudent.

Si les deux ne vont pas être modifiés (pas d'ajout / suppression d'éléments - la modification des éléments existants est très bien tant que vous tenez compte des problèmes de thread), vous pouvez simplement contourner data.begin() + 100000et data.begin() + 101000, et prétendre qu'ils sont le begin()et end()d'un vecteur plus petit.

Ou, comme le stockage vectoriel est garanti contigu, vous pouvez simplement contourner un tableau de 1000 é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.

Cette discussion est assez ancienne, mais la plus simple n'est pas encore mentionnée, avec initialisation de liste :

 vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2}; 

Il nécessite c ++ 11 ou supérieur.

Exemple d'utilisation:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    vector<int> big_vector = {5,12,4,6,7,8,9,9,31,1,1,5,76,78,8};
    vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};

    cout << "Big vector: ";
    for_each(big_vector.begin(), big_vector.end(),[](int number){cout << number << ";";});
    cout << endl << "Subvector: ";
    for_each(subvector.begin(), subvector.end(),[](int number){cout << number << ";";});
    cout << endl;
}

Résultat:

Big vector: 5;12;4;6;7;8;9;9;31;1;1;5;76;78;8;
Subvector: 6;7;8;9;9;31;1;1;5;76;

Vous n'avez pas mentionné le type std::vector<...> myVec, mais s'il s'agit d'un type simple ou d'une structure / classe qui n'inclut pas de pointeurs et que vous voulez la meilleure efficacité, vous pouvez faire une copie de mémoire directe (qui, je pense, sera plus rapide que la autres réponses fournies). Voici un exemple général de l' std::vector<type> myVecendroit où se trouve typedans ce cas 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 simplement utiliser insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);

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

La seule façon de projeter une collection qui n'est pas du temps 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 List#subseqméthode de Scala crée une sous-séquence en temps constant. Cependant, cela ne fonctionne que si la collection est immuable et si la langue sous-jacente est garbage collection.

Publier ce retard juste pour les autres ... Je parie que le premier codeur est terminé maintenant. Pour les types de données simples, aucune copie n'est nécessaire, il suffit de revenir aux bonnes vieilles méthodes de code C.

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

Passez ensuite le pointeur p et un len à tout ce qui nécessite un sous-vecteur.

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

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

Voici également une implémentation d'un seul fichier: array_view .

Copier facilement des éléments d'un vecteur à un autre
Dans cet exemple, j'utilise un vecteur de paires pour le rendre facile à comprendre
`

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 voir, vous pouvez facilement copier des éléments d'un vecteur à un autre, si vous souhaitez copier des éléments de l'index 10 à 16 par exemple, nous utiliserions

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

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

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

j'espère que cela aide, rappelez-vous juste dans le dernier cas v.end()-5 > v.begin()+10

Encore une autre option: utile par exemple lors du déplacement entre a thrust::device_vectoret a 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));

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

Vous pouvez combiner cela 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));