Дубликаты 17102015b

//ы

#include <iostream>
#include <vector>
using namespace std;


template<typename T>
struct twoVectors
{
    vector<T> vFirst;
    vector<T> vSecond;
};

typedef twoVectors<unsigned> twoVU;
typedef twoVectors<int> twoVI;
typedef twoVectors<float> twoVF;



struct Oper
{
    template<typename T>
    static void dupDel(vector<T>& vData)
    {
        unsigned eInd, n, k;
        bool oneOrMore_del;
        vector<T>::iterator it;

        sz = vData.size();

        // проверка на Дубликаты и Корректировка
        for( oneOrMore_del = false, eInd = sz-1,  n=0; n < eInd; n++ )
        {
            for(k = n + 1; k < sz;)
            {
                if( vData[n] == vData[k] )
                {
                    it = vData.begin() + k;
                    vData.erase(it);
                    oneOrMore_del = true;

                    eInd--;
                    sz--;
                }
                else k++;
            }
        }
        // освобождаем память если необходимо
        if(oneOrMore_del) vData.shrink_to_fit();
    }

    //

    template<typename T>
    static vector<unsigned> dupFind(const vector<T>& vData)
    {
        unsigned szStp, eInd, n, k;
        bool found_1stDup, added;
        vector<unsigned> dupI;
        vector<unsigned>::iterator it;
        vector<unsigned>::iterator itB;

        szStp = vData.size();
        eInd = szStp - 1;

        // инициализация вектора Шагов для проверки Дубликатов
        vector<unsigned> stepsI(szStp);
        for(n=0; n < szStp; n++)
        {
            stepsI[n] = n;
        }

        // резервируем по максимуму память для ускорения
        // максимальное кол-во = 1 уникальный и все остальные дубликаты = size - 1
        dupI.reserve(eInd);

        // 1ое Нахождение дубликатов
        found_1stDup = false;
        for( n=0; n < eInd; n++ )
        {
            for( k = n+1; k < szStp; )
            {
                if( vData[stepsI[n]] != vData[stepsI[k]] ) k++;
                else
                {
                    dupI.push_back( stepsI[k] );
                    found_1stDup = true;

                    // удаление из вектора Шагов
                    it = stepsI.begin() + k;
                    stepsI.erase(it);
                    szStp--;
                    eInd--;
                }
            }

            if(found_1stDup){ n++; break; }
            //
        }


        // следующие проверки на Дубликаты
        if(found_1stDup)
        {
            for( ; n < eInd; n++ )
            {
                for( added = false, k = n+1; k < szStp; added = false )
                {
                    if( vData[stepsI[n]] != vData[stepsI[k]] ) k++;
                    else
                    {
                        // Добавляем в нужную Позицию чтобы стало по-Порядку !!
                        for(itB = dupI.begin(), it = dupI.end()-1; it > itB; it--)
                        {
                            if( stepsI[k] > *it )
                            {
                                it = dupI.insert(it+1, stepsI[k]);
                                it--;

                                // удаление из вектора Шагов
                                stepsI.erase( stepsI.begin() + k );
                                eInd--;
                                szStp--;

                                added = true;
                                break;
                            }
                        }

                        if(!added)
                        {
                            // тут итератор dupI стоит вначале
                            if( stepsI[k] > *it ) dupI.insert(it+1, stepsI[k]);
                            else
                                dupI.insert(it, stepsI[k]);

                            // удаление из вектора Шагов
                            stepsI.erase( stepsI.begin() + k );
                            eInd--;
                            szStp--;
                        }
                    }
                }
            }
            //
        }

        dupI.shrink_to_fit();
        return dupI;
        //
    }

    //

    template<typename T>
    static vector<unsigned> uniqFind(const vector<T>& vData)
    {
        unsigned szStp, eInd, n, k;
        vector<unsigned> dupI;

        szStp = vData.size();
        eInd = szStp - 1;

        // инициализация вектора Шагов для проверки Дубликатов
        vector<unsigned> stepsI(szStp);
        for(n=0; n < szStp; n++)
        {
            stepsI[n] = n;
        }

        // Фильтрация на Уникальные индексы
        for( n=0; n < eInd; n++ )
        {
            for( k = n+1; k < szStp; )
            {
                if( vData[stepsI[n]] != vData[stepsI[k]] ) k++;
                else
                {
                    // удаление из вектора Шагов
                    stepsI.erase( stepsI.begin() + k );
                    szStp--;
                    eInd--;
                }
            }
        }

        stepsI.shrink_to_fit();
        return stepsI;
        //
    }

    //

    template<typename T>
    static twoVU uniqueAndDup_Find(const vector<T>& vData)
    {
        unsigned szStp, eInd, n, k;
        bool found_1stDup, added;
        vector<unsigned> dupI;
        vector<unsigned>::iterator it;
        vector<unsigned>::iterator itB;

        szStp = vData.size();
        eInd = szStp - 1;

        // инициализация вектора Шагов для проверки Дубликатов
        vector<unsigned> stepsI(szStp);
        for(n=0; n < szStp; n++)
        {
            stepsI[n] = n;
        }

        // резервируем по максимуму память для ускорения
        // максимальное кол-во = 1 уникальный и все остальные дубликаты = size - 1
        dupI.reserve(eInd);

        // 1ое Нахождение дубликатов
        found_1stDup = false;
        for( n=0; n < eInd; n++ )
        {
            for( k = n+1; k < szStp; )
            {
                if( vData[stepsI[n]] != vData[stepsI[k]] ) k++;
                else
                {
                    dupI.push_back( stepsI[k] );
                    found_1stDup = true;

                    // удаление из вектора Шагов
                    it = stepsI.begin() + k;
                    stepsI.erase(it);
                    szStp--;
                    eInd--;
                }
            }

            if(found_1stDup){ n++; break; }
            //
        }


        // следующие проверки на Дубликаты
        if(found_1stDup)
        {
            for( ; n < eInd; n++ )
            {
                for( added = false, k = n+1; k < szStp; added = false )
                {
                    if( vData[stepsI[n]] != vData[stepsI[k]] ) k++;
                    else
                    {
                        // Добавляем в нужную Позицию чтобы стало по-Порядку !!
                        for(itB = dupI.begin(), it = dupI.end()-1; it > itB; it--)
                        {
                            if( stepsI[k] > *it )
                            {
                                it = dupI.insert(it+1, stepsI[k]);
                                it--;

                                // удаление из вектора Шагов
                                stepsI.erase( stepsI.begin() + k );
                                eInd--;
                                szStp--;

                                added = true;
                                break;
                            }
                        }

                        if(!added)
                        {
                            // тут итератор dupI стоит вначале
                            if( stepsI[k] > *it ) dupI.insert(it+1, stepsI[k]);
                            else
                                dupI.insert(it, stepsI[k]);

                            // удаление из вектора Шагов
                            stepsI.erase( stepsI.begin() + k );
                            eInd--;
                            szStp--;
                        }
                    }
                }
            }
            //
        }

        twoVU tVi;
        tVi.vFirst = stepsI;
        tVi.vSecond = dupI;

        return tVi;
        //
    }


};


void main()
{
    vector<const char*> vD(13);

    vD[0] = "d33";
    vD[1] = "d33";
    vD[2] = "z44";
    vD[3] = "d33";
    vD[4] = "d33";
    vD[5] = "x55";
    vD[6] = "d33";
    vD[7] = "n558797";
    vD[8] = "x55";
    vD[9] = "x55";
    vD[10] = "d33";
    vD[11] = "j77";
    vD[12] = "j77";


    cout << "Unique Indexes: " << endl;
    twoVU udI = Oper::uniqueAndDup_Find(vD);
    for(unsigned n=0; n < udI.vFirst.size(); n++)
    {
        cout << udI.vFirst[n] << endl;
    }
    cout << endl;


    cout << "Duplicate Indexes: " << endl;
    for(unsigned n=0; n < udI.vSecond.size(); n++)
    {
        cout << udI.vSecond[n] << endl;
    }



}