find_duplicate.cpp

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

using namespace std;

// g++ find_duplicate.cpp -o test -Wall -std=c++0x


class Test
{
    public:
        Test(const vector<int>&v):values(v){}
        bool test_with_direct(void);
        bool test_with_set(void);
        bool test_with_unique(void);

    private:
        vector<int> values;
};

bool Test::test_with_direct(void)
{
    for(vector<int>::iterator it=values.begin(); it<values.end()-1; it++)
    {
        for(vector<int>::iterator _it=it+1; _it<values.end(); _it++)
        {
            if(*it == *_it) return true;
        }
    }
    return false;
}

bool Test::test_with_set(void)
{
    set<int> tmp(values.begin(), values.end());
    return (tmp.size() != values.size());
}

bool Test::test_with_unique(void)
{
    sort(values.begin(), values.end());
    vector<int>::iterator unique_iter = unique(values.begin(), values.end());
    return (unique_iter != values.end());
}



int main(int argc, char *argv[])
{
    vector<int> input_duplicate{1, 23, 4, 2, 5, 2, 6, 4, 12, 3, 56, 33, 7, 90};
    vector<int> input_unique{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

    Test test_1(input_duplicate);
    Test test_2(input_unique);

    const int rounds = 10000 * 100;
    time_t start, end;

    cout << "test direct" << endl;
    start = time(NULL);
    for(int i=0; i<rounds; i++) test_1.test_with_direct();
    end = time(NULL);
    cout << "cost " << end-start << " seconds" << endl;


    cout << "test set" << endl;
    start = time(NULL);
    for(int i=0; i<rounds; i++) test_1.test_with_set();
    end = time(NULL);
    cout << "cost " << end-start << " seconds" << endl;

    cout << "test unique" << endl;
    start = time(NULL);
    for(int i=0; i<rounds; i++) test_1.test_with_unique();
    end = time(NULL);
    cout << "cost " << end-start << " seconds" << endl;

    

    return 0;
}