Melhor maneira de extrair um subvetor de um vetor?

295

Suponha que eu tenha um tamanho std::vector(vamos chamá-lo myVec) N. Qual é a maneira mais simples de construir um novo vetor que consiste em uma cópia dos elementos X a Y, onde 0 <= X <= Y <= N-1? Por exemplo, myVec [100000]através myVec [100999]de um vetor de tamanho 150000.

Se isso não puder ser feito eficientemente com um vetor, existe outro tipo de dados STL que eu deveria usar?

An̲̳̳drew
fonte
7
você diz que deseja extrair um subvetor, mas me parece que o que realmente deseja é uma visualização / acesso ao subvetor - a diferença é que uma visualização não copia - o C ++ da velha escola seria usar o ponteiro inicial e o ponteiro final, considerando que mem em um vetor std :: é contíguo, deve ser possível iterar usando ponteiros e, assim, evitar a cópia; no entanto, se você não se importa em copiar, basta inicializar um novo vetor com o escopo de seu anterior vector
serup
Há .data () ( cplusplus.com/reference/vector/vector/data ) desde o c ++ 11. No entanto, o uso de ponteiros é desencorajado em contêineres stl, consulte stackoverflow.com/questions/31663770/…
David Tóth

Respostas:

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

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

Greg Rogers
fonte
12
1, também é O (YX), o que é menos do que ou igual a O (N) (e na sua exemplo muito menos)
oriP
74
@ orip Bem, então é O (N) depois de tudo.
Johann Gerell 8/01/09
55
@ GregRogers: Não faz sentido usar a notação big-O em que N é um número específico. Big-O comunica a taxa de crescimento em relação à forma como N muda. Johann: É melhor não usar um nome de variável de duas maneiras. Nós normalmente diríamos qualquer um O(Y-X), ou diríamos O(Z) where Z=Y-X.
Mooing Duck
2
@GregRogers Ao usar esse método, precisamos declarar um novo vetor. Existe uma maneira de alterar o vetor original? algo como myVec (primeiro, último)? Eu sei que isso está errado, mas eu realmente preciso da solução, pois quero usar a recursão em meus códigos e preciso usar repetidamente o mesmo vetor (embora alterado). Obrigado!
precisa saber é o seguinte
13
Por que não apenas vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);?
aquirdturtle
88

Basta usar o construtor de vetores.

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);
Martin York
fonte
2
Ok, eu não sabia que era tão simples obter um iterador de um elemento vetorial arbitrário.
An̲̳̳drew 7/01/09
5
Tomar o endereço desses elementos do vetor é um hack não transportável que será interrompido se o armazenamento do vetor não for de fato contíguo. Use begin () + 100000 etc.
j_random_hacker
2
Meu problema, aparentemente, o padrão garante que o armazenamento vetorial seja contíguo. No entanto, é uma má prática trabalhar com endereços como este, pois certamente não é garantido que funcione para todos os contêineres que suportam acesso aleatório, enquanto begin () + 100000 é.
j_random_hacker
33
@j_random_hacker: Desculpe ter que discordar. A especificação STL para std :: vector foi alterada explicitamente para suportar esse tipo de procedimento. Além disso, um ponteiro é um tipo válido de iterador. Procure iterator_traits <> #
Martin York
6
@ taktak004 Não. Lembre-se que operator[]retorna uma referência. É apenas no ponto em que você lê ou escreve a referência que se tornaria uma violação de acesso. Como não fazemos nenhum dos dois, mas obtemos o endereço, não invocamos o UB.
Martin York
28

std::vector<T>(input_iterator, input_iterator), no seu caso foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, veja por exemplo aqui

Anteru
fonte
1
Como Andrew está tentando construir um novo vetor, eu recomendaria "std :: vector foo (..." em vez de copiar com "foo = std :: vector (...")
Drew Dormann
4
Sim, é claro, mas se você digita std :: vector <int> foo = std :: vector (...) ou std :: vector <int> foo (...) não deve importar.
Anteru
19

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

#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 obter um intervalo de 1000 elementos do mesmo tipo que myvec's. Ou uma forma mais concisa:

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

(mas não gosto muito disso, pois o significado de cada argumento numérico não é totalmente claro; e fica pior se o tamanho e o start_pos forem da mesma ordem de magnitude.)

De qualquer forma, lembre-se de que não é uma cópia, é apenas uma visão dos dados no vetor, portanto, tenha cuidado. Se você quiser uma cópia real, poderá:

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

Notas:

einpoklum
fonte
usaria cbegine cendapenas pelo princípio;) std::cbeginetc mesmo.
JHBonarius
1
@JHBonarius: vendo como esse código não é modelado na escolha do contêiner, não vejo um benefício específico; uma questão de gosto, suponho.
einpoklum
10

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() + 100000e data.begin() + 101000, e fingir que eles são o begin()e end()de um vector menor.

Ou, como é garantido que o armazenamento vetorial seja contíguo, você pode simplesmente transmitir uma matriz de 1000 itens:

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

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

Eclipse
fonte
Isso também é bom se você deseja que o vetor original e o subvetor sejam vinculados.
PyRulez
7

Essa discussão é bastante antiga, mas a mais simples ainda não foi mencionada, com a inicialização da lista :

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

Requer c ++ 11 ou superior.

Exemplo 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;
David Tóth
fonte
6

Você não mencionou o tipo std::vector<...> myVec, mas se é um tipo ou estrutura / classe simples que não inclui ponteiros e deseja a melhor eficiência, pode fazer uma cópia direta da memória (que eu acho que será mais rápida que a outras respostas fornecidas). Aqui está um exemplo geral de std::vector<type> myVeconde 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
MasterHD
fonte
2
Gostaria de saber se com -O3, @ using using constructor de Anteru std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, a versão mais longa deste não produzirá exatamente o mesmo assembly?
Sandthorn
1
O MSVC ++ 2015, por exemplo, compila std::vector<>(iter, iter)para memmove(), se apropriado (se o construtor for trivial, para uma definição adequada de trivial).
21718 Pablo H:
1
Não ligue memcpy. Faça um std::copyou um construtor que aceite um intervalo (dois iteradores), e o compilador e a biblioteca std.l conspirarão para chamar memcpyquando apropriado.
Bulletmagnet
4

Você poderia apenas usar insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Matheus Vinícius de Andrade
fonte
3

Você pode usar a cópia STL com desempenho O (M) quando M é o tamanho do subvetor.

Yuval F
fonte
Promovido o voto porque me indicou a direção certa, mas posso ver por que @LokiAstari sugere que não é a escolha correta - uma vez que a STL :: copy trabalha com duas matrizes std :: vector <T> do mesmo tamanho e tipo. Aqui, o OP deseja copiar uma subseção em um novo array menor, conforme descrito aqui no post do OP: "0 <= X <= Y <= N-1"
Andrew
@ Andrew, veja o exemplo usando std :: copy e std :: back_inserter
chrisg
@LokiAstari porque não?
chrisg
2
@LokiAstari Eu estava me referindo a uma edição que não sobreviveu à revisão por pares, que apresentou o exemplo <br/> vetor <T> newvec; std :: copy (myvec.begin () + 10000, myvec.begin () +10100, std :: back_inserter (newvec)); <br/> Nesse caso, você não precisa criar o destino primeiro, mas a inicialização direta é mais ... direta.
chrisg
1
@chrisg: São também duas linhas. Além disso, você precisa inserir uma terceira linha para garantir que seja eficiente. newvec.reserve(10100 - 10000);. Definitivamente, é uma opção e tecnicamente funcionará. Mas dos dois que você vai recomendar?
Martin York
1

A única maneira de projetar uma coleção que não é tempo linear é fazê-lo preguiçosamente, onde o "vetor" resultante é na verdade um subtipo que delega à coleção original. Por exemplo, o List#subseqmétodo de Scala cria uma sub-sequência em tempo constante. No entanto, isso funciona apenas se a coleção é imutável e se o idioma subjacente ostenta a coleta de lixo.

Daniel Spiewak
fonte
em c ++, para fazer isso, seria ter o vetor de shared_ptr em X em vez do vetor de X e, em seguida, copiar os SPs, mas infelizmente não acho que seja mais rápido porque a operação atômica envolvida com o cpying SP. Ou o vetor original pode ser uma const shared_ptr do vetor e você apenas faz referência ao sub-intervalo nele. ofc você não precisa torná-lo um shared_ptr do vetor, mas então você tem problemas ao longo da vida ... tudo isso está fora de minha cabeça, pode estar errado ...
NoSenseEtAl
0

Postando esta tarde apenas para outras pessoas ... aposto que o primeiro codificador já está pronto. Para tipos de dados simples, nenhuma cópia é necessária, basta reverter para bons métodos antigos de código C.

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

Em seguida, passe o ponteiro pe um len para qualquer coisa que precise de um subvetor.

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

mrrgu
fonte
Isso não realiza uma cópia.
precisa saber é o seguinte
0

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

Aqui também está uma implementação de arquivo único: array_view .

myd7349
fonte
Por favor, adicione a resposta aqui junto com o link. Como ligação externa pode mudar no futuro
Panther
0

Copie elementos de um vetor para outro facilmente
Neste exemplo, estou usando um vetor de pares para facilitar a compreensão de
`

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, pode copiar facilmente elementos de um vetor para outro, se quiser copiar elementos do índice 10 para 16, por exemplo, usaríamos

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

e se você quiser elementos do índice 10 para algum índice do final, 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

Jishu Dohare
fonte
0

Outra opção: Útil, por exemplo, ao se mover entre a thrust::device_vectore a 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));

Também deve ser complexidade O (N)

Você pode combinar isso com o melhor código da resposta

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