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

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

int main()
{
    multiset<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 will be inserted
    s.insert( 25 );
    s.insert( 10 );
    s.insert( 19 );
    cout << s << endl;

    multiset<int>::iterator si;

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

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

    // now lets erase some of them
    cout << s << endl;
    s.erase( 19 );
    s.erase( 10 );
    cout << s << endl;

    return 0;
}