#include<iostream>
#include<list>
using namespace std;
/*
 * lists are unordered linked structures
 * they do not support random access
 * insert and remove are faster than a vector
 */

// a comparision function, return true on greater than
// default compare is less than
bool compare( const int & a, const int & b )
{
        return a > b;
}

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

int main()
{
    list<int> l;

    l.push_back(42); // allocates memory and places at back
    for ( int i = 0 ; i < 10 ; ++i )
        l.push_back(i);
    l.push_back(86);

    cout << "size = " << l.size() << endl;
    cout << "front = " << l.front() << endl;
    cout << "back = " << l.back() << endl;

    l.pop_back();   // removes element at back end
    l.pop_front();  // removes element at front end

    l.resize( 15, -999 );   // resize and set values
    // the value only gets applied to new elements

    l.push_back( -72 );
    l.push_back(2);
    l.push_back(9);

    // typedefs are your friend
    typedef list<int>::iterator li;
    for ( li i = l.begin() ; i != l.end() ; ++i )
        cout << *i << " ";
    cout << endl;

    li lii;
    // these are not supported, they require random access
    //lii = l.begin() + 4;
    //cout << l[4] << endl;
    // but iteration is supported
    ++lii;
    lii++;

    // erase can be called on single element and range
    lii = l.erase( lii );
    // it returns the one after the erase
    cout << "after erase " << *lii << endl;

    // you can remove a value also, this gets all of them
    l.remove( -999 );
    cout << l << endl;

    // using sort method for lists, which is faster than the function
    l.sort();
    cout << l << endl;

    // adding new elements will break the order
    l.push_front( -7 ); // I can insert on either end
    l.push_front(19);
    l.push_back(113);
    cout << l << endl;

    // remove duplicate elements
    l.unique();
    cout << l << endl;

    // resort using my compare function
    l.sort( compare );
    cout << l << endl;



    return 0;
}