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

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

  •  05-07-2019
  •  | 
  •  

Pregunta

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 consta de una copia de los elementos X a Y, donde 0 <= X <= Y <= N-1?Por ejemplo, myVec [100000] a 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 debería usar en su lugar?

¿Fue útil?

Solución 

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.

Otros consejos

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

Hoy en día utilizamos span¡s!Entonces 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 lapso de 1000 elementos del mismo tipo que myvec's.Ahora, esto es 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:

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

O, 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 requieren un tiempo constante, pero requieren que la longitud de los datos no aumente, lo que desencadena una reasignación.

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, puede hacer una copia de memoria directa (que yo pensar será más rápido que las otras respuestas proporcionadas). Aquí hay un ejemplo general de std::vector<type> 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<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

Puede usar 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 " es en realidad un subtipo que delega a la colección original. Por ejemplo, el método List#subseq 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.

Ok. Esta es una discusión bastante antigua. Pero acabo de descubrir algo bueno:

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

Publicar esto tarde solo para otros ... Apuesto a que el primer codificador ya está listo. 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 desea 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, al moverse entre un thrust::device_vector y un thrust::host_vector, donde no puedes usar el constructor.

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

También debería 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));

Podrías usar insert 

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top