¿Cuál es la mejor manera de concatenar dos vectores?

190

Estoy usando multihilo y quiero fusionar los resultados. Por ejemplo:

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

Quiero que AB tenga los contenidos de A y los contenidos de B en ese orden. ¿Cuál es la forma más eficiente de hacer algo como esto?

jmasterx
fuente
1
Si busca eficiencia cuando trabaja con contenedores de gran tamaño, puede ser más eficiente usar list, donde puede empalmar uno con el otro con varias operaciones de puntero. Pero la lista tiene sobrecarga de espacio (considere usar una lista enlazada única).
Kemin Zhou

Respuestas:

323
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
fuente
66
¡Gracias! No habría pensado en la reserva.
jmasterx
10
debería copiar cada elemento, por lo que es O (n)
Kirill V. Lyadvinsky
1
No estoy seguro de si hacer una nueva pregunta o no, pero ¿se puede mejorar esta respuesta al tener en cuenta la semántica de movimiento? ¿Hay alguna forma en que pueda esperar / instruir al compilador que haga un solo movimiento de memoria en lugar de recorrer todos los elementos?
Broes De Cat
2
@boycy No. Se amortiza el tiempo constante para retroceder un elemento. Hacer retroceder n elementos es O (n)
Konrad Lindenbach
1
@ Konrad No implicaba lo contrario, pero gracias por la aclaración. Tenga en cuenta que la complejidad de una operación de inserción nunca se da en términos del número de elementos que se insertan, lo que siempre dará O (n), sino en términos del número de elementos que ya están en el contenedor, ya que eso proporciona una medida de su escalabilidad .
boycy
65

Esto es precisamente lo que la función miembro std::vector::insertes para

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
Shirik
fuente
44
@ Nick: lento en comparación con qué?
GManNickG
2
¿Tal vez que verifica si hay suficiente espacio en cada inserción de elemento? Usar la reserva de antemano lo acelerará.
RvdK
10
@ Nick: No me sorprendería si todas las implementaciones modernas de stdlib se especializaran inserten iteradores de acceso aleatorio y se reservaran por adelantado.
GManNickG
1
@Gman: Ese es un punto justo ya que sabemos que la fuente también es un vector (donde el iterador distancetiene una complejidad O (1)). Aún así, las garantías de rendimiento insertson algo a tener en cuenta cuando a menudo se puede mejorar planificando con anticipación.
Nick Bastin
2
@RvdK buscando espacio es solo unas pocas instrucciones: capacidad de carga, comparación con el tamaño, salto condicional; todo lo cual es un costo insignificante para la mayoría de los casos. Dado que la size < capacitymayoría de las veces, la predicción de ramificación probablemente hará que las instrucciones de la ramificación no reasignadas se encuentren en la tubería de instrucciones, minimizando la latencia inducida por ramificaciones, excepto para un recuento de iteraciones bajo. Esto supone una buena implementación de vectores, además de la canalización de instrucciones de la CPU y la predicción de ramificaciones [buenas], pero esas son suposiciones bastante confiables para una cadena de herramientas moderna y una máquina de escritorio. Sin embargo, no sé acerca de los teléfonos inteligentes ..
boycy
27

Depende de si realmente necesita concatenar físicamente los dos vectores o si desea dar la apariencia de concatenación en aras de la iteración. La función boost :: join

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

te dará esto

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;
}

debería darte

1
2
3
4
5
6

Tenga en cuenta boost :: join no copia los dos vectores en un nuevo contenedor, sino que genera un par de iteradores (rango) que cubren el lapso de ambos contenedores. Habrá algo de sobrecarga de rendimiento, pero tal vez menos que copiar todos los datos a un nuevo contenedor primero.

bradgonesurfing
fuente
1
Buena idea. Después de pensar por un tiempo, me di cuenta de que este objetivo también se puede lograr sin usar bibliotecas de impulso. He publicado una respuesta explicando cómo.
Ronald Souza
11

Basado en la respuesta de Kiril V. Lyadvinsky , hice una nueva versión. Este fragmento utiliza la plantilla y la sobrecarga. Con ella, puedes escribir vector3 = vector1 + vector2y vector4 += vector3. Espero que pueda ayudar.

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 se muda a codidact.com
fuente
1
¿Te refieres a agregar los elementos de cada vector entre sí? ¿O quieres anexar? Esto está claro ahora pero para los próximos 5 años ...? No debe sobrecargar el operador si el significado es ambiguo.
SR
2
@ SR me refiero a concatenar. Escribí esta respuesta hace 3 años. Todavía sé lo que significa. No hay problema ahí. Si C ++ pudiera proporcionar su propia sobrecarga, sería aún mejor. (y sí ::se toma;)
aloisdg se muda a codidact.com
Definitivamente no está claro en general que v1 + v2no represente la suma.
Apollys apoya a Monica el
@Apollys bien
aloisdg se muda a codidact.com el
La alternativa sería usar @como en F #
aloisdg se muda a codidact.com el
6

En la dirección de la respuesta de Bradgonesurfing, muchas veces uno realmente no necesita concatenar dos vectores (O (n)), sino que simplemente trabaja con ellos como si estuvieran concatenados (O (1)) . Si este es su caso, se puede hacer sin la necesidad de bibliotecas Boost.

El truco es crear un proxy vectorial: una clase de contenedor que manipula referencias a ambos vectores, vistos externamente como uno único y contiguo.

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

IMPLEMENTACIÓN

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(); };

PRINCIPALES BENEFICIOS

Es O (1) (tiempo constante) para crearlo, y con una asignación mínima de memoria adicional.

ALGUNAS COSAS A CONSIDERAR

  • Solo debe hacerlo si realmente sabe lo que está haciendo cuando se trata de referencias . Esta solución está diseñada para el propósito específico de la pregunta formulada, para lo cual funciona bastante bien . Emplearlo en cualquier otro contexto puede conducir a un comportamiento inesperado si no está seguro de cómo funcionan las referencias.
  • En este ejemplo, AB no proporciona un operador de acceso no constante ([]). Siéntase libre de incluirlo, pero tenga en cuenta: dado que AB contiene referencias, asignarle valores también afectará los elementos originales dentro de A y / o B. Si esta es una característica deseable o no, es una pregunta específica de la aplicación que uno debe Considere cuidadosamente.
  • Cualquier cambio realizado directamente en A o B (como asignar valores, ordenar, etc.) también "modificará" AB. Esto no es necesariamente malo (en realidad, puede ser muy útil: AB nunca necesita actualizarse explícitamente para mantenerse sincronizado tanto con A como con B), pero ciertamente es un comportamiento que uno debe tener en cuenta. Excepción importante: cambiar el tamaño de A y / o B a algo más grande puede hacer que estos se reasignen en la memoria (por la necesidad de un espacio contiguo), y esto a su vez invalidaría AB.
  • Como cada acceso a un elemento está precedido por una prueba (es decir, "i <v1.size ()"), el tiempo de acceso VecProxy, aunque constante, también es un poco más lento que el de los vectores.
  • Este enfoque se puede generalizar a n vectores. No lo he intentado, pero no debería ser un gran problema.
Ronald Souza
fuente
2

Una variante más simple que aún no se mencionó:

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

Y usando el algoritmo de fusión:

#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
fuente
-1

Si sus vectores están ordenados *, consulte set_union de <algorithm>.

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

Hay un ejemplo más completo en el enlace.

* gracias rlbond

Rueda dentada
fuente
44
Además, no hace lo mismo que un apéndice directo: los elementos en el rango de salida son únicos, lo que puede no ser lo que el OP quería (incluso podrían no ser comparables). Ciertamente no es la forma más eficiente de hacerlo.
Peter
-1

Todas las soluciones son correctas, pero me resultó más fácil escribir una función para implementar esto. Me gusta esto:

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

De esa manera puede evitar la colocación temporal de esta manera:

ContainerInsert(vec, GetSomeVector());
usuario3360767
fuente