How to sort pointer in stl set?

Question

In c++, set can sort value automatically, so i just need to insert them.

for a self-defined struct, i only need to define operator > and <, like this:

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

struct A { 
  A(int a) : a_(a) {}
  friend bool operator <(const A& shot1, const A& shot2) {
    return shot1.a_ < shot2.a_;
  }
  friend bool operator >(const A& shot1, const A& shot2) {
    return shot1.a_ > shot2.a_;
  }
  int a_; 
};

int main(int argc, char** argv) {
  std::set<A> s;
  A a1(10), a2(11), a3(9);
  s.insert(a1);
  s.insert(a2);
  s.insert(a3);
  for (auto i : s) {
    cout << i.a_ << endl;  // 9, 10, 11, it's sorted.
  }
}

this can work, but when i have a self-defined struct, which is very heavy, so the copy constructor will be expensive. i want to make set save pointer like this:

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

struct A {   // NOTICE HERE: A's contructor is very heavy
  A(int a) : a_(a) {}
  friend bool operator <(const A& shot1, const A& shot2) {
    return shot1.a_ < shot2.a_;
  }
  friend bool operator >(const A& shot1, const A& shot2) {
    return shot1.a_ > shot2.a_;
  }
  int a_; 
};

int main(int argc, char** argv) {
  std::set<A*> s;
  A a1(10), a2(11), a3(9);
  s.insert(&a1);
  s.insert(&a2);
  s.insert(&a3);
  for (auto i : s) {
    cout << i->a_ << endl;  // 10, 11, 9, not sorted!!!!!!!
  }
}

but i think the set sort function failed, so, how can i make it work when set value is pointer?

Adrian Maire · Answer 1 · 2021-05-22T12:42:26.833

The set is not any-more of object A, but of pointer: A*. Because of this, the default ordering for the set is performed on the conversion of pointer to integer, it is ordering it position on memory. To avoid this, a custom comparison operator is required, which bypass to the required ordering of instances.

You can define your own comparison function like in the example below.

The idea is to create a functor: a structure that has an operator parenthesis and implement a comparison (less than) between the required objects:

bool operator()(Obj a, Obj b); //Less comparison.

Then, the class can be used in the template of the set:

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

struct A {   // NOTICE HERE: A's contructor is very heavy
  A(int a) : a_(a) {}
  friend bool operator <(const A& shot1, const A& shot2) {
    return shot1.a_ < shot2.a_;
  }
  friend bool operator >(const A& shot1, const A& shot2) {
    return shot1.a_ > shot2.a_;
  }
  int a_; 
};

struct Comp
{
    bool operator()(const A* a, const A* b)
    {
        if (a && b)
        {
            return *a < *b;
        }
        return a<b;
    }
};

int main(int argc, char** argv) {
  std::set<A*, Comp> s;
  A a1(10), a2(11), a3(9);
  s.insert(&a1);
  s.insert(&a2);
  s.insert(&a3);
  for (auto i : s) {
    cout << i->a_ << endl;  // 10, 11, 9, not sorted!!!!!!!
  }
}

For more information about how to create custom comparators for a set:

Using custom std::set comparator

How to sort pointer in stl set?

1 Answers1