C ++, cópia definida como vetor

146

Preciso copiar std::setpara std::vector:

std::set <double> input;
input.insert(5);
input.insert(6);

std::vector <double> output;
std::copy(input.begin(), input.end(), output.begin()); //Error: Vector iterator not dereferencable

Onde está o problema?

CrocodiloDundee
fonte
5
também existe a assign()função:output.assign(input.begin(), input.end());
Gene Bushuyev 17/02
seu vetor está vazio. Existem várias maneiras de remediar isso, embora as pessoas estejam apontando abaixo.
AJG85
@Gene: assign () quer reservar () a quantidade necessária de armazenamento antes do tempo. Ele usará os iteradores de entrada para determinar quanto é necessário, a menos que os iteradores sejam estritamente InputIterator; nesse caso, ignorará a reserva e resultará em realocações em cada push_back (). No extremo oposto do espectro, os BiderectionalIterators permitiriam apenas subtrair o final - começar. Os iteradores do std :: set, no entanto, não são nenhum (são ForwardIterator), e isso é lamentável: nesse caso, o assign () apenas percorre todo o conjunto para determinar seu tamanho - desempenho ruim em conjuntos grandes.
Sergey Shevchenko

Respostas:

213

Você precisa usar um back_inserter:

std::copy(input.begin(), input.end(), std::back_inserter(output));

std::copynão adiciona elementos ao contêiner no qual você está inserindo: não pode; ele possui apenas um iterador no contêiner. Por esse motivo, se você passar diretamente um iterador de saída std::copy, verifique se ele aponta para um intervalo que seja pelo menos grande o suficiente para manter o intervalo de entrada.

std::back_insertercria um iterador de saída que chama push_backum contêiner para cada elemento, para que cada elemento seja inserido no contêiner. Como alternativa, você poderia ter criado um número suficiente de elementos std::vectorpara manter o intervalo que está sendo copiado:

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

Ou você pode usar o std::vectorconstrutor range:

std::vector<double> output(input.begin(), input.end()); 
James McNellis
fonte
3
Oi James, em vez da sua linha std :: copy (o primeiro bloco de código na sua resposta), eu não poderia simplesmente fazer isso output.insert(output.end(), input.begin(), input.end());?
user2015453
ou apenas use a versão cbegin and cend: o output.insert(output.cend(), input.cbegin(), input.cend());que você acha? Obrigado.
User2015453
2
Devo output.reserve (input.size ()); sozinho ou posso esperar que algum compilador faça isso por mim?
Jimifiki 27/03
@ Jimifiki, sem esperança, eu tenho medo.
Alexis Wilke
Sua primeira inicialização de vetor está incorreta. Você cria uma matriz de input,size()entradas vazias e acrescenta os anexos depois disso. Eu acho que você pretende usar std::vector<double> output; output.reserve(input.size()); std::copy(...);.
Alexis Wilke
121

Basta usar o construtor para o vetor que leva os iteradores:

std::set<T> s;

//...

std::vector v( s.begin(), s.end() );

Supõe que você deseja apenas o conteúdo de s em v, e não há nada em v antes de copiar os dados para ele.

Jacob
fonte
42

aqui está outra alternativa usando vector::assign:

theVector.assign(theSet.begin(), theSet.end());
TeddyC
fonte
24

Você não reservou espaço suficiente no seu objeto de vetor para armazenar o conteúdo do seu conjunto.

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());
Marlon
fonte
1
Isso não merece -1. Em particular, isso permite que o vetor faça apenas uma alocação (já que não pode determinar a distância dos iteradores definidos em O (1)) e, se não foi definido para o vetor zerar cada elemento quando construído, isso poderia vale a pena permitir que a cópia se reduza a um memcpy. O último ainda pode valer a pena se a implementação descobrir o loop no ctor do vetor puder ser removida. Obviamente, o primeiro também pode ser alcançado com reserva.
Fred Nurk
Eu não sei. Deixe-me ajudá-lo com isso.
wilhelmtell
Eu dei um -1, mas foi um pensamento da minha parte. Faça uma edição pequena para que eu possa desfazer o meu voto, e eu darei um +1: essa é realmente uma solução muito limpa devido à propriedade fail-first.
Fred Foo
Eu só descobri que, se eu editar a resposta, posso fazer um voto positivo. Com isso, você recebeu um +1 para a alocação de memória com falha inicial. Desculpe!
Fred Foo
3

Eu acho que a maneira mais eficiente é pré-alocar e depois substituir elementos:

template <typename T>
std::vector<T> VectorFromSet(const std::set<T>& from)
{
    std::vector<T> to;
    to.reserve(from.size());

    for (auto const& value : from)
        to.emplace_back(value);

    return to;
}

Dessa forma, chamaremos apenas o construtor de cópia para cada elemento, em vez de chamar o construtor padrão primeiro e, em seguida, o operador de atribuição de cópia para outras soluções listadas acima. Mais esclarecimentos abaixo.

  1. back_inserter pode ser usado, mas chamará push_back () no vetor ( https://en.cppreference.com/w/cpp/iterator/back_insert_iterator ). emplace_back () é mais eficiente porque evita a criação de um temporário ao usar push_back () . Não é um problema com tipos trivialmente construídos, mas será uma implicação de desempenho para tipos não-trivialmente construídos (por exemplo, std :: string).

  2. Precisamos evitar a construção de um vetor com o argumento size, que faz com que todos os elementos sejam construídos por padrão (por nada). Como na solução usando std :: copy () , por exemplo.

  3. E, finalmente, o método vector :: assign () ou o construtor que utiliza o intervalo do iterador não são boas opções porque invocam std :: distance () (para saber o número de elementos) nos iteradores de conjunto . Isso causará iteração adicional indesejada nos elementos definidos , pois o conjunto é a estrutura de dados da Árvore de Pesquisa Binária e não implementa iteradores de acesso aleatório.

Espero que ajude.

dshvets1
fonte
Por favor, adicione uma referência a uma autoridade porque este é rápido e algo como por que um back_inserternão precisa ser usado
Tarick Welling
Adicionados mais esclarecimentos na resposta.
dshvets1
1

std::copynão pode ser usado para inserir em um recipiente vazio. Para fazer isso, você precisa usar um insert_iterator da seguinte forma:

std::set<double> input;
input.insert(5);
input.insert(6);

std::vector<double> output;
std::copy(input.begin(), input.end(), inserter(output, output.begin())); 
Bradley Swain
fonte
3
Isso falha na primeira vez que o vetor é realocado: o iterador de output.begin () é invalidado.
Fred Nurk 17/02/11