#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

//Lists
typedef  list<int> Liste; // lists are doubled linked lists

Liste mk_empty_list()
{
  return list<int>();
}

void print_list(Liste L)
{
  list<int>::iterator p_L ;
  for(p_L=L.begin(); p_L != L.end(); ++p_L) 
    cout << *p_L << " ";
  cout << endl;
}

void insertHead(Liste* L, int elem)
{
  (*L).push_front(elem);
}

void insertEnd(Liste* L, int elem)
{
  (*L).push_back(elem);
}

void insertMiddle(Liste* L, Liste::iterator it,int elem)
{
  (*L).insert(it,elem);
}

// insert in a sorted list.
void insertinSortedList(Liste* L,int elem)
{
  //algo : lower_bound
  Liste::iterator theplace = lower_bound(L->begin(), L->end(), elem);
  L->insert(theplace,elem);
}


int main()
{
  Liste l = mk_empty_list();
  
  insertHead(&l,42);
  insertHead(&l,23);

  insertinSortedList(&l,35);
  insertinSortedList(&l,70);

  print_list(l);

  Liste l2 = mk_empty_list();
  insertHead(&l2,2);
  insertHead(&l2,-42);
  insertHead(&l2,1515);
  insertHead(&l2,70);
  
  l2.sort(); // sort is used with < as standard comparaison function on integers

  print_list(l2);

  return 0;
}