#include <list>
#include <ctime>
#include <vector> 
#include <iostream>
#include <algorithm>

int diff(timespec &time1, timespec &time2)
{
    return (time2.tv_sec - time1.tv_sec)*1000000 + (time2.tv_nsec - time1.tv_nsec) / 1000;
}

template<typename container> void update_con(container &con, size_t value)
{
    bool inserted = false;
    typename container::iterator it = con.begin();
    while(it != con.end())
    {
        if(*it == value)
            it = con.erase(it);
        else
        {
            if(!inserted && value < *it)
            {
                inserted = true;
                it = con.insert(it, value);
            }
            ++it;
        }
    }
    if(!inserted)   con.push_back(value);   
}

int main(void)
{
    timespec time1, time2;
    
    const size_t steps = 10000;
    {
        std::list<size_t> con;
        
        con.push_back(0);
        
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1);
        
        for(size_t i = 0; i < steps; ++i)
        {
            con.erase(con.begin());
            
            update_con(con,i*2);
            update_con(con,i*2+1);
            update_con(con,i*2+2);
            update_con(con,i*2+3);
        }
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2);
        
        std::cout << "list+insert:\t" << diff(time1,time2) << std::endl;  
    }
    
    {
        std::vector<size_t> con;
        
        con.push_back(0);
        
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1);
        
        for(size_t i = 0; i < steps; ++i)
        {
            con.erase(con.begin());
            
            update_con(con,i*2);
            update_con(con,i*2+1);
            update_con(con,i*2+2);
            update_con(con,i*2+3);
        }
        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2);
        
        std::cout << "vector+insert:\t" << diff(time1,time2) << std::endl;  
    }
    return 0;
}