C++ Sorted Set of Objects

Question

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.

@Jeffrey You are correct. As for you question, if i have elemetn A=4 and B=2 already inserted, if I try to add A=3 B=2 it should not be added. But also I will never pass such input. — Kaloyan Manev, Oct 22 '19 at 21:12
Do your care if 2,3 sorts ahead of 2,4 or must 2,4 be first if added first (or some other logic)? — user4581301, Oct 22 '19 at 21:15
Rethought what I was going to suggest. I don't think `set`, or at least not `set` alone, is the right tool. — user4581301, Oct 22 '19 at 21:26
@user4581301 Basically I need uniqe priority queue. But how? — Kaloyan Manev, Oct 22 '19 at 21:33

sweenish · Answer 1 · 2019-10-22T21:30:30.913

0

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.

edited Oct 22 '19 at 21:30

answered Oct 22 '19 at 21:25

sweenish

4,793
3
12
23

Can we have something more efficient in addToSet insted of looping trough all the items in the set? – Kaloyan Manev Oct 22 '19 at 21:30
I doubt it. It's the only way to validate unique B keys that I can currently think of while keeping a `std::set`. You could maybe overload the `==` and then use a `std::priority_queue`. – sweenish Oct 22 '19 at 21:36
@KaloyanManev that's what I was trying to figure out when I abandoned my answer as unworkable. If you have a `set` (for quick rejection) and an ordered list wrapped up together in another class (Bonus points for making it behave like a [Library Container](https://stackoverflow.com/questions/7758580/writing-your-own-stl-container)) you get the best of both worlds at a cost in storage. – user4581301 Oct 22 '19 at 21:37
@user4581301 won't this duplicate my data? – Kaloyan Manev Oct 22 '19 at 21:40
@KaloyanManev that's the cost in storage. One could store a reference to the other, but a pointer is usually as or more heavy that an `int` and the added cost of pointer-chasing makes the list of pointers not worthwhile. – user4581301 Oct 22 '19 at 21:40
@user4581301 Before asking the question I tried holding all my data in a priority queue and using an extra set to check if i already have inserted the element but that required too much memory :/ – Kaloyan Manev Oct 22 '19 at 21:43
After a quick look, I don't like the `priority_queue` for this. Seems like you'll have to eat a cost somewhere, whether it's storage or O(n) + O(lg n) to add to the set. Are you able to sanitize the data ahead of time? That would eliminate the need for the extra requirement regarding the B key. – sweenish Oct 22 '19 at 21:48
@KaloyanManev that's what I figured. Option 3: is you write your own structure that does exactly what you want in O(n) space complexity and at worst O(N) time. I don't think that can be done, though. You have a set of data that has two different ordering requirements. One actually is for ordering and the other is you need ordering of some sort to get the predictability required for high speed look-up. You probably can't do both at the same time, so usually this means one is easy and the other is hard. You have to decide if you look up or add more frequently and cut your losses. – user4581301 Oct 22 '19 at 22:51

score 0 · Answer 2 · edited Aug 02 '21 at 11:05

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.

score -1 · Answer 3 · answered Oct 22 '19 at 22:24

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.

C++ Sorted Set of Objects

3 Answers3