How can make pointer valid in std::set?

Question

I have a self defined struct, which i overload the operator >:

struct A {
  A(int a) : a_(a) {}
  int a_;
  friend operator > (const A& a) const {
    return a_ > a.a_; 
  }
};

so i can push this struct into stl container set:

std::set<A> s;
s.insert(A(3));
s.insert(A(5));
s.insert(A(4));

but i am doing a large task, which means, copy operation is costly for me.

So, i want to build a set with element type of pointer like this:

std::set<A*>s;
A a(3); A b(5); A c(4);
s.insert(&a); s.insert(&b); s.insert(&c);

but i found it failed to keep the order, is there any methods that can keep the order by element pointer?

or, how can i save element in a ordered container, without copying and have good performance?

What kind of copy do you want to prevent? There may be better ways to do that. Note that using pointers throws your custom sorting out of the window (or at least you need even more custom sorting that will dereference the pointers). — Yksisarvinen, Mar 16 '21 at 13:23
You can use `emplace` instead of `insert` to construct the object in-place so there is no copy. — François Andrieux, Mar 16 '21 at 13:24
Sets work with `operator<`, not `operator>`. For pointers you'd need to provide a custom comparator. — interjay, Mar 16 '21 at 13:25
Are you only going to add three local variables to your set-of-pointers? This makes little sense. — n. m. could be an AI, Mar 16 '21 at 13:26
Does this answer your question? [Using custom std::set comparator](https://stackoverflow.com/questions/2620862/using-custom-stdset-comparator) — Hi - I love SO, Mar 16 '21 at 13:29
Don't do it. Think about cache locality. The additional indirection with pointers will reduce performance. Use `s.emplace(3);` instead of `s.insert(A(3));` to avoid copying/moving. — rustyx, Mar 16 '21 at 13:31
The second piece of code is also way more complicated, because you need to properly manage the lifetime of the objects that are pointed to. Simply storing the address of local variables might end up badly. — Lukas-T, Mar 16 '21 at 13:34
@rustyx I always assumed that `std::set` had poor locality in the first place. If you put the elements in a vectors and had a `set` of pointers (assuming you fixed the comparator to dereference) wouldn't that *improve* cache locality, depending on how much the vector element order was similar to the set order? — François Andrieux, Mar 16 '21 at 13:36
@rustyx so, emplace can get the best performance, instead of custom compare operator? — nick, Mar 16 '21 at 13:43
Don't focus on "the best performance". Focus on having a program that calculates the results you desire. If, when you run it, it turns out to be too slow, then *measure* what the slow part is, and ask about speeding those up. — Caleth, Mar 16 '21 at 14:44
@FrançoisAndrieux maybe, but `std::set` is still a binary tree, even if just a tree of pointers. Need to benchmark to be sure. — rustyx, Mar 16 '21 at 14:55

score 3 · Accepted Answer · answered Mar 16 '21 at 13:31

3

Use a custom comparator:

#include <iostream>
#include <set>

struct CustomCmp {
    bool operator()(const int* lhs, const int* rhs) const { 
        return *lhs < *rhs;
    }
};

int main()
{
    int arr[] = { 3, 1, 4 };

    std::set<int*, CustomCmp> mySet;
    mySet.insert(&arr[0]);
    mySet.insert(&arr[1]);
    mySet.insert(&arr[2]);

    for (auto& el: mySet) std::cout << *el << ' '; // 1, 3, 4

    return 0;
}

https://godbolt.org/z/zGc1a3

answered Mar 16 '21 at 13:31

m88

1,968
6
14

thanks m88, but how's the performance comparing to using emplace? – nick Mar 16 '21 at 13:43
If your A class has a move-constructor, `s.insert(A(n))` and `s.emplace(n);` are roughly equivalent, otherwise `insert` will just make a copy of `A(n)`. (It doesn't make a difference at all for pointers) – m88 Mar 16 '21 at 13:49
@FrançoisAndrieux What I meant is [If you want a a set of T* sorted as if they were T, then] use a custom comparator. That being said, unless T is a `std::array` I doubt this is truly what OP needs, I agree. – m88 Mar 16 '21 at 14:21
@m88 Sorry, I tagged the wrong user. I meant to tag nick. Edit : I reposted my comment with the right @. – François Andrieux Mar 16 '21 at 14:43
@nick You are doing what is called Premature Optimization. You have two similar solutions, it isn't clear which will be fastest for your specific use case. Don't worry about it, it is a detail. Use the solution that is easiest and safest to work with and understand, which is by far `std::set`. – François Andrieux Mar 16 '21 at 14:44
@FrançoisAndrieux thank you, i think you are right – nick Mar 17 '21 at 01:18

How can make pointer valid in std::set?

1 Answers1