c++ - 如何仅使用第二个值从集合中查找对？

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++标准库却不支持的原因。