1

我正在寻找根据两个排序参数中的位置从大型集合中提取对象的最佳方法。

例子:

struct Object{
    Time start;
    Time end;
    //... data
};

现在,任何时候t我都想快速找到在这段时间内“存在”的所有对象,即t在对象startend值之间。

我想到的方法是使用:

std::multimap<Time, object*> objectsOrderedByStart;
std::multimap<Time, object*> objectsOrderedByEnd;

multimap因为可能有许多具有相同Time值的对象,它们是排序的键)

每次我创建一个时,Object我都会将它添加到每个multimap对象中,它会自动将对象放置在一个排序列表startend

然后,我通过查找wheret中的所有对象和whereobjectsOrderedByStart中的对象来“查询”我的有效对象的时间,然后只获取两个结果集中的对象。但这似乎效率低下,我能想到的唯一找到联合的技术是逐个检查一个结果集并查看该对象是否在另一个结果集中。t>TimeobjectsOrderedByEndt<End

但是我怀疑这不是最有效的方法。我可以通过在迭代 each 时跳过元素来进行迭代multimap,而不是逐个迭代,然后如果我走得太远,然后从最后一个跳过点开始逐个迭代。或者,我可以只保留一个multimap,然后在每个内部object查看它的end时间。

但我怀疑有更好的方法来组织这些数据并找到我感兴趣的范围内的数据?

4

2 回答 2

0

您可以使用两个手动排序的数组而不是两个多图,然后使用std::lower_boundandstd::upper_bound或手动编码的二进制搜索来搜索它们。

于 2013-06-18T09:59:19.577 回答
0

我认为你应该看看Boost.ICL

于 2013-06-18T10:11:15.763 回答