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

/*
 * multimaps are used to store 1:n relationships
 * the keys are in order, but the values are not
 * they are really multisets with a pair
 * they are not random access,
 * the [] is not supported like the map
 */

// overloading the output stream operator
ostream & operator << ( ostream & ost, const multimap<int,float> & l )
{
    multimap<int,float>::const_iterator i = l.begin();
    for ( ; i != l.end() ; ++i )
        ost << i->first << ":" << i->second << endl;
    return ost;
}

int main()
{
    multimap< int, float > m;

    for ( int i = 0 ; i < 10 ; ++i )
    {
        m.insert( make_pair( i, i * 1.01 ) );
        m.insert( make_pair( i, i * 0.02 ) );
    }
    cout << m << endl;

    // there are iterator based inserts too
    multimap< int, float >::iterator mmifi;
    mmifi = m.upper_bound( 7 );
    cout << "upper on 7 is " << mmifi->second << endl;
    mmifi = m.lower_bound( 7 );
    cout << "lower on 7 is " << mmifi->second << endl;

    m.insert( mmifi,  make_pair( 7, 7 * 0.01 ) );
    mmifi = m.upper_bound( 7 );
    m.insert( --mmifi,  make_pair( 7, 7 * 0.01 ) );
    cout << m << endl;

    // there are three forms of erase
    multimap< int, float >::iterator low;
    multimap< int, float >::iterator high;
    low = m.find( 7 );
    if ( low != m.end() )
    {
        cout << "erasing " << low->first << " " << low->second << endl;
        m.erase( low );   // take an iterator
    }
    low = m.lower_bound( 2 );
    high = m.upper_bound( 4 );
    if ( low != m.end() )
    {
        cout << "erasing from " << low->first << " " << low->second
            << " to " << high->first << " " << high->second << endl;
        m.erase( low, high );   // take an iterator range
    }
    cout << "erasing 6" << endl;
    m.erase( 6 );       // take a key
    cout << m << endl;

    return 0;
}