Emad Kheyroddin
Emad Kheyroddin

Reputation: 25

How does the C++ std::set check for duplication?

Take this code snippet, for example:

#include <iostream>
#include "set"

using namespace std;

struct WeightedEdge {
public:
    int weight;
    int n1;
    int n2;

    WeightedEdge(int n1, int n2, int weight) {
        this->n1 = n1;
        this->n2 = n2;
        this->weight = weight;
    }

    void print() {
        cout << "WeightedEdge(" << "n1= " << n1 << ",n2= " << n2;
        cout << ",weight= " << weight << ")" << endl;
    }

    bool operator<(const WeightedEdge &other) const {
        if (weight < other.weight) {
            return true;
        } else if (weight > other.weight) {
            return false;
        } else {

            if (n1 < other.n1) {
                return true;
            } else if (n1 > other.n1) {
                return false;
            } else {
                if (n2 < other.n2) {
                    return true;
                } else if (n2 > other.n2) {
                    return false;
                } else {
                    return false;
                }
            }

        }
    }

};

int main() {

    set<WeightedEdge> edges;

    edges.insert(WeightedEdge(1, 2, 5));
    edges.insert(WeightedEdge(1, 12, 5));
    edges.insert(WeightedEdge(1, 5, 5));
    edges.insert(WeightedEdge(1, 3, 5));
    edges.insert(WeightedEdge(1, 2, 5));


    for (auto i = edges.begin(); i != edges.end(); ++i) {
        auto edge = *i;
        edge.print();
    }
}

I don't know if I understand how insertion in sets works in C++, but it seems like it uses the less-than operator (by default) to compare and place the inserted element correctly.

However, I can't understand how it detects duplication.

If we insert (1,2,5) and (1,12,5) in the set, the operator function returns false when it's comparing n2 attributes.

But when we try to insert (1,2,5) and (1,2,5), the operator also returns false.

So, how does the set decide to insert the (1,4,5) but not the second (1,2,5) while the operator returned false anyways?

Upvotes: 0

Views: 114

Answers (0)

Related Questions