Melhor maneira de extrair um subvector a partir de um vector?

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

  •  05-07-2019
  •  | 
  •  

Pergunta

Suponha que eu tenho um std::vector (vamos chamá-lo myVec) de tamanho N. Qual é a maneira mais simples para a construção de um novo vector que consiste de uma cópia de elementos X através de Y, em que 0 <= X myVec [100000] myVec [100999] num vector de tamanho 150000.

Se isto não pode ser feito de forma eficiente com um vector, existe um outro tipo de dados STL que eu deveria usar em vez disso?

Foi útil?

Solução 

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

É um O (N) operação para construir o novo vector, mas não há realmente uma maneira melhor.

Outras dicas

Basta usar o construtor Vector. 

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), no seu caso foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, ver, por exemplo aqui

Hoje em dia, usamos spans! Então, você poderia escrever: 

#include <gsl/span>

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

para obter um espaço de 1000 elementos do mesmo tipo que myvec de. Agora, este é não uma cópia, é apenas uma visão dos dados do vector, por isso tome cuidado. Se você quiser uma cópia real, você poderia fazer: 

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

Notas:

Se ambos não vão ser modificadas (sem adição / exclusão de itens - modificar os já existentes é bom, desde que você preste atenção aos problemas de threading), você pode simplesmente passar em torno data.begin() + 100000 e data.begin() + 101000, e fingir que eles são o begin() e end() de um vector menor.

Ou, já que o armazenamento vector é garantido para ser contíguos, você pode simplesmente passar em torno de uma matriz 1000 Item: 

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

Ambas as estas técnicas levam tempo constante, mas exigem que o comprimento dos dados não aumenta, provocando uma realocação.

Você não mencionou que tipo std::vector<...> myVec é, mas se é um tipo simples ou struct / classe que não inclui ponteiros, e você quer a melhor eficiência, então você pode fazer uma cópia de memória direta (o que eu acho que vai ser mais rápido do que as outras respostas fornecidas). Aqui está um exemplo geral para std::vector<type> myVec onde type neste caso é 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

Você pode usar STL cópia com o desempenho O (M) quando M é o tamanho da subvector.

A única maneira de projetar uma coleção que não é linear do tempo é fazê-lo preguiçosamente, onde o "vector" resultante é realmente um subtipo que delegados da coleção original. Por exemplo, o método List#subseq Scala criar uma sub-sequência no tempo constante. No entanto, isso só funciona se a coleção é imutável e se a coleta de lixo esportes linguagem subjacente.

Ok. Esta é uma discussão bastante antiga. Mas eu só descobri algo puro:

slice_array - Esta poderia ser uma alternativa rápida ? Eu não testei.

postar esta tarde apenas para others..I apostar o primeiro codificador é feito por agora. Para tipos de dados simples é necessária nenhuma cópia, apenas reverter para bons métodos de código C antigos. 

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

Em seguida, passe o ponteiro p e um len a qualquer coisa que necessitam de um subvector.

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

Talvez a array_view / span na biblioteca GSL é uma boa opção.

Aqui também é uma única implementação de arquivo:. array_view

elementos copiar de um vetor para outro facilmente
Neste exemplo, estou usando um vetor de pares para torná-lo 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 você pode ver, você pode facilmente copiar elementos de um vetor para outro, se você quiser copiar elementos de índice de 10 a 16, por exemplo, então poderíamos usar 

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

e se você quiser elementos de índice de 10 a algum índice de ponta, então, nesse caso 

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

espero que isso ajude, basta lembrar no último caso v.end()-5 > v.begin()+10

No entanto, uma outra opção: Útil, por exemplo quando se deslocam entre uma thrust::device_vector e uma thrust::host_vector, onde você não pode usar o construtor. 

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

deve também ser complexidade O (N)

Você pode combinar isso com código anwer top 

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

Você pode simplesmente usar insert 

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top