CODEWITHSUNDEEP
c++data-structuresstl
corsel
corsel

Reputation: 325

Container Using std::set with Multiple Compare Criteria

I'm trying to write a container comprising of two std::sets with identical elements using different comparator classes. Here's my take, simplified:

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);
};

All I wanted to achieve was to make a set wrapper that finds in log(n) complexity a member with two different search criteria. ElementContainer::erase method can easily find the [Foo|Bar]SortedSet::iterator for either criterion, but I'll have to traverse the other one naïvely anyway (which pretty much beats the whole point). Then again, I can put [Foo|Bar]SortedSet::const_iterator references inside Element struct and reach the corresponding iterator in the other set with a single step, but this feels like an overkill.

OK now, I can't possibly be the first person to ever encounter this. Is there any established way of keeping a set of elements with easy navigation using more than a single criteria? Particularly without going on an over-engineering frenzy?

Upvotes: 1

Views: 589

Answers (1)

Max Langhof
Max Langhof

Reputation: 23711

First, you want heterogeneous lookup: The ability to find the Element with a given BarStruct value myBar without having to construct a dummy Element(myBar). This can be achieved by adding the following operator() overloads to CriterionBar (and equivalently CriterionFoo):

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

Note: Your comparison operators must be const member functions!

Further, you need to add an is_transparent to make the set consider these additional comparison options (and add the corresponding overloads to e.g. find). For example:

using is_transparent = void;

This is not strictly necessary, but miles better than the dummy Element thing you are doing currently.

The actual steps for deleting from both sets in two O(log(N)) operations are simple:

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

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

Upvotes: 1

Related Questions