removedup.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>


template <typename T>
struct cmp
{
    bool operator()(std::pair<T, int>& a,
                    std::pair<T, int> & b)
    {
        return  a.second < b.second;
    }
};

template <typename T, typename Predicate_T>
class RemoveDups
{
    std::map<T, int> m_mapped;
    std::vector<std::pair<T, int>> m_sorted;
public:
    std::vector<T> operator()(const std::vector<T> in)
    {
        std::vector<T> ret;
        ret.reserve(in.size());
        for(int i=in.size()-1; i >= 0; i--)
            m_mapped[in[i]] = i;

        for(auto it : m_mapped)
            m_sorted.push_back(it);

        std::sort(m_sorted.begin(), m_sorted.end(), Predicate_T());
        for (auto it : m_sorted)
            ret.push_back(it.first);
        return ret;
    }
};


int main()
{
    std::vector<int> v          =   {1,1, 2, 2, 7, 2, 2, 7, 7, 2, 3, 8, 4, 5, 3, 2, 3, 2, 6, 2, 3, 2, 9, 10, 1, 2, 2, 1};
    std::vector<std::string> s =    {"world", "hello", "there", "world", "man", "there", "john", "doe", "doe", "john"};

    RemoveDups<int, cmp<int>> c;
    v = c(v);
    RemoveDups<std::string, cmp<std::string>> vs;
    s = vs(s);

    for(auto p : v)
        std::cout << p<< " ";
    std::cout << "\r\n";
    for(auto ps : s)
        std::cout << ps << " ";
    std::cout << "\r\n";

    return 0;
}