c++ - 比较它们之间的元素，得到共同值的键

Question

我在两个不同的集合中有成对的数据、键和值。我需要比较两个集合的值，并创建一个集合，其中包含值相等的键对。

例如，使用以下数据集:

      Vals
Key Col1 Col2
1    4     5
2    6     9
4    8     4
6    10    10

常用值是 4 和 10。所以他的想法是得到一个包含对的新集合，在本例中是 (key col1, key col2) {{1, 4}, {6, 6}}

我需要一种最快的方法来做到这一点，每个集合都可以轻松拥有 100k 的数据，并且使用 for 循环迭代太慢，我尝试使用 vector。

两个集合不一定具有相同的键(如 map)，并且数据可以是除 int 之外的其他东西(我使用二进制数据，通常键是 int(unsinged long)。

这是我的示例代码(非常非常慢的代码):

struct p {
    unsigned long int p1;
    unsigned long int p2;
};

vector<int> table1 = tables1(n); /* bigger n -> more samples */
vector<int> table2 = tables2(n); /* n = 10000 generate 150k per table */

vector<p> common;

for (unsigned long int i = 0;i < table1.size(); i++) {
    for (unsigned long int j = 0; j < table2.size(); j++) {
        if (table1[i] == table2[j]) {common.push_back ({i, j};}
    }
}

有没有办法使用 map、set 或其他方法更快地完成此操作？ (我从 C++ 开始)

Answer 1

实际上，您比较了它们之间的所有值，并想知道每个集合中该值的键。

在这种情况下，我建议简单地反转每个映射中的键和值。这将导致以下结构:

      Vals
RevKey1 RevVal1 RevKey2 RevVal2
4       1         5     1
6       2         9     2
8       4         4     4
10      6        10     6

然后您只需遍历第一个映射，并在第二个映射中查找相同的键:

map<int,int> col1;
map<int,int> col2;
map<int,pair<int,int>> common ; 
...
for (auto& x: col1) {
    auto y= col2.find(x.first); 
    if (y!=col2.end()) 
        common[x.first]=make_pair(x.second,y->second);
}
cout<<"Result:"<<endl;
for (auto& x:common ) 
    cout << x.first << "<-" << x.second.first << " in col1 and " <<x.second.second << " in col2"<<endl;

Online demo

备注:我让你作为一个练习来反转现有映射中表示的映射关系。我还允许您扩展此算法以处理多重映射，以防多个键具有相同的值。