Qual é a melhor maneira de concatenar dois vetores?

189

Estou usando a multitreading e quero mesclar os resultados. Por exemplo:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

Eu quero que AB tenha o conteúdo de A e o conteúdo de B nessa ordem. Qual é a maneira mais eficiente de fazer algo assim?

jmasterx
fonte
1
Se você estiver procurando eficiência ao trabalhar com contêineres de tamanho grande, pode ser mais eficiente usar a lista, onde é possível unir um ao outro com várias operações de ponteiro. Mas a lista tem sobrecarga de espaço (considere o uso de uma lista vinculada única).
Kemin Zhou # 03:

Respostas:

316
AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );
Kirill V. Lyadvinsky
fonte
6
Obrigado! Não teria pensado em reserva.
jmasterx
10
deve copiar cada elemento, por isso é O (n)
Kirill V. Lyadvinsky
1
Não tem certeza se deve fazer uma nova pergunta ou não, mas essa resposta pode ser aprimorada ao levar em consideração a semântica da movimentação? Existe alguma maneira de esperar / instruir o compilador a mover uma única memória em vez de fazer um loop sobre todos os elementos?
Broes De Cat
2
Não. É um tempo constante amortizado para pressionar um elemento. Para empurrar para trás elementos n é O (n)
de Konrad Lindenbach
1
@ Konrad Eu não sugeri o contrário, mas obrigado pelo esclarecimento. Observe que a complexidade de uma operação de inserção nunca é dada em termos do número de elementos que estão sendo inseridos - o que sempre fornecerá O (n) - mas em termos do número de elementos que já estão no contêiner, pois isso fornece uma medida de sua escalabilidade .
boycy
64

Este é precisamente o que a função de membro std::vector::inserté para

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
Shirik
fonte
4
@ Nick: Lento em comparação com o que?
GManNickG
2
Talvez ele verifique se há espaço suficiente em cada inserção do elemento? O uso antecipado da reserva acelerará.
RvdK
10
@ Nick: Eu não ficaria surpreso se todas as implementações stdlib modernas se especializassem insertem iteradores de acesso aleatório e reservassem antecipadamente.
GManNickG
1
@ Gman: Esse é um ponto justo, pois sabemos que a fonte também é um vetor (onde o iterador distancetem complexidade O (1)). Ainda assim, as garantias de desempenho insertsão algo a ser lembrado quando você pode fazer melhor planejando com antecedência.
Nick Bastin
2
A verificação de espaço no @RvdK é apenas algumas instruções: capacidade de carga, comparação com tamanho, salto condicional; tudo isso é um custo insignificante para a maioria dos casos. Como na size < capacitymaioria das vezes, a previsão de ramificação provavelmente fará com que as instruções da ramificação não realocada estejam no pipeline de instruções, minimizando a latência induzida por ramificação, exceto pela baixa contagem de iterações. Isso pressupõe uma boa implementação vetorial, mais o pipeline de instruções da CPU e a [boa] previsão de ramificação, mas essas são suposições bastante confiáveis ​​para uma moderna cadeia de ferramentas e máquina de desktop. Não sei sobre smartphones embora ..
boycy
27

Depende se você realmente precisa concatenar fisicamente os dois vetores ou se deseja dar a aparência de concatenação por causa da iteração. A função boost :: join

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/utilities/join.html

vai te dar isso.

std::vector<int> v0;
v0.push_back(1);
v0.push_back(2);
v0.push_back(3);

std::vector<int> v1;
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
...

BOOST_FOREACH(const int & i, boost::join(v0, v1)){
    cout << i << endl;
}

deveria te dar

1
2
3
4
5
6

Nota boost :: join não copia os dois vetores em um novo contêiner, mas gera um par de iteradores (intervalo) que cobrem a extensão dos dois contêineres. Haverá alguma sobrecarga de desempenho, mas talvez menos que a cópia de todos os dados para um novo contêiner primeiro.

bradgonesurfing
fonte
1
Boa ideia. Depois de pensar um pouco, percebi que esse objetivo também pode ser alcançado sem o uso de bibliotecas de impulso. Eu postei uma resposta explicando como.
Ronald Souza
11

Baseado na resposta de Kiril V. Lyadvinsky , fiz uma nova versão. Esse snippet usa modelo e sobrecarga. Com ele, você pode escrever vector3 = vector1 + vector2e vector4 += vector3. Espero que possa ajudar.

template <typename T>
std::vector<T> operator+(const std::vector<T> &A, const std::vector<T> &B)
{
    std::vector<T> AB;
    AB.reserve(A.size() + B.size());                // preallocate memory
    AB.insert(AB.end(), A.begin(), A.end());        // add A;
    AB.insert(AB.end(), B.begin(), B.end());        // add B;
    return AB;
}

template <typename T>
std::vector<T> &operator+=(std::vector<T> &A, const std::vector<T> &B)
{
    A.reserve(A.size() + B.size());                // preallocate memory without erase original data
    A.insert(A.end(), B.begin(), B.end());         // add B;
    return A;                                        // here A could be named AB
}
aloisdg movendo-se para codidact.com
fonte
1
Você quer adicionar os elementos de cada vetor um ao outro? Ou você quer acrescentar? Isso está claro agora, mas pelos próximos 5 anos ..? Você não deve sobrecarregar o operador se o significado for ambíguo.
SR
2
@ SR eu pretendo concordar. Eu escrevi esta resposta há 3 anos. Eu ainda sei o que isso significa. Não tem problema. Se o C ++ puder fornecer sua própria sobrecarga, será ainda melhor. (e sim ::é tomado;)
aloisdg se mudar para codidact.com
Definitivamente não é claro em geral que v1 + v2não representa adição.
Apollys suporta Monica
@Apollys well
aloisdg movendo-se para codidact.com
Alternativa seria usar @como em F #
aloisdg se mudar para codidact.com
5

Na direção da resposta de Bradgonesurfing, muitas vezes não é necessário concatenar dois vetores (O (n)), mas sim trabalhar com eles como se fossem concatenados (O (1)) . Se este for o seu caso, isso pode ser feito sem a necessidade de bibliotecas Boost.

O truque é criar um proxy de vetor: uma classe de wrapper que manipula referências a ambos os vetores, vistos externamente como um único e contíguo.

USO

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

VecProxy<int> AB(A, B);  // ----> O(1). No copies performed.

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

IMPLEMENTAÇÃO

template <class T>
class VecProxy {
private:
    std::vector<T>& v1, v2;
public:
    VecProxy(std::vector<T>& ref1, std::vector<T>& ref2) : v1(ref1), v2(ref2) {}
    const T& operator[](const size_t& i) const;
    const size_t size() const;
};

template <class T>
const T& VecProxy<T>::operator[](const size_t& i) const{
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};

template <class T>
const size_t VecProxy<T>::size() const { return v1.size() + v2.size(); };

PRINCIPAIS BENEFÍCIOS

É O (1) (tempo constante) para criá-lo e com alocação de memória extra mínima.

ALGUMAS COISAS A CONSIDERAR

  • Você só deve fazer isso se realmente souber o que está fazendo ao lidar com referências . Esta solução é destinada ao objetivo específico da pergunta feita, para a qual funciona muito bem . Empregá-lo em qualquer outro contexto pode levar a um comportamento inesperado se você não tiver certeza de como as referências funcionam.
  • Neste exemplo, AB não fornece um operador de acesso não-const ([]). Sinta-se à vontade para incluí-lo, mas lembre-se: como AB contém referências, atribuir valores a ele também afetará os elementos originais em A e / ou B. Se esse é um recurso desejável ou não, é uma pergunta específica do aplicativo. considere cuidadosamente.
  • Quaisquer alterações feitas diretamente em A ou B (como atribuir valores, classificar etc.) também "modificarão" AB. Isso não é necessariamente ruim (na verdade, pode ser muito útil: a AB nunca precisa ser atualizada explicitamente para se manter sincronizada com A e B), mas é certamente um comportamento que você deve estar ciente. Exceção importante: redimensionar A e / ou B para sth maior pode levar a que eles sejam realocados na memória (para a necessidade de espaço contíguo) e isso, por sua vez, invalidaria AB.
  • Como todo acesso a um elemento é precedido por um teste (ou seja, "i <v1.size ()"), o tempo de acesso ao VecProxy, embora constante, também é um pouco mais lento que o dos vetores.
  • Essa abordagem pode ser generalizada para n vetores. Eu não tentei, mas não deve ser grande coisa.
Ronald Souza
fonte
2

Mais uma variante simples que ainda não foi mencionada:

copy(A.begin(),A.end(),std::back_inserter(AB));
copy(B.begin(),B.end(),std::back_inserter(AB));

E usando o algoritmo de mesclagem:

#include <algorithm> #include <vector> #include <iterator> #include <iostream> #include <sstream> #include <string> template<template<typename, typename...> class Container, class T> std::string toString(const Container<T>& v) { std::stringstream ss; std::copy(v.begin(), v.end(), std::ostream_iterator<T>(ss, "")); return ss.str(); }; int main() { std::vector<int> A(10); std::vector<int> B(5); //zero filled std::vector<int> AB(15); std::for_each(A.begin(), A.end(), [](int& f)->void { f = rand() % 100; }); std::cout << "before merge: " << toString(A) << "\n"; std::cout << "before merge: " << toString(B) << "\n"; merge(B.begin(),B.end(), begin(A), end(A), AB.begin(), [](int&,int&)->bool {}); std::cout << "after merge: " << toString(AB) << "\n"; return 1; }

D. Alex
fonte
-1

Se seus vetores forem classificados *, verifique set_union em <algorithm>.

set_union(A.begin(), A.end(), B.begin(), B.end(), AB.begin());

Há um exemplo mais completo no link

* obrigado rlbond

Roda dentada
fonte
4
Além disso, ele não faz o mesmo que um acréscimo direto - os elementos no intervalo de saída são únicos, o que pode não ser o que o OP queria (eles podem até não ser comparáveis). Certamente não é a maneira mais eficiente de fazê-lo.
Peter
-1

Todas as soluções estão corretas, mas achei mais fácil escrever uma função para implementar isso. como isso:

template <class T1, class T2>
void ContainerInsert(T1 t1, T2 t2)
{
    t1->insert(t1->end(), t2->begin(), t2->end());
}

Dessa forma, você pode evitar o posicionamento temporário como este:

ContainerInsert(vec, GetSomeVector());
user3360767
fonte