¿La mejor forma de extraer un subvector de un vector?

Supongamos que tengo un std::vector (llamémoslo myVec ) de tamaño N ¿Cuál es la forma más sencilla de construir un nuevo vector consistente en una copia de los elementos X a Y, donde 0 <= X <= Y <= N-1? Por ejemplo, myVec [100000] a myVec [100999] en un vector de tamaño 150000 .

Si esto no se puede hacer de manera eficiente con un vector, ¿hay otro tipo de datos STL que deba usar en su lugar?

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

Es una operación O (N) para construir el nuevo vector, pero realmente no hay una mejor manera.

Solo usa el constructor vectorial.

 std::vector data(); // Load Z elements into data so that Z > Y > X std::vector sub(&data[100000],&data[101000]); 

std::vector(input_iterator, input_iterator) , en su caso foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000); , ve por ejemplo aquí

Si no se van a modificar ambos (no agregar / eliminar elementos, modificar los ya existentes está bien siempre que preste atención a los problemas de subprocesamiento), simplemente puede pasar data.begin() + 100000 y data.begin() + 101000 , y pretender que son el begin() y el end() de un vector más pequeño.

O bien, dado que se garantiza que el almacenamiento vectorial será contiguo, simplemente puede pasar una matriz de 1000 elementos:

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

Ambas técnicas toman tiempo constante, pero requieren que la longitud de los datos no aumente, lo que provoca una reasignación.

No mencionó qué tipo es std::vector<...> myVec , pero si es un tipo simple o estructura / clase que no incluye punteros, y desea la mejor eficiencia, entonces puede hacer una memoria directa copiar (que creo que será más rápido que las otras respuestas proporcionadas). Aquí hay un ejemplo general para std::vector myVec donde type en este caso es 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 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 

En estos días, usamos span s! Entonces tu escribirías:

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

para obtener un lapso de 1000 elementos del mismo tipo que myvec ‘s. Ahora, esto no es una copia, es solo una vista de los datos en el vector, así que ten cuidado. Si quieres una copia real, puedes hacer:

 std::vector new_vec(my_subspan.begin(), my_subspan.end()); 

Notas:

  • Con C ++ 20 usaría std::span y #include lugar de #include .
  • Para obtener más información acerca de los tramos, consulte: ¿Qué es un “tramo” y cuándo debería usar uno?

Puede usar la copia STL con el rendimiento O (M) cuando M es el tamaño del subvector.

La única manera de proyectar una colección que no sea el tiempo lineal es hacerlo de forma perezosa, donde el “vector” resultante es en realidad un subtipo que delega en la colección original. Por ejemplo, el método List#subseq la List#subseq crea una List#subseq en tiempo constante. Sin embargo, esto solo funciona si la colección es inmutable y si el idioma subyacente tiene una recolección de basura.

De acuerdo. Esta es una discusión bastante antigua. Pero acabo de descubrir algo ordenado:

slice_array – ¿Podría ser una alternativa rápida? No lo he probado.

Publicando esto tarde solo para otros … Apuesto a que el primer codificador ya está hecho. Para los tipos de datos simples, no se necesita copiar, solo revierte a los buenos viejos métodos de código C.

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

Luego pase el puntero p y len a cualquier cosa que necesite un subvector.

notelen debe ser !! len < myVec.size()-start

Tal vez el array_view / span en la biblioteca GSL es una buena opción.

Aquí también hay una implementación de archivo único: array_view .

Copie elementos de un vector a otro fácilmente
En este ejemplo, estoy usando un vector de pares para que sea fácil de entender
`

 vector > v(n); //we want half of elements in vector a and another half in vector b vector > a(v.begin(),v.begin()+n/2); vector > 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)] 


Como puede ver, puede copiar fácilmente elementos de un vector a otro, si quiere copiar elementos del índice 10 al 16, por ejemplo, entonces usaríamos

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

y si quiere elementos del índice 10 a algún índice desde el final, entonces en ese caso

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

Espero que esto ayude, solo recuerda en el último caso v.end()-5 > v.begin()+10

Otra opción más: útil, por ejemplo, cuando se mueve entre un thrust::device_vector y un thrust::host_vector , donde no se puede usar el constructor.

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

También debería ser la complejidad O (N)

Puedes combinar esto con el código anwer superior

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