0

我一直在思考一个数据结构问题，但似乎无法想出一个好的解决方案。我无法摆脱解决方案很简单的感觉，但是我只是没有看到它，所以希望你们能提供帮助！

这是问题所在：我在内存中有大量对象。它们中的每一个都有许多数据字段。某些数据字段（例如 ID）对于每个对象都是唯一的，但其他数据字段（例如名称）可以出现在多个对象中。

class Object {
    size_t id;
    std::string name;
    Histogram histogram;
    Type type;
    ...
};

我需要以一种允许我快速（即使对象的数量相对较大，即数百万）过滤集合的方式来组织这些对象，给定任意数量的对象成员的规范，而所有未指定的成员计数作为通配符。例如，如果我指定一个给定的name，我想检索其名称成员等于给定名称的所有对象。但是，如果我随后将直方图添加到查询中，我希望查询仅返回在 thename和histogram字段中都匹配的对象，依此类推。所以，例如，我想要一个函数

std::set<Object*> retrieve(size_t, std::string, Histogram, Type)

两者都可以

retrieve(42, WILDCARD, WILDCARD, WILDCARD)

也

retrieve(42, WILDCARD, WILDCARD, Type_foo)

第二个调用将返回与第一个调用更少或相同数量的对象。哪种数据结构允许这样的查询，并且可以在合理的时间内构造和查询数百万的对象？

谢谢您的帮助！

4

1 回答 1

0

首先，您可以使用Boost Multi-index对Object. 这可能有助于限制要考虑的元素数量。作为第二步，您可以简单地使用 lambda 表达式来实现谓词std::find_if以获取第一个元素或使用std::copy_if将所有元素复制到目标序列。如果您决定使用 boost，您可以使用 Boost Range 和过滤。

于 2013-06-21T07:30:42.363 回答