我正在使用多步操作，并希望合并结果。例如:
std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;
我想让AB有A的内容和B的内容按照这个顺序。做这样的事情最有效的方法是什么?
当前回答
template<typename T>
vector<T> CombineVectors(vector<T> &&a, vector<T> &&b) {
vector<T> ab = move(a);
ab.insert(
ab.end(), make_move_iterator(b.begin()), make_move_iterator(b.end()));
return ab;
}
template<typename T>
vector<T> CombineVectors(const vector<T> &a, const vector<T> &b) {
vector<T> ab = a;
ab.insert(ab.end(), b.begin(), b.end());
return ab;
}
其他回答
template<typename T>
vector<T> CombineVectors(vector<T> &&a, vector<T> &&b) {
vector<T> ab = move(a);
ab.insert(
ab.end(), make_move_iterator(b.begin()), make_move_iterator(b.end()));
return ab;
}
template<typename T>
vector<T> CombineVectors(const vector<T> &a, const vector<T> &b) {
vector<T> ab = a;
ab.insert(ab.end(), b.begin(), b.end());
return 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)(常数时间)来创建它，并且使用最小的额外内存分配。
一些需要考虑的问题
You should only go for it if you really know what you're doing when dealing with references. This solution is intended for the specific purpose of the question made, for which it works pretty well. To employ it in any other context may lead to unexpected behavior if you are not sure on how references work. In this example, AB does not provide a non-const access operator ([ ]). Feel free to include it, but keep in mind: since AB contains references, to assign it values will also affect the original elements within A and/or B. Whether or not this is a desirable feature, it's an application-specific question one should carefully consider. Any changes directly made to either A or B (like assigning values, sorting, etc.) will also "modify" AB. This is not necessarily bad (actually, it can be very handy: AB does never need to be explicitly updated to keep itself synchronized to both A and B), but it's certainly a behavior one must be aware of. Important exception: to resize A and/or B to sth bigger may lead these to be reallocated in memory (for the need of contiguous space), and this would in turn invalidate AB. Because every access to an element is preceded by a test (namely, "i < v1.size()"), VecProxy access time, although constant, is also a bit slower than that of vectors. This approach can be generalized to n vectors. I haven't tried, but it shouldn't be a big deal.
如果你的向量排序*，检查set_union从<algorithm>。
set_union(A.begin(), A.end(), B.begin(), B.end(), AB.begin());
链接中有一个更详细的例子。
还有一个没有提到的简单变体:
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;
}
AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );
