Дубликаты 17102015a

//ы

#include <iostream>
#include <vector>
#include <Windows.h>
using namespace std;


struct Oper
{
    template<typename T>
    static void dupDel(vector<T>& vData)
    {
        unsigned eInd, sz, 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 sz, szStp, eInd, n, k;
        bool found_1stDup, added;
        vector<unsigned> dupI;
        vector<unsigned>::iterator it;
        vector<unsigned>::iterator itB;

        sz = vData.size();
        szStp = sz;
        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;
        //
    }




};


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";

    vector<unsigned> dI = Oper::dupFind(vD);

    for(unsigned n=0; n < dI.size(); n++)
    {
        cout << dI[n] << endl;
    }


}