11 个解决方案
#1
补充一下，集合用数据结构VECTOR表示，且对每个集合内的元素可预先排序
#2
set
#3
用STL中的集合set
#4
但是SET只能里的元素只能是唯一的吧，我每个集合里的元素是可以重复的
#5
学习了
#6
能不能这样，先找出5个vector里最短的那个，比如A，然后遍历A的元素，用VECTOR的FIND方法依次到B,C,D,E里去找，如果在四个里面都找到了，则将该元素push到一个新的VECTOR里，只要有一个没找到，就跳出来找下一个元素？请问这样的话效率会怎么样，大概多大的数据量会导致效率非线性的下降？
#7
写了一个，但是效率不彰，运算过程中会产生临时对象
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
//重载&&运算符(需要知道的是这里重载之后&&不再进行短路求值了详见：《More Effective C++》Item M7)，还有就是传进来的参数必须是有序的
template<class T>
vector<T> operator &&(const vector<T>&v1, const vector<T>&v2)
{
vector<T> res;
if (0 == v1.size() || 0 == v2.size())
return res;
vector<T>::const_iterator f1 = v1.begin(), f2 = v2.begin();
while (f1 != v1.end() && f2 != v2.end())
{
if (*f1 < *f2)
{
++f1;
}
else if (*f1 > *f2)
{
++f2;
}
else
{
res.push_back(*f1);
++f1;
++f2;
}
}
return res;
}
int main()
{
int a[] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9};
int b[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int c[] = {0, 2, 3, 4, 5, 6, 7,};
int d[] = {0, 1, 3, 4, 5, 6, 7, 9};
int e[] = {0, 1, 2, 5, 6, 7, 8, 9};
//构造vector
vector<int> A(a, a + sizeof(a) / sizeof(a[0]));
vector<int> B(b, b + sizeof(b) / sizeof(b[0]));
vector<int> C(c, c + sizeof(c) / sizeof(c[0]));
vector<int> D(d, d + sizeof(d) / sizeof(d[0]));
vector<int> E(e, e + sizeof(e) / sizeof(e[0]));
//对vector排序
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
sort(D.begin(), D.end());
sort(E.begin(), E.end());
//求交集，因为A, B, C, D, E都是排过序的，所以任意两者之间的结果仍然是有序的
vector<int>res = A && B && C && D && E;
for (vector<int>::iterator it = res.begin(); it != res.end(); ++it)
{
cout<<*it<<' ';
}
cout<<endl;
system("pause");
return 0;
}
#8
嗯，楼上的方法也是一种思路，谢谢
#9
楼上的代码我又测试了下效率，每个容器10000个数据的时候效率还不错，谢谢
#10
这个代码主要的时间花费用在了sort排序，在我的笔记本上，当每个容器的数据量为1万时，排序需要的时间很短，2万时，需要1秒，达到3万就要2秒了，真正的&&重载执行过程基本很稳定，一直在0.04左右
#11
呵呵.
#1
补充一下，集合用数据结构VECTOR表示，且对每个集合内的元素可预先排序
#2
set
#3
用STL中的集合set
#4
但是SET只能里的元素只能是唯一的吧，我每个集合里的元素是可以重复的
#5
学习了
#6
能不能这样，先找出5个vector里最短的那个，比如A，然后遍历A的元素，用VECTOR的FIND方法依次到B,C,D,E里去找，如果在四个里面都找到了，则将该元素push到一个新的VECTOR里，只要有一个没找到，就跳出来找下一个元素？请问这样的话效率会怎么样，大概多大的数据量会导致效率非线性的下降？
#7
写了一个，但是效率不彰，运算过程中会产生临时对象
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
//重载&&运算符(需要知道的是这里重载之后&&不再进行短路求值了详见：《More Effective C++》Item M7)，还有就是传进来的参数必须是有序的
template<class T>
vector<T> operator &&(const vector<T>&v1, const vector<T>&v2)
{
vector<T> res;
if (0 == v1.size() || 0 == v2.size())
return res;
vector<T>::const_iterator f1 = v1.begin(), f2 = v2.begin();
while (f1 != v1.end() && f2 != v2.end())
{
if (*f1 < *f2)
{
++f1;
}
else if (*f1 > *f2)
{
++f2;
}
else
{
res.push_back(*f1);
++f1;
++f2;
}
}
return res;
}
int main()
{
int a[] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9};
int b[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int c[] = {0, 2, 3, 4, 5, 6, 7,};
int d[] = {0, 1, 3, 4, 5, 6, 7, 9};
int e[] = {0, 1, 2, 5, 6, 7, 8, 9};
//构造vector
vector<int> A(a, a + sizeof(a) / sizeof(a[0]));
vector<int> B(b, b + sizeof(b) / sizeof(b[0]));
vector<int> C(c, c + sizeof(c) / sizeof(c[0]));
vector<int> D(d, d + sizeof(d) / sizeof(d[0]));
vector<int> E(e, e + sizeof(e) / sizeof(e[0]));
//对vector排序
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
sort(D.begin(), D.end());
sort(E.begin(), E.end());
//求交集，因为A, B, C, D, E都是排过序的，所以任意两者之间的结果仍然是有序的
vector<int>res = A && B && C && D && E;
for (vector<int>::iterator it = res.begin(); it != res.end(); ++it)
{
cout<<*it<<' ';
}
cout<<endl;
system("pause");
return 0;
}
#8
嗯，楼上的方法也是一种思路，谢谢
#9
楼上的代码我又测试了下效率，每个容器10000个数据的时候效率还不错，谢谢
#10
这个代码主要的时间花费用在了sort排序，在我的笔记本上，当每个容器的数据量为1万时，排序需要的时间很短，2万时，需要1秒，达到3万就要2秒了，真正的&&重载执行过程基本很稳定，一直在0.04左右
#11
呵呵.