Sets in C++

· by

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main() {
    // create an empty set of integers
    set<int> mySet;

    // insert one element
    mySet.insert(5);

    // insert another element
    mySet.insert(4);

    // insert more elements
    mySet.insert(1337);
    mySet.insert(42);
    mySet.insert(31415);

    // insert an element which was there before
    mySet.insert(5);

    // check if 4 is in set
    bool is_in = mySet.find(4) != mySet.end();
    cout << "4 is in mySet: " << is_in << endl;

    is_in = mySet.find(6) != mySet.end();
    cout << "6 is in mySet: " << is_in << endl;

    // iterate over the set
    set<int>::iterator myIt;
    for(myIt=mySet.begin(); myIt != mySet.end(); myIt++){
        cout << *myIt << " ";
    }

    return 0;
}

As find is logarithmic in size() (source: C++ Reference), the membership test is also in \(\mathcal{O}(\log(n))\).

Sets of structs

If you want to create a set of structs, you have to create a comparator:

bool operator<(const Edge&amp; left, const Edge&amp; right)
{
    return left.uniqueEdge < right.uniqueEdge;
}

See also