如何仅使用第二个值从集合中找到一对？

Question

我只想使用第二个元素来查找一对，第一个元素可以是任何东西，而且所有第二个元素都是唯一的。

使用std::find_if的代码，但这需要线性时间

set<pair<int,int> > s;

s.insert(make_pair(3,1));
s.insert(make_pair(1,0));

auto it = find_if(s.begin(),s.end(),[value](const pair<int,int>& p ){ return p.second == value; });

if(it==s.end()) 
    s.insert(make_pair(1,value));
else {
    int v = it->first;
    s.erase(it);
    s.insert(make_pair(v+1,value));
}

我想使用set的std::find函数，以便花费对数时间。

Answer 1

没有任何数据结构可以完全满足您的要求。

但是数据库做类似的事情。他们称它为Index Skip Scanning。要实现相同而无需从头开始，您可以从对中的第一个对象到对中第二个对象的std::map来实现一个std::map。现在，单对查询在时间上是对数的，具有给定第一个条目的事物的查找在时间上也是对数的（尽管迭代这些事物的速度可能较慢），而在第二个条目的事物的查找是线性的您拥有的第一个值的数量乘以您拥有的第二个值的数量的对数。

请注意，仅当您有非常多的配对时，并且配对中第一个条目的值相对较少时，才值得这样做。而且，您一直在不断更改数据（因此，维护多个索引会增加很多开销），并且很少会查找该对中的第二个值。打破这些假设中的任何一个，开销都不值得。

这是要满足的一组相当具体的假设。对于数据库而言，它比C ++程序员更常见。这就是为什么大多数数据库都支持该操作，而C ++标准库却不支持的原因。