Concatenando dois std :: vectors

686

Como concatenar dois std::vectors?

emlai
fonte
5
As respostas dadas na verdade não concatenam. Eles anexam uma cópia. Pode haver um uso (para o ponto de vista da eficiência) para criar um método de concatenação std :: vector, no entanto, seria necessário um compartilhamento sofisticado do gerenciamento dos nós e é provavelmente por isso que não foi feito.
FauChristian
8
@FauChristian: Não, pode não ser útil do ponto de vista da eficiência. A memória vetorial deve ser contínua; portanto, o que lhe é sugerido é impossível. Se você quisesse "algum compartilhamento sofisticado do gerenciamento dos nós" e se mudasse a classe de vetores dessa maneira, acabaria com um deque. Mesmo assim, é muito difícil reutilizar a memória da maneira sugerida, embora isso comece a ser um pouco mais viável. Não acho que esteja implementado atualmente. O principal é que nesse compartilhamento de nós de gerenciamento (um deque) o nó final pode estar parcialmente vazio.
Cookie
4
@lecaruyer Você percebe que você só marcou uma pergunta que foi feita dois anos antes como uma duplicata
eshirima
9
Eu sou o único a perguntar por que isso não é implementado como a + bou a.concat(b)na biblioteca padrão? Talvez a implementação padrão não ser o melhor, mas cada concatenação de matriz não precisa ser micro-otimizado
oseiskar
9
anos de evolução, a sobrecarga de operador mais avançada de qualquer linguagem convencional, um sistema de modelos que dobra a complexidade da linguagem e, no entanto, a resposta não é v = v1 + v2;
Spike0xff

Respostas:

726
vector1.insert( vector1.end(), vector2.begin(), vector2.end() );
Robert Gamble
fonte
53
Eu adicionaria apenas o código para obter primeiro o número de elementos que cada vetor contém e definir o vetor1 como aquele que contém o maior. Caso contrário, você está fazendo muitas cópias desnecessárias.
Joe Pineda
34
Eu tenho uma pergunta. Isso funcionará se o vetor1 e o vetor2 forem os mesmos vetores?
Alexander Rafferty
6
Se você concatenou vários vetores para um, é útil chamar reserveo vetor de destino primeiro?
Faheem Mitha
33
@AlexanderRafferty: Somente se vector1.capacity() >= 2 * vector1.size(). O que é atípico, a menos que você tenha telefonado std::vector::reserve(). Caso contrário, o vector vai realocar, invalidar os iterators passados como parâmetros 2 e 3.
Desenhou Dormann
28
É uma pena que não haja uma expressão mais sucinta na biblioteca padrão. .concatou +=algo parecido
nmr
193

Se você estiver usando o C ++ 11 e desejar mover os elementos, em vez de apenas copiá-los, poderá usar std::move_iteratorjunto com insert (ou copy):

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<int> dest{1,2,3,4,5};
  std::vector<int> src{6,7,8,9,10};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  // Print out concatenated vector.
  std::copy(
      dest.begin(),
      dest.end(),
      std::ostream_iterator<int>(std::cout, "\n")
    );

  return 0;
}

Isso não será mais eficiente para o exemplo com ints, pois movê-los não é mais eficiente do que copiá-los, mas para uma estrutura de dados com movimentos otimizados, ele pode evitar a cópia de um estado desnecessário:

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<std::vector<int>> dest{{1,2,3,4,5}, {3,4}};
  std::vector<std::vector<int>> src{{6,7,8,9,10}};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  return 0;
}

Após a mudança, o elemento src é deixado em um estado indefinido, mas seguro para destruir, e seus elementos anteriores foram transferidos diretamente para o novo elemento do dest no final.

Alex
fonte
6
O método std :: make_move_iterator () me ajudou ao tentar concatenar std :: vectors de std :: unique_ptr.
Knitschi
Qual a diferença entre isso e std::move(src.begin(), src.end(), back_inserter(dest))?
kshenoy
145

Eu usaria a função de inserção , algo como:

vector<int> a, b;
//fill with data
b.insert(b.end(), a.begin(), a.end());
Tom Ritter
fonte
77

Ou você pode usar:

std::copy(source.begin(), source.end(), std::back_inserter(destination));

Esse padrão é útil se os dois vetores não contêm exatamente o mesmo tipo de coisa, porque você pode usar algo em vez de std :: back_inserter para converter de um tipo para outro.

Roger Lipscombe
fonte
7
o método de cópia não é uma maneira tão boa. Ele chamará push_back várias vezes, o que significa que, se muitos elementos precisarem ser inseridos, isso pode significar várias realocações. é melhor usar o insert, pois a implementação do vetor poderia fazer alguma otimização para evitar realocações. pode reservar memória antes de iniciar a cópia
Yogesh Arora
7
@ Yogesh: concedido, mas não há nada para você ligar reserveprimeiro. O motivo std::copyàs vezes é útil é se você deseja usar algo diferente back_inserter.
22410 Roger Lipscombe
Quando você diz "várias alocações", isso é verdade - mas o número de alocações é no pior log (número de entradas adicionadas) - o que significa que o custo de adicionar uma entrada é constante no número de entradas adicionadas. (Basicamente, não se preocupe, a menos que o perfil mostre que você precisa de uma reserva).
Martin Bonner apoia Monica
Você pode usar std :: transform para fazer isso.
Martin Broadhurst 07/02
1
copiar é péssimo, mesmo com reserva. vector :: insert evitará todas as verificações: quick-bench.com/bLJO4OfkAzMcWia7Pa80ynwmAIA
Denis Yaroshevskiy
63

Com o C ++ 11, prefiro seguir o anexo b a a:

std::move(b.begin(), b.end(), std::back_inserter(a));

quando ae bnão se sobrepõem e bnão será mais usado.


Isto é std::movede <algorithm>, não o habitual std::move de <utility>.

Deqing
fonte
10
Comportamento indefinido se a for realmente b (o que é bom se você sabe que isso nunca pode acontecer - mas vale a pena estar ciente do código de uso geral).
Martin Bonner apoia Monica
1
@ Martinartner Obrigado por mencionar isso. Provavelmente eu deveria voltar ao insertcaminho antigo , que é mais seguro.
Deqing
15
Ah, o OTHER std :: move. Bastante confuso a primeira vez que você o vê.
Xaxxon
1
Isso é diferente de insert()com move_iterators? Se sim, como?
GPHilo #
1
Adicionei uma observação sobre o std::moveque estamos falando aqui, pois a maioria das pessoas não conhece essa sobrecarga. Espero que seja uma melhoria.
YSC
38
std::vector<int> first;
std::vector<int> second;

first.insert(first.end(), second.begin(), second.end());
James Curran
fonte
24

Eu prefiro um que já é mencionado:

a.insert(a.end(), b.begin(), b.end());

Mas se você usa C ++ 11, há mais uma maneira genérica:

a.insert(std::end(a), std::begin(b), std::end(b));

Além disso, não faz parte de uma pergunta, mas é recomendável usá-lo reserveantes de anexá-lo para obter um melhor desempenho. E se você estiver concatenando o vetor consigo mesmo, sem reservar, ele falhará, então você sempre deve reserve.


Então, basicamente, o que você precisa:

template <typename T>
void Append(std::vector<T>& a, const std::vector<T>& b)
{
    a.reserve(a.size() + b.size());
    a.insert(a.end(), b.begin(), b.end());
}
ST3
fonte
2
std::é deduzido através da pesquisa dependente de argumento . end(a)Será suficiente.
Asu
4
O @Asu ADL só adicionará std::se o tipo de origem avier std, o que anula o aspecto genérico.
Potatoswatter
bom ponto. nesse caso, é um vetor, portanto funcionaria de qualquer maneira, mas sim, é uma solução melhor.
Asu
std :: begin () / end () foram adicionados para coleções (como matrizes) que não as possuem como funções membro. Mas matrizes também não têm uma função de membro insert () e chama a pergunta "Existe uma coleção com um insert () mas sem begin () (que funciona com o std :: begin ())?"
21818 James Curran #
15

Com o intervalo v3 , você pode ter uma concatenação lenta :

ranges::view::concat(v1, v2)

Demo .

Jarod42
fonte
12

Você deve usar vector :: insert

v1.insert(v1.end(), v2.begin(), v2.end());
Boris
fonte
2
Não é o mesmo com a resposta dada por Tom Ritter e Robert Gamble em 2008?
IgNite
9

Um aumento geral no desempenho para concatenar é verificar o tamanho dos vetores. E mesclar / inserir o menor com o maior.

//vector<int> v1,v2;
if(v1.size()>v2.size()) {
    v1.insert(v1.end(),v2.begin(),v2.end());
} else {
    v2.insert(v2.end(),v1.begin(),v1.end());
}
Vikramjit Roy
fonte
Tão simples, mas nunca pensei nisso dessa maneira!
Zimano 15/03/19
2
O código de exemplo está incorreto. v1.insert(v2.end()...está a utilizar uma iteração para v2a determinar a posição em v1.
1855 David Stone
Você também pode usar uma troca rápida. @ DavidStone Eu editei para que a ordem da concat fosse alterada. É possível adicionar ao início de um vetor?
Q9
Você pode inserir no início, mas isso será mais lento. Para realmente "concatenar", no entanto, a ordem normalmente importa, e é isso que você precisa fazer.
David Stone
7

Se você deseja concatenar vetores de forma concisa, pode sobrecarregar o +=operador.

template <typename T>
std::vector<T>& operator +=(std::vector<T>& vector1, const std::vector<T>& vector2) {
    vector1.insert(vector1.end(), vector2.begin(), vector2.end());
    return vector1;
}

Então você pode chamar assim:

vector1 += vector2;
Daniel Giger
fonte
6

Se você estiver interessado em uma garantia forte de exceção (quando o construtor de cópias puder lançar uma exceção):

template<typename T>
inline void append_copy(std::vector<T>& v1, const std::vector<T>& v2)
{
    const auto orig_v1_size = v1.size();
    v1.reserve(orig_v1_size + v2.size());
    try
    {
        v1.insert(v1.end(), v2.begin(), v2.end());
    }
    catch(...)
    {
        v1.erase(v1.begin() + orig_v1_size, v1.end());
        throw;
    }
}

Similar append_movecom garantia forte não pode ser implementado em geral se o construtor de movimento do elemento vetorial puder lançar (o que é improvável, mas ainda).

AlexT
fonte
Não é possível v1.erase(...jogar também?
Class Skeleton
insertjá lida com isso. Além disso, essa chamada para eraseé equivalente a a resize.
Potatoswatter
Eu gosto disso - obrigado!
natersoz
5

Adicione este ao seu arquivo de cabeçalho:

template <typename T> vector<T> concat(vector<T> &a, vector<T> &b) {
    vector<T> ret = vector<T>();
    copy(a.begin(), a.end(), back_inserter(ret));
    copy(b.begin(), b.end(), back_inserter(ret));
    return ret;
}

e use desta maneira:

vector<int> a = vector<int>();
vector<int> b = vector<int>();

a.push_back(1);
a.push_back(2);
b.push_back(62);

vector<int> r = concat(a, b);

r conterá [1,2,62]

Stepan Yakovenko
fonte
Não sei por que isso foi rejeitado. Pode não ser a maneira mais eficiente de fazer isso, mas não está errada e é eficaz.
Leeor_net 19/06/2016
4

Aqui está uma solução de uso geral usando a semântica de movimentação do C ++ 11:

template <typename T>
std::vector<T> concat(const std::vector<T>& lhs, const std::vector<T>& rhs)
{
    if (lhs.empty()) return rhs;
    if (rhs.empty()) return lhs;
    std::vector<T> result {};
    result.reserve(lhs.size() + rhs.size());
    result.insert(result.cend(), lhs.cbegin(), lhs.cend());
    result.insert(result.cend(), rhs.cbegin(), rhs.cend());
    return result;
}

template <typename T>
std::vector<T> concat(std::vector<T>&& lhs, const std::vector<T>& rhs)
{
    lhs.insert(lhs.cend(), rhs.cbegin(), rhs.cend());
    return std::move(lhs);
}

template <typename T>
std::vector<T> concat(const std::vector<T>& lhs, std::vector<T>&& rhs)
{
    rhs.insert(rhs.cbegin(), lhs.cbegin(), lhs.cend());
    return std::move(rhs);
}

template <typename T>
std::vector<T> concat(std::vector<T>&& lhs, std::vector<T>&& rhs)
{
    if (lhs.empty()) return std::move(rhs);
    lhs.insert(lhs.cend(), std::make_move_iterator(rhs.begin()), std::make_move_iterator(rhs.end()));
    return std::move(lhs);
}

Observe como isso difere de appending para a vector.

Daniel
fonte
4

Você pode preparar seu próprio modelo para o operador +:

template <typename T> 
inline T operator+(const T & a, const T & b)
{
    T res = a;
    res.insert(res.end(), b.begin(), b.end());
    return res;
}

A próxima coisa - basta usar +:

vector<int> a{1, 2, 3, 4};
vector<int> b{5, 6, 7, 8};
for (auto x: a + b)
    cout << x << " ";
cout << endl;

Este exemplo fornece a saída:

1 2 3 4 5 6 7 8
Vladimir U.
fonte
2
Usar T operator+(const T & a, const T & b)é perigoso, é melhor usar vector<T> operator+(const vector<T> & a, const vector<T> & b).
Matthieu H
4

Existe um algoritmo std::mergedo C ++ 17 , que é muito fácil de usar,

Abaixo está o exemplo:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    //DATA
    std::vector<int> v1{2,4,6,8};
    std::vector<int> v2{12,14,16,18};

    //MERGE
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

    //PRINT
    for(auto item:dst)
        std::cout<<item<<" ";

    return 0;
}
Pavan Chandaka
fonte
2
Eu não acho que seja mais fácil de usar do que isso std::vector::insert, mas faz algo diferente: mesclar dois intervalos em um novo intervalo versus inserir um vetor no final de outro. Vale mencionar na resposta?
jb
4

Se seu objetivo é simplesmente iterar o intervalo de valores para fins somente leitura, uma alternativa é agrupar os dois vetores em torno de um proxy (O (1)) em vez de copiá-los (O (n)), para que sejam vistos imediatamente como um único, contíguo.

std::vector<int> A{ 1, 2, 3, 4, 5};
std::vector<int> B{ 10, 20, 30 };

VecProxy<int> AB(A, B);  // ----> O(1)!

for (size_t i = 0; i < AB.size(); i++)
    std::cout << AB[i] << " ";  // ----> 1 2 3 4 5 10 20 30

Consulte https://stackoverflow.com/a/55838758/2379625 para obter mais detalhes, incluindo a implementação 'VecProxy', bem como prós e contras.

Ronald Souza
fonte
3
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2 = {11, 12, 13, 14, 15};
copy(v2.begin(), v2.end(), back_inserter(v1));
instância
fonte
6
Embora esse trecho de código possa resolver o problema, ele não explica por que ou como responde à pergunta. Por favor incluir uma explicação para o seu código , como o que realmente ajuda a melhorar a qualidade do seu post. Sinalizadores / revisores: para respostas somente de código como esta, com voto negativo, não exclua! (. Nota: Esta resposta pode realmente ser bastante simples de fazer uma explicação, e assim downvotes, desnecessária Você ainda pode querer adicionar uma explicação para evitar mais bandeiras NAA / VLQ.)
Scott Weldon
2

Eu implementei essa função que concatena qualquer número de contêineres, movendo-se de rvalue-reference e copiando de outra forma

namespace internal {

// Implementation detail of Concatenate, appends to a pre-reserved vector, copying or moving if
// appropriate
template<typename Target, typename Head, typename... Tail>
void AppendNoReserve(Target* target, Head&& head, Tail&&... tail) {
    // Currently, require each homogenous inputs. If there is demand, we could probably implement a
    // version that outputs a vector whose value_type is the common_type of all the containers
    // passed to it, and call it ConvertingConcatenate.
    static_assert(
            std::is_same_v<
                    typename std::decay_t<Target>::value_type,
                    typename std::decay_t<Head>::value_type>,
            "Concatenate requires each container passed to it to have the same value_type");
    if constexpr (std::is_lvalue_reference_v<Head>) {
        std::copy(head.begin(), head.end(), std::back_inserter(*target));
    } else {
        std::move(head.begin(), head.end(), std::back_inserter(*target));
    }
    if constexpr (sizeof...(Tail) > 0) {
        AppendNoReserve(target, std::forward<Tail>(tail)...);
    }
}

template<typename Head, typename... Tail>
size_t TotalSize(const Head& head, const Tail&... tail) {
    if constexpr (sizeof...(Tail) > 0) {
        return head.size() + TotalSize(tail...);
    } else {
        return head.size();
    }
}

}  // namespace internal

/// Concatenate the provided containers into a single vector. Moves from rvalue references, copies
/// otherwise.
template<typename Head, typename... Tail>
auto Concatenate(Head&& head, Tail&&... tail) {
    size_t totalSize = internal::TotalSize(head, tail...);
    std::vector<typename std::decay_t<Head>::value_type> result;
    result.reserve(totalSize);
    internal::AppendNoReserve(&result, std::forward<Head>(head), std::forward<Tail>(tail)...);
    return result;
}
Desenhou
fonte
1

Se o que você procura é uma maneira de anexar um vetor a outro após a criação, vector::inserté sua melhor aposta, como já foi respondido várias vezes, por exemplo:

vector<int> first = {13};
const vector<int> second = {42};

first.insert(first.end(), second.cbegin(), second.cend());

Infelizmente, não há como construir um const vector<int>, como acima você deve construir e depois insert.


Se o que você está realmente procurando é um contêiner para conter a concatenação desses dois vector<int>s, pode haver algo melhor disponível para você, se:

  1. O seu vectorcontém primitivas
  2. Suas primitivas contidas são de tamanho 32 bits ou menor
  3. Você quer um constcontêiner

Se tudo isso for verdade, sugiro usar o basic_stringwho que char_typecorresponde ao tamanho do primitivo contido no seu vector. Você deve incluir um static_assertno seu código para validar que esses tamanhos permaneçam consistentes:

static_assert(sizeof(char32_t) == sizeof(int));

Com isso, você pode apenas fazer:

const u32string concatenation = u32string(first.cbegin(), first.cend()) + u32string(second.cbegin(), second.cend());

Para obter mais informações sobre as diferenças entre stringe vectorvocê pode procurar aqui: https://stackoverflow.com/a/35558008/2642059

Para um exemplo ao vivo deste código, você pode procurar aqui: http://ideone.com/7Iww3I

Jonathan Mee
fonte
0

Essa solução pode ser um pouco complicada, mas boost-rangetambém tem outras coisas boas a oferecer.

#include <iostream>
#include <vector>
#include <boost/range/algorithm/copy.hpp>

int main(int, char**) {
    std::vector<int> a = { 1,2,3 };
    std::vector<int> b = { 4,5,6 };
    boost::copy(b, std::back_inserter(a));
    for (auto& iter : a) {
        std::cout << iter << " ";
    }
    return EXIT_SUCCESS;
}

Muitas vezes, a intenção é combinar vetor ae biterar sobre ele, fazendo alguma operação. Nesse caso, existe a joinfunção simples ridícula .

#include <iostream>
#include <vector>
#include <boost/range/join.hpp>
#include <boost/range/algorithm/copy.hpp>

int main(int, char**) {
    std::vector<int> a = { 1,2,3 };
    std::vector<int> b = { 4,5,6 };
    std::vector<int> c = { 7,8,9 };
    // Just creates an iterator
    for (auto& iter : boost::join(a, boost::join(b, c))) {
        std::cout << iter << " ";
    }
    std::cout << "\n";
    // Can also be used to create a copy
    std::vector<int> d;
    boost::copy(boost::join(a, boost::join(b, c)), std::back_inserter(d));
    for (auto& iter : d) {
        std::cout << iter << " ";
    }
    return EXIT_SUCCESS;
}

Para vetores grandes, isso pode ser uma vantagem, pois não há cópia. Também pode ser usado para copiar uma generalização facilmente para mais de um contêiner.

Por alguma razão, não há nada como boost::join(a,b,c), o que poderia ser razoável.

Aleph0
fonte
0

Você pode fazer isso com algoritmos STL pré-implementados usando um modelo para um uso do tipo polimórfico.

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>

void concat(std::vector<T>& valuesa, std::vector<T>& valuesb){

     for_each(valuesb.begin(), valuesb.end(), [&](int value){ valuesa.push_back(value);});
}

int main()
{
    std::vector<int> values_p={1,2,3,4,5};
    std::vector<int> values_s={6,7};

   concat(values_p, values_s);

    for(auto& it : values_p){

        std::cout<<it<<std::endl;
    }

    return 0;
}

Você pode limpar o segundo vetor se não quiser usá-lo mais ( clear()método).

rekkalmd
fonte
-3

Para ser honesto, você pode concatenar rapidamente dois vetores copiando elementos de dois vetores para o outro ou apenas anexando apenas um dos dois vetores !. Depende do seu objetivo.

Método 1: Atribuir novo vetor com seu tamanho é a soma do tamanho de dois vetores originais.

vector<int> concat_vector = vector<int>();
concat_vector.setcapacity(vector_A.size() + vector_B.size());
// Loop for copy elements in two vectors into concat_vector

Método 2: anexar o vetor A adicionando / inserindo elementos do vetor B.

// Loop for insert elements of vector_B into vector_A with insert() 
function: vector_A.insert(vector_A .end(), vector_B.cbegin(), vector_B.cend());
nvnhcmus
fonte
4
O que sua resposta acrescenta que ainda não foi fornecida em outras respostas?
Mat
13
@ Mat: caracteres em negrito.
Marcv81
Se os vetores originais não forem mais necessários depois, pode ser melhor usá-los para std::move_iteratorque os elementos sejam movidos em vez de copiados. (consulte en.cppreference.com/w/cpp/iterator/move_iterator ).
tmlen 23/02
O que é setcapacity? O que é function: ?
LF
@ LF Acho que ele está falando sobre o resizemétodo.
Matthieu H