stable_unique

#include <iostream>
#include <unordered_set>
#include <set>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>

using namespace std;


// iterator to praktycznie wskaźnik; można go przesuwać po elementach przez ++ i --
// "*iterator" to dereferencja "wskaźnika", czyli dostęp do wartośći, na którą pokazuje.
//to samo co pascalowskie "iterator^"

template <class iter>
iter stable_unique_1 ( iter first, iter last )
{
    unordered_set<int> temp; //zbiór użytych, pusty na poczatku
    iter writer(first); //tym będziemy czytac kazdy element
    iter reader(first); // tu bedziemy zapisywac tylko unikalne. poczatkowo oba wskazniki idą razem
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)==0){  //element pokazywany przez reader nie istenije w temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.insert(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer; // zwracam iterator (wskaźnik) za ostatnim sensownym elementem,
    //nie zmieniam wielkośći tablicy, tym sie zajme poziom wyzej,
    //taka konwencja, patrz idiom remove-erase
}


template <class iter>
iter stable_unique_2 ( iter first, iter last )
{
    set<int> temp; //zbiór użytych
    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)==0){  //element pokazywany przez reader nie istenije ww temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.insert(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer;
}

template <class iter>
iter stable_unique_3 ( iter first, iter last )
{
    iter writer(first);
    iter reader(first);
    while (reader!= last)  //czy to już koniec
    {
        if (count(first, writer, *reader)==0){  //elementu poszukiwany (wskazywany przez reader) nie ma
                                                  //w już przetworzonym zakresie (od [first a przed writer)
                                                //lepiej byłoby użyć funkcji find:
                                                //find(first, writer, *reader)==writer) ale warunek trochę zaciemnia:)
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
        }
        reader++;// kroczek
    }
    return writer;
}

template <class iter>
iter stable_unique_4 ( iter first, iter last )
{
    unordered_set<int> temp(first, last); //zbiór nieużytych
    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)>0){  //element pokazywany przez reader istenije w temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.erase(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer;
}


template <class iter>
iter unstable_unique ( iter first, iter last )
{
    sort(first, last);
    return unique(first, last);
}


template <class iter>
iter stable_unique_5 ( iter first, iter last )
{
    vector <int> sorted(first, last);
    vector <uint8_t> visited(sorted.size(),0);
    sort(sorted.begin(), sorted.end());

    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        auto it = lower_bound(sorted.begin(), sorted.end(),*reader);
        if ( visited[ it-sorted.begin() ]==0  ){
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            visited[ it-sorted.begin() ] = 1;
        }
        reader++;// kroczek
    }
    return writer;

}





class stoper
{
    chrono::time_point<chrono::high_resolution_clock> a,b;
public:
    void start(){a = chrono::high_resolution_clock::now();}
    void stop() {b = chrono::high_resolution_clock::now();}
    double value()
    {
        chrono::duration<double> elapsed_seconds = b-a;
        return elapsed_seconds.count();
    }
};


template <typename F >
void test (F f, string s)
{
    cout<<s<<endl<<"poprawność:"<<endl; ;
    vector<int> tab = {12,457,12,457,1,56,89,12,11,11,55,11,11,1,457};
    for (auto a:tab)
        cout<<a<<" ";
    cout<<endl;


    tab.erase( f( tab.begin(),tab.end() ), tab.end()  );

    for (auto a:tab)
        cout<<a<<" ";
    cout<<endl<<"szybkość"<<endl;

    random_device rd;
    mt19937 gen(rd());

    for (int size = 100; size<=100000;size*=10 )
    {
        tab.resize(size);
        generate(tab.begin(), tab.end(), gen);
        stoper st;   st.start();
        for (int i=0; i<100000/size+1;i++)
            tab.erase( f( tab.begin(),tab.end() ), tab.end()  );
        st.stop();
        cout<<size<<" zajelo "<<st.value()/((double)100000/size+1)<<"s"<<endl;
    }

    cout<<endl;


}

int main()
{

    typedef vector<int>::iterator iter;
    test(  stable_unique_1<iter> ,"hashmapa budowana" );
    test(  stable_unique_2<iter> , "zbior budowany" );
    test(  stable_unique_4<iter> , "hashmapa usuwana " );
    test(  stable_unique_3<iter> , "naiwne n^2 " );
    test(  unstable_unique<iter> , "sortowanie " );
    test(  stable_unique_5<iter> , "sortowanie stab" );
    return 0;
}