[c++] 두 벡터를 연결하는 가장 좋은 방법은 무엇입니까?

멀티 트 레딩을 사용하고 결과를 병합하려고합니다. 예를 들면 다음과 같습니다.

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

AB가 A의 내용과 B의 내용을 순서대로 갖기를 원합니다. 이와 같은 작업을 수행하는 가장 효율적인 방법은 무엇입니까?



답변

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );


답변

이것이 정확히 멤버 함수의 기능 std::vector::insert입니다

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());


답변

실제로 두 벡터를 실제로 연결해야하는지 또는 반복을 위해 연결 모양을 제공 하려는지에 따라 다릅니다. 부스트 :: 결합 기능

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

당신에게 이것을 줄 것입니다.

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

너에게 줄거야

1
2
3
4
5
6

참고 boost :: join은 두 벡터를 새 컨테이너에 복사하지 않지만 두 컨테이너의 범위를 포함하는 한 쌍의 반복자 (범위)를 생성합니다. 약간의 성능 오버 헤드가 있지만 모든 데이터를 새 컨테이너에 먼저 복사하는 것보다 적을 수 있습니다.


답변

Kiril V. Lyadvinsky의 답변을 바탕으로 새 버전을 만들었습니다. 이 스 니펫은 템플릿 및 과부하를 사용합니다. 그것으로, 당신은 쓸 수 vector3 = vector1 + vector2vector4 += vector3. 그것이 도움이되기를 바랍니다.

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
}


답변

Bradgonesurfing의 대답의 방향으로, 많은 경우 실제로 두 벡터 (O (n))를 연결할 필요 가 없지만 대신 연결된 것처럼 (O (1)) 작동 합니다. 이 경우 Boost 라이브러리가 없어도 가능합니다.

트릭은 벡터 프록시를 만드는 것입니다 : 참조 를 조작하는 래퍼 클래스 는 두 개의 벡터에 를 외부에서 하나의 연속 된 것으로 간주하여 합니다.

용법

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

이행

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

주요 혜택

그것을 만드는 데는 O (1) (일정 시간)이며 최소한의 추가 메모리 할당이 있습니다.

고려해야 할 몇 가지

  • 당신이 참조를 다룰 때 무엇을하고 있는지 정말로 아는 경우에만 사용해야한다 . 이 솔루션은 질문의 특정 목적을 위해 고안된 것으로, 잘 작동합니다 . 참조가 어떻게 작동하는지 확실하지 않은 경우 다른 컨텍스트에서 사용하면 예기치 않은 동작이 발생할 수 있습니다.
  • 이 예에서, AB는 수행 하지 비 const 액세스 연산자 ([])를 제공 . AB는 참조를 포함하므로 값을 지정하면 A 및 / 또는 B 내의 원래 요소에도 영향을 미칩니다. 이것이 바람직한 기능인지 여부에 관계없이 응용 프로그램 관련 질문입니다. 신중하게 고려하십시오.
  • 값 할당, 정렬 등과 ​​같이 A 또는 B에 직접 변경 한 내용도 AB를 “수정”합니다. 이것은 반드시 나쁘지는 않지만 (실제로는 매우 편리 할 수 ​​있습니다. AB는 A와 B 둘 다에 동기화되도록 명시 적으로 업데이트 할 필요가 없습니다.) 그러나 반드시 알아야 할 동작입니다. 중요한 예외 : A 및 / 또는 B의 크기를 sth로 더 크게 조정 하면 연속 된 공간이 필요한 경우 메모리에 다시 할당되어 AB가 무효화 될 수 있습니다.
  • 요소에 대한 모든 액세스 앞에 테스트 (즉, “i <v1.size ()”)가 있기 때문에 VecProxy 액세스 시간은 일정하지만 벡터의 액세스 시간보다 약간 느립니다.
  • 이러한 접근법은 n 개의 벡터로 일반화 될 수있다. 나는 시도하지 않았지만 큰 문제가되어서는 안됩니다.

답변

아직 언급되지 않은 또 하나의 간단한 변형 :

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

그리고 병합 알고리즘을 사용하십시오.

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


답변

벡터가 정렬 된 경우 * <algorithm>에서 set_union 을 확인하십시오 .

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

링크에 더 철저한 예가 있습니다.

* 감사합니다 rlbond