c++ - Set vs. Multiset

Question

I'd like to store (about 100 to 1000) different relations of type <Object A, Relation R, Object B> in a set or multiset. I'd like to be able to search for A and (A,R), but not for (A,R,B) (and there will be only a few (<5) relations with the same A and R, so linear search if fine then).

Is it better to store the relations in a set (ordered by A, R and B) or to store them in a multiset ordered by A and R?

Edit: I've looked into hash tables, but their iteration isn't as fast as (ordered) set iteration, and the pattern matching requires a lot of iteration too. (It will have to search once to find the start of the iteration and then iterate until all relations with the same object A are done.)

Thanks, Ragnar

Answer 1

从我收集的评论中，您必须查找完全匹配的 A 或 (A, R) 对。

如果这是正确的，您可以做的最好的事情是使用两个哈希表：一个以 A 作为键，另一个以 (A, R) 作为键。关系本身可以存储在未排序的向量中，并将它们的索引插入到两个哈希表中。这是您为查找任务获得 O(1) 复杂性的唯一方法。

拥有两个独立的索引结构对性能至关重要：如果仅使用 A 作为键，则在查找 (A, R) 对时，您将获得必须搜索合适 R 的对象列表。在相反的情况下，如果您只有 (A, R) 键，您将无法在 O(1) 时间内仅查找某个 A。