c++ - 使用 std::set 和多重比较条件的容器

Question

我正在尝试编写一个由两个 std::set 组成的容器，这些容器具有使用不同比较器类的相同元素。这是我的看法，经过简化:

struct Element
{
    // foo and bar are immutable to prevent messing set order up.
    FooStruct const foo;
    BarStruct const bar;
    int someVar;

    Element(FooStruct foo);
    Element(BarStruct bar);
};

class CriterionFoo
{
    // Sorts according to member foo.
    bool operator()(Element* const& arg0, Element* const& arg1);
};

class CriterionBar
{
    // Sorts according to member bar.
    bool operator()(Element* const& arg0, Element* const& arg1);
};

class ElementContainer
{
    typedef std::set<Element*, CriterionFoo> FooSortedSet;
    typedef std::set<Element*, CriterionBar> BarSortedSet;

    FooSortedSet fooSortedSet;
    BarSortedSet barSortedSet;

    // fooSortedSet.find(&Element(myFoo))
    Element* findElement(FooStruct myFoo);
    // barSortedSet.find(&Element(myBar))
    Element* findElement(BarStruct myBar);

    // Inserts in both sets.
    void insert(Element* element);

    // Enter total alienation and existential crisis...
    void erase(BarStruct myBar);
    void erase(FooStruct myFoo);
};

我想要实现的只是制作一个集合包装器，它可以在 log(n) 复杂性中找到具有两个不同搜索条件的成员。 ElementContainer::erase 方法可以很容易地找到 [Foo|Bar]SortedSet::iterator 的任一标准，但无论如何我都必须天真地遍历另一个(它几乎胜过整点)。再一次，我可以将 [Foo|Bar]SortedSet::const_iterator 引用放在 Element 结构中，并通过一个步骤到达另一个集合中的相应迭代器，但这感觉就像矫枉过正。

现在好了，我不可能是第一个遇到这种情况的人。是否有任何既定的方法可以使用多个标准来保持一组易于导航的元素？尤其是在不过度设计的情况下？

Answer 1

首先，您需要异构查找:能够找到具有给定 BarStruct 值 myBar 的 Element 而没有 必须构造一个虚拟 Element(myBar)。这可以通过将以下 operator() 重载添加到 CriterionBar(和等效的 CriterionFoo)来实现:

bool operator()(Element* const& lhs, BarStruct const& rhs) const;
bool operator()(BarStruct const& lhs, Element* const& rhs) const;

注意:您的比较运算符必须是 const 成员函数!

此外，你need to add is_transparent 使集合考虑这些额外的比较选项(并将相应的重载添加到例如 find)。例如:

using is_transparent = void;

这不是绝对必要的，但比您当前正在做的虚拟 Element 事情要好得多。

在两个 O(log(N)) 操作中从两个集合中删除的实际步骤很简单:

void erase(FooStruct myFoo)
{
  auto fooIt = fooSortedSet.find(myFoo);
  Element* elementToErase = *fooIt;
  auto barIt = barSortedSet.find(elementToErase);

  fooSortedSet.erase(fooIt);
  barSortedSet.erase(barIt);
}