std::set<Key, Comparator, Allocator>

Question

I've tried to use set to keep some configurations in a trie lately.

I've found a doubt on the comparator, for instance :

    #include <iostream>
    #include <set>

    using namespace std;

    struct Node{
      int position;
      int reference;
      Node(int r, int p){
        this->position = p;
        this->reference = r;
      }
    };

    struct Node_c{
      const bool operator()(const Node& n1, const Node& n2){
        // return n1.reference != n2.reference;
        // i've tried some functions here, like n1.reference != n2.reference ? true : n1.position < n2.position;  
      }
    };


    int main(){
      set<Node, Node_c> aNodes;

      aNodes.emplace(1,1);
      aNodes.emplace(1, 2); // i dont want to add this one, the reference already exists and the position is bigger than the last one
      aNodes.emplace(1, 0); // i want to replace the (1,1) for this one


      for(auto nd : aNodes){
        cout << nd.reference << ' ' << nd.position << '\n';
      }
    }

How could I keep the nodes with the lesser positions in order but excluding the equals references?

thanks.

Answer 1

This cannot be done with a single method of std::set, because it strictly requires its elements to have unique keys!

set.emplace either inserts an element or it doesn't, but it won't replace an existing element, see the documentation

The best solution for you would probably be either to use a std::map<int, int> where a position is mapped to reference and update the value if it becomes smaller, or keep using a std::set and write a custom method that first checks if the set contains an element and if yes, only replaces it if the new reference is smaller

Also, your comparator should compare for less-than (<), not for inequality (!=)