假设现在你有一组数据:
Data 1: (1, 2);
Data 2: (1, 3);
Data 3: (7, 8);
Data 4: (8, 20);
现在的任务是合并数据集,如果它与另一个数据集有共同元素。在我们的示例中,数据 1 将与数据 2 合并,因为它们共享公共数字 1。数据 3 和数据 4 也是如此。我的问题是我们如何才能在 C++ 中非常有效地实现此功能。目前我的实现是基于 std::vector > 数据结构的,如下代码所示:
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
bool find_the_element(const set<int> &mysets, const vector<int> &myvector)
{
for(int i=0; i<myvector.size(); i++)
{
set<int>::iterator it;
it = mysets.find(myvector[i]);
if (it != mysets.end())
return true;
}
return false;
}
int main ()
{
set<vector<int> > myset;
vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int> b;
b.push_back(1);
b.push_back(3);
vector<int> c;
c.push_back(7);
c.push_back(8);
vector<int> d;
d.push_back(8);
d.push_back(20);
vector<vector<int> > my_vector_array;
my_vector_array.push_back(a);
my_vector_array.push_back(b);
my_vector_array.push_back(c);
my_vector_array.push_back(d);
vector<set<int> > my_sets;
for(int i=0; i<my_vector_array.size(); i++)
{
vector<int> temp_vector = my_vector_array[i];
if (my_sets.empty())
{
set<int> temp_set;
for(int j=0; j<temp_vector.size(); j++)
temp_set.insert(temp_vector[j]);
my_sets.push_back(temp_set);
}
else
{
bool b_find = false;
for(int j=0; j<my_sets.size(); j++)
{
set<int>temp_set;
temp_set = my_sets[j];
if (find_the_element(temp_set,temp_vector))
{
b_find = true;
my_sets[j].insert(temp_vector.begin(), temp_vector.end());
break;
}
}
if (b_find)
{
// something already done
}
else
{
set<int> temp_set;
for(int j=0; j<temp_vector.size(); j++)
temp_set.insert(temp_vector[j]);
my_sets.push_back(temp_set);
}
}
}
}
我想知道 C++ 中是否有更有效的数据结构或有效的算法来完成这项工作。谢谢!