¿La mejor manera 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 simple de construir un nuevo vector que consiste en una copia de los elementos X a Y, donde 0 <= X <= Y <= N-1? Por ejemplo, a myVec [100000]través myVec [100999]de 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 debería usar en su lugar?

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

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

Solo usa el constructor de vectores.

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), en su caso foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, vea por ejemplo aquí

En estos días, usamos spans! Entonces escribirías:

#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);

para obtener un lapso de 1000 elementos del mismo tipo que myvec's. O una forma más concisa:

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

(pero esto no me gusta tanto, ya que el significado de cada argumento numérico no está del todo claro; y empeora si la longitud y start_pos son del mismo orden de magnitud).

De todos modos, recuerde que esto no es una copia, es solo una vista de los datos en el vector, así que tenga cuidado. Si desea una copia real, puede hacer:

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

Notas:

• gslsignifica Biblioteca de soporte de guías. Para más información sobregsl , consulte: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library .
• Para una implementación de gsl , consulte: https://github.com/Microsoft/GSL
• C ++ 20 proporciona una implementación de span . Lo usarías std::spany en #include <span>lugar de #include <gsl/span>.
• Para obtener más información acerca de los tramos, consulte: ¿Qué es un "tramo" y cuándo debo usar uno?
• std::vector tiene miles de millones de constructores, es muy fácil caer en uno que no pretendías usar, así que ten cuidado.

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

O, dado que se garantiza que el almacenamiento vectorial sea 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 desencadena una reasignación.

Esta discusión es bastante antigua, pero la más simple aún no se menciona, con la inicialización de la lista :

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

Requiere c ++ 11 o superior.

Ejemplo de uso:

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

Resultado:

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;

No mencionó qué tipo std::vector<...> myVeces, pero si es un tipo simple o estructura / clase que no incluye punteros, y desea la mejor eficiencia, puede hacer una copia de memoria directa (que creo que será más rápido que el otras respuestas proporcionadas). Aquí hay un ejemplo general de std::vector<type> myVecdónde typeen 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<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

Podrías usar insert

vector<type> myVec { n_elements };

vector<type> newVec;

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

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

La única forma de proyectar una colección que no es tiempo lineal es hacerlo perezosamente, donde el "vector" resultante es en realidad un subtipo que delega en la colección original. Por ejemplo, el List#subseqmétodo de Scala crea una subsecuencia 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.

Publicar esto tarde solo para otros ... Apuesto a que el primer codificador ya ha terminado. Para los tipos de datos simples, no se necesita copia, simplemente vuelva a los viejos métodos de código C.

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

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

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

Quizás 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<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)]

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

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

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

vector<pair<int, int> > 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 ay thrust::device_vectora thrust::host_vector, donde no se puede usar el constructor.

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

También debe ser complejidad O (N)

Puedes combinar esto con el código de respuesta superior

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