小编Par*_*esh的帖子

我有一个集合std::set.我希望以最快的方式找到此集合中所有集合的交集.集合中的集合数量通常非常小(~5-10),每个集合中的元素数量通常小于1000,但偶尔可以达到10000左右.但我需要做几十个交叉点成千上万的时间,尽可能快.我试着对几个方法进行基准测试,如下所示:

1. std::set最初复制第一组的对象中的就地交叉.然后对于后续集合,它遍历其自身的所有元素和集合的第i组,并根据需要从其自身中移除项目.
2. 使用std::set_intersection临时std::set,将内容交换到当前集,然后再次找到当前集与下一集的交集并插入临时集,依此类推.
3. 手动迭代所有集合中的所有元素,如1),但使用a vector作为目标容器而不是std::set.
4. 与4相同,但使用a std::list而不是a vector,怀疑a list将提供从中间更快的删除.
5. 使用散列集(std::unordered_set)并检查所有集合中的所有项目.

事实证明,vector当每组中的元素数量较少时,使用a 略微更快,而list对于较大的集合,使用a 略微更快.就地使用set比两者都慢得多,其次是set_intersection哈希集.是否有更快的算法/数据结构/技巧来实现这一目标？如果需要,我可以发布代码片段.谢谢!

我正在寻找Java中的快速平方根实现,用于输入范围为[0,2*10 ^ 12]的双值.对于此范围内的任何值,精度应小于5位小数.换句话说,结果可能与Math.sqrt()小数点后5位的方法不同.但是,这种方法需要比它快得多Math.sqrt().

有任何想法吗？谢谢!

我打算在C++中使用两个类型的地图:std::map<char, Node>,其中Node是一个自定义类.假设我有两个地图,m1并且m2上面的类型,我想知道是否m1包含所有键m2.换句话说,我想验证m1和的键集的交集是否与键m2的集合相同m2.

我可以遍历所有键m2并执行find()或者count()执行m1,但这看起来像是浪费,可能会很慢.我这样说是因为密钥以排序顺序存储为二进制搜索树std::map,因此每个查找/计数将采用O(logn),而对于下一个密钥m2,密钥中的相同路径m1将必须从一开始就被遍历.

我是STL的新手,所以请原谅我对一些应该很容易实现的东西的无知.此外,一些简单的示例代码片段或代码片段链接将非常有助于更好地理解.我不能使用非标准库,包括boost.

提前致谢!

我有一个类,并且指向这个类的对象的指针需要放在一个std::set.我想要定义的比较里面的类.我已经看到了一些解决方案,其中定义了一个单独的类(我猜它被称为仿函数),或者定义了一个重载的结构operator().我想避免使用这个样板代码,并希望将比较器定义为类本身的成员,这与Java的compareTo()方法类似.

让我们说,我的班级是这样的:

class Item {
private:
    int id;
    float score;
.....
public:
// Rest of the methods and setters/getters
}

我想以一种方式定义比较器,指向具有较高分数的对象的指针首先放在集合中.如果两者的分数相等,则首先放置具有较低id的分数.我想代码将类似于以下内容,但由于我不太了解这一部分,请纠正我(我希望将其放在类本身内):

bool operator()(const Item* a, const Item* b) {
    if (a->score != b->score) return a->score > b->score;
    return a->id < b->id;
}

用法如下:

std::set<Item*> sortedItems;
Item* item = new Item();
sortedItems.insert(item);

std::set如果在类中定义,我不确定是否需要在模板中指定比较器,如果是,如何？另外,如何在类本身中添加此比较器？我是STL的新手,也是C++的新手.谢谢!