#include<iostream>
#include<set>
using namespace std;

/*
 * sets are ordered red-black trees, without duplicates
 * they do not support random access
 * all traversal is log(n)
 */
// overloading the output stream operator
ostream & operator << ( ostream & ost, const set<int> & l )
{
    set<int>::const_iterator i = l.begin();
    for ( ; i != l.end() ; ++i )
        ost << *i << " ";
    return ost;
}

int main()
{
    set<int> s;

    // put some elements in the set
    for ( int i = 0 ; i < 10 ; ++i )
        s.insert( 30 - ( i * 3 ) );

    cout << s << endl;
    // adding some more elements
    s.insert( 25 );
    s.insert( 10 );
    s.insert( 19 );
    cout << s << endl;
    // these duplicates are not inserted
    s.insert( 25 );
    s.insert( 10 );
    s.insert( 19 );
    cout << s << endl;

    set<int>::iterator si;

    // lower_bound returns iterator to first element >=
    si = s.lower_bound ( 9 );
    cout << "lower on 9 " << *si << endl;
    si = s.lower_bound ( 13 );
    cout << "lower on 13 " << *si << endl;
    // upper_bound returns iterator to first element >
    si = s.upper_bound ( 9 );
    cout << "upper on 9 " << *si << endl;

    // declare a pair of iterators
    pair< set<int>::iterator, set<int>::iterator > psi;
    // get the range
    psi = s.equal_range( 9 );
    // show the two iterators
    cout << "equal range" << endl;
    cout << "first " << *psi.first << endl;
    cout << "second " << *psi.second << endl;

    return 0;
}