c++ - new - ¿La mejor manera de extraer un subvector de un vector?

vector in c++ stl

Question

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 que consiste en una copia de los elementos X a Y, donde 0 <= X <= Y <= N-1? Por ejemplo, myVec [100000] través de 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?

Answer 1

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

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

Answer 2

En estos días, utilizamos span s! Así que escribirías:

#include <gsl/span>

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

para obtener un intervalo de 1000 elementos del mismo tipo que el de myvec . 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, podrías hacer:

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

Notas:

• Con C ++ 20 usaría std::span y #include <span> lugar de #include <gsl/span> .
• Para obtener más información sobre los intervalos , consulte: ¿Qué es un "intervalo" y cuándo debo usar uno?

Answer 3

La única forma de proyectar una colección que no sea lineal es hacerlo perezosamente, donde el "vector" resultante es en realidad un subtipo que delega a 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 es deportivo la recolección de basura.

Answer 4

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

Answer 5

Otra opción más: útil por ejemplo cuando se mueve entre thrust::device_vector y thrust::host_vector , donde no 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)

Podrías 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));

Answer 6

Publicación esta tarde solo para otros ... Apuesto a que el primer programador ya está hecho. Para tipos de datos simples no se necesita una copia, simplemente vuelva a los buenos métodos de código C antiguos.

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

Answer 7

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

Answer 8

Si no se van a modificar ambos (sin agregar / eliminar elementos, modificar los existentes está bien siempre que preste atención a los problemas de subprocesos), 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, como se garantiza que el almacenamiento de vectores es contiguo, simplemente puede pasar una matriz de 1000 elementos:

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

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

Answer 9

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

Answer 10

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

Aquí también hay una implementación de un solo archivo: array_view .

Answer 11

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

Answer 12

Copia 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 del final, entonces en ese caso

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

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

Answer 13

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) construir el nuevo vector, pero realmente no hay una mejor manera.