C++ Sorted Set of Objects

user_9665681 0
Viewed 3219

I am using std::set<T> where T is my own class. Is there a way to have a set that is always sorted by property A of my class and still keep all elements inside unique in terms of property B in my class.

class T
{
public:
    int A;
    int B;
}

So I need my class instances to be sorted by A and unique by B. Any alternative to std::set as long as it is part from STL is also accepted.

set sorting stl algorithm c++
3 Answers

I might go with an intermediate function. The code below illustrates it. 

#include <iostream>
#include <set>

class Foo {  // Your T
public:
    int A;
    int B;
    Foo(int a, int b) : A(a), B(b) { }
};

template <typename T, typename Comparison>
void addToSet(std::set<T, Comparison>& s, Foo item)
{
    for (auto i : s) {
        if (i.B == item.B) {
            // Do whatever you need here, currently item is not added.
            return;
        }
    }
    s.insert(item);
}

int main()
{
    auto comp = [](Foo a, Foo b) { return a.A < b.A; };
    std::set<Foo, decltype(comp)> sortedSet(comp);

    auto quickAdd = [&sortedSet](Foo item) mutable { addToSet(sortedSet, item); };

    quickAdd(Foo(1, 2));
    quickAdd(Foo(5, 2));  // Shouldn't be seen
    quickAdd(Foo(5, 5));

    for (auto i : sortedSet)
        std::cout << "A: " << i.A << ", B: " << i.B << '\n';
}

This outputs

A: 1, B: 2
A: 5, B: 5

Which should fit your criteria.

Some notes, I hardcoded the Foo type into the addToSet function because of the specific requirement about not adding items with matching B keys. The quickAdd lambda in main is just so I don't have to always type sortedSet as the first parameter. You can naturally modify the comp function to get whatever behavior you want like sorting matching A keys by the B key, or A keys from high to low.

user_61195820 
class Foo {  // Your T
public:
int A;
int B;
Foo(int a, int b) : A(a), B(b) { }
bool operator==(Foo&& other){
  return B == other.B;
}
};

auto comp = [](Foo a, Foo b) { return a.A < b.A; };
std::set<Foo, decltype(comp)> sortedSet(comp);

sortedSet.insert({1, 2});
sortedSet.insert({5, 2});  // Shouldn't be seen
sortedSet.insert({5, 5});

std::cout <<std::endl;
for (auto i : sortedSet)
    std::cout << "A: " << i.A << ", B: " << i.B << '\n';

It should work.

user_165727120

Just sort by both properties, with property A having a larger priority than property B.

class T
{
public:
   int A;
   int B;
   bool operator < (T other) const
   {
       return (A<other.A) || ((A == other.A) && (B < other.B));
   }
}

It is difficult to ensure uniqueness without sorting by both parameters. Other method, is usage of a hash function on property B and it should be a faster method but it is probably complicated to implement correctly. Since to achieve suitable efficiency you'll need to implement your own container - you could write a wrapper around std::map<propertyA, std::unordered_map<propertyB, remaining_data>> to achieve interface of a set but I doubt that it will be more efficient than a straightforward std::set.

user_108036710
Related