Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C++ Builder > стандартные алгоритмы

Автор: ano360 23.1.2007, 18:51

Есть в библиотеке стандартных шаблонов такой алгоритм как Unique-по идее он удаляет все повторяющиеся элементы.
Есть ли какаиенибудь ограничения или особенности при сипользовонии этой функци.
У меня она почемуто не работает.

Код



bool even(TRCords c1,TRCords c2){
return c1==c2 ;
}

class TRCords{
        public:
        int i;
        int j;
        TRCords(){i=j=0;}
        TRCords(int i1,int j1){i=i1;j=j1;}
        bool operator<(TRCords &ob2){return(i<ob2.i&&j<ob2.j);}
        bool operator>(TRCords &ob2){return(i>ob2.i&&j>ob2.j);}
        bool operator==(TRCords &ob2){return (i==ob2.i && j==ob2.j);}
        bool operator!=(TRCords &ob2){return (i!=ob2.i || j!=ob2.j);}                
};

vector<TRCords>vectorTemp;

 unique(vectorTemp.begin(),vectorTemp.end(),even);

Автор: zkv 23.1.2007, 19:09

Цитата(ano360 @ 23.1.2007, 18:51

)

У меня она почемуто не работает.

а в чем это выражается?

Код


vector<TRCords>vectorTemp;
//где то тут должно быть заполнение вектора
 unique(vectorTemp.begin(),vectorTemp.end(),even);

Автор: ano360 23.1.2007, 19:17

дубликаты не удаляются. Просто не удаляются, как были, так и остаются.

Цитата

//где то тут должно быть заполнение вектора

Да. там просто ОЧЕНЬ много всякого када, на имеющего к проблеме отношения.
массив точно заполняется, сразу после вызова unique, у меня след. код.

Код



for(int j1=0;j1<int(vectorTemp.size());j1++)
                                WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String(" ")+vectorTemp[j1].i+String(" ")+vectorTemp[j1].j+String("~")).data(),5,0,NULL);
                                WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String("\n")).data(),1,0,NULL);

Да, и вот ещё странность-vectorTemp не чистится, но это пока не доказано

Добавлено @ 19:22

Код


for(int j1=0;j1<int(vectorTemp.size());j1++)
                               WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String(" ")+vectorTemp[j1].i+String(" ")+vectorTemp[j1].j+String("~")).data(),5,0,NULL);
                               WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String("\n")).data(),1,0,NULL);

                               unique(vectorTemp.begin(),vectorTemp.end(),even);

                               for(int j1=0;j1<int(vectorTemp.size());j1++)
                                WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String(" ")+vectorTemp[j1].i+String(" ")+vectorTemp[j1].j+String("~")).data(),5,0,NULL);
                                WriteConsole(GetStdHandle( STD_OUTPUT_HANDLE ),(String("\n")).data(),1,0,NULL);

при запуске следующего выводятся 2 идентичные строки:
2 2~ 2 3~ 2 4~ 3 2~ 3 4~ 4 2~ 3 2~ 3 4~ 4 2~ 4 4~ 5 2~ 5 3~ 5 4~ 4 4~
2 2~ 2 3~ 2 4~ 3 2~ 3 4~ 4 2~ 3 2~ 3 4~ 4 2~ 4 4~ 5 2~ 5 3~ 5 4~ 4 4~

Автор: ano360 23.1.2007, 19:40

кстати, вариант запуска unique(vectorTemp.begin(),vectorTemp.end()); у меня не работает, ыдаёт ошибку и посылает к исходникам, хотя operator== для ТРКордс, как вы видете, определён.

У кого есть какие идеи? Даже самые безумные

Автор: zkv 23.1.2007, 19:48

Цитата(ano360 @ 23.1.2007, 19:40

)

У кого есть какие идеи? Даже самые безумные

посмотрите комментарии в этом примере, здесь говорится про последовательные элементы:

Код


//from MSDN
// alg_unique.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>

using namespace std;

// Return whether modulus of elem1 is equal to modulus of elem2
bool mod_equal ( int elem1, int elem2 )
{
   if ( elem1 < 0 ) 
      elem1 = - elem1;
   if ( elem2 < 0 ) 
      elem2 = - elem2;
   return elem1 == elem2;
};

int main( )
{
   vector <int> v1;
   vector <int>::iterator v1_Iter1, v1_Iter2, v1_Iter3,
         v1_NewEnd1, v1_NewEnd2, v1_NewEnd3;

   int i;
   for ( i = 0 ; i <= 3 ; i++ )
   {
      v1.push_back( 5 );
      v1.push_back( -5 );
   }

   int ii;
   for ( ii = 0 ; ii <= 3 ; ii++ )
   {
      v1.push_back( 4 );
   }
   v1.push_back( 7 );
   
   cout << "Vector v1 is ( " ;
   for ( v1_Iter1 = v1.begin( ) ; v1_Iter1 != v1.end( ) ; v1_Iter1++ )
      cout << *v1_Iter1 << " ";
   cout << ")." << endl;

   // Remove consecutive duplicates
   v1_NewEnd1 = unique ( v1.begin ( ) , v1.end ( ) );

   cout << "Removing adjacent duplicates from vector v1 gives\n ( " ;
   for ( v1_Iter1 = v1.begin( ) ; v1_Iter1 != v1_NewEnd1 ; v1_Iter1++ )
      cout << *v1_Iter1 << " ";
   cout << ")." << endl;

   // Remove consecutive duplicates under the binary prediate mod_equals
   v1_NewEnd2 = unique ( v1.begin ( ) , v1_NewEnd1 , mod_equal );

   cout << "Removing adjacent duplicates from vector v1 under the\n "
        << " binary predicate mod_equal gives\n ( " ;
   for ( v1_Iter2 = v1.begin( ) ; v1_Iter2 != v1_NewEnd2 ; v1_Iter2++ )
      cout << *v1_Iter2 << " ";
   cout << ")." << endl;

   // Remove elements if preceded by an element that was greater
   v1_NewEnd3 = unique ( v1.begin ( ) , v1_NewEnd2, greater<int>( ) );

   cout << "Removing adjacent elements satisfying the binary\n "
        << " predicate mod_equal from vector v1 gives ( " ;
   for ( v1_Iter3 = v1.begin( ) ; v1_Iter3 != v1_NewEnd3 ; v1_Iter3++ )
      cout << *v1_Iter3 << " ";
   cout << ")." << endl;
   cin.get();
}

Автор: ano360 23.1.2007, 20:05

Это всё,конечно, здорово, и я вспомнил как пользоваться промтом, но мне это чёто не очень помогло.
Мож я тупой?
или уникуе удаляет только одинаковые эл-ты, стоящие друг за другом?

Автор: zkv 23.1.2007, 20:22

Цитата(ano360 @ 23.1.2007, 20:05

)

или уникуе удаляет только одинаковые эл-ты, стоящие друг за другом?

судя по примеру - да, но в описании нигде не встречал такого утверждения, у меня в студии удаляются только последовательные элементы

Автор: ano360 23.1.2007, 20:29

в чаком случае мне проще будет самому написать ф-ю удаления повторяющихся э-тов.

Автор: ano360 23.1.2007, 20:50

А как получить интератор элемента вектора с опред номером. допустим 3 его эл-та?

Я тут функцмю сортировки накидал, вдруг кому понадобится, только необходимо знать интератор эл -та

Код


template <class X> vector<X> RUnique(vector<X> &vec1){
int vec1_s = vec1.size();
for (int i=0;i<vec1_s;i++)
        for (int j=i+1;j<vec1_s;j++)
                if (vec1[j]==vec1[i])
                        vec1.erase[ интератор эл-та номер j ] ;

return vec1_s;
}

Автор: segmentation_fault 24.1.2007, 00:01

ano360, итератор определяется так:

Код


vec1.begin()+=j;

Но твоя функция не будет работать, т.к. после удаления элементов, размер вектора уменьшается, так что твой цикл

Код


 for (int j=i+1;j<vec1_s;j++)

будет указывать за пределы вектора.
Если порядок элементов вектора не принципиален, можешь сделать так:
создай сет, скопируй туда содержимое вектора, очисти вектор и скопируй туда содержимое сета. Одинаковые элементы в сет не копируются, так что получишь то, что хотел.

Автор: Vyacheslav 24.1.2007, 13:22

Про unique
1. Во-первых он "удаляет" смежные дубликаты
2. А во-вторых, он реально ничего не удаляет, как и любой remove-подобный алгоритм. Он просто перемещает дубликаты за логический конец и возвращает итератор этого логического конца. Причем, что самое неприятное, никто при этом не гарантирует, что в результате перемещения, часть перемещаемых элементов не исчезнет.
Поэтому вызов такого рода грубейшая ошибка

Код


 unique(vectorTemp.begin(),vectorTemp.end(),even);

Чтобы происходло реальное удаление смежных дубликатов следует использовать связку erase-unique

Код


  vectorTemp.erase( unique(vectorTemp.begin(),vectorTemp.end(),even), vectorTemp.end());

Автор: stmamont 24.1.2007, 14:08

ano360,
у этой сортировки сложность n^2 , логичней использовать встроенную в stl сортировку

Автор: ano360 24.1.2007, 17:23

Цитата(stmamont @ 24.1.2007, 14:08)

ano360,
у этой сортировки сложность n^2 , логичней использовать встроенную в stl сортировку

А конкретней?
Если вы имеете ввиду sort

Автор: ano360 24.1.2007, 17:40

Вот конечный вр-т:

Код


template <class X> vector<X> RUnique(vector<X> &vec1){
for (int i=0;i<vec1.size();i++)
        for (int j=i+1;j<vec1.size();j++)
                if (vec1[j]==vec1[i])
                        vec1.erase(vec1.begin()+j) ;

return vec1;
}

Добавлено @ 17:41

Цитата(stmamont @ 24.1.2007, 14:08)

ano360,
у этой сортировки сложность n^2 , логичней использовать встроенную в stl сортировку

Что вы имели ввиду? про с ложность n^2. Это как?

Автор: stmamont 24.1.2007, 17:53

Код


for (int i=0;i<vec1.size();i++)
        for (int j=i+1;j<vec1.size();j++)

сложность алгоритма - n^2

в то время как средняя сложность алгоритма встроенного sort составляет n * log n
где n количество сортируемых элементов в массиве.

Автор: ano360 24.1.2007, 18:17

круто, но мне ещё ведь надо и удалить все лишние эл-ты, а не только отсортировать, а моя ф-я делает итои другое.

Автор: segmentation_fault 24.1.2007, 19:53

ano360, а почему бы тебе не отсортировать сначала вектор стандартным алгоритмом, а потом применить unique, как это обьяснил Vyacheslav, т.к. в отсортированном векторе, все одинаковые элементы теперь действительно будут последовательными.

Автор: Vyacheslav 24.1.2007, 19:57

Цитата(segmentation_fault @ 24.1.2007, 00:01

)

создай сет, скопируй туда содержимое вектора, очисти вектор и скопируй туда содержимое сета. Одинаковые элементы в сет не копируются, так что получишь то, что хотел.

Логично

Код


#pragma hdrstop
#include <iterator>
#include<vector>
#include<set>
#include <algorithm>
#include <iostream>



//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

template< class T>
void my_unique(vector<T>& tmp)
{
    set<T> set_tmp(tmp.begin(), tmp.end());
    vector<T>(set_tmp.begin(),set_tmp.end()).swap(tmp);
}


int main(int argc, char* argv[])
{
    int temp[10] = { 1,2,3,4,5,1,2,3,4, 6  };
    vector<int> vectorTemp(temp, temp + 10);
   
    //вывод на консоль содержимого вектора 
    copy(vectorTemp.begin(),vectorTemp.end(),ostream_iterator< int, char >(cout," "));
    cout << endl;

    my_unique( vectorTemp );

     //вывод на консоль содержимого вектора  после удаления дубликатов
    copy(vectorTemp.begin(),vectorTemp.end(),ostream_iterator< int, char >(cout," "));
    cout << endl;
    return 0;
}
//---------------------------------------------------------------------------

Можно задействовать и sort c unique

Код


template< class T>
void my_unique(vector<T>& tmp)
{
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
}

Добавлено @ 20:08
Кстати для понимания работы unique посмотрите, что получится, если просто вызвать unique без erase

Код


void my_unique(vector<T>& tmp)
{
    sort(tmp.begin(), tmp.end());
    //tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    unique(tmp.begin(), tmp.end()); // грубая ошибка
}

Автор: ano360 24.1.2007, 20:18

segmentation_fault-Вы считаете это будет работать быстрее чем нов. функция?

Автор: stmamont 24.1.2007, 22:35

ano360, быстрее чем твоя - точно. особенно при больших объемах данных. и уж точно - надежно

Автор: Vyacheslav 25.1.2007, 10:31

Кстати в первом варианте сделал ошибку. Конечно же надо было

Код


template< class T>
void my_unique(vector<T>& tmp)
{
    //set<int> set_tmp(tmp.begin(), tmp.end());
    set<T> set_tmp(tmp.begin(), tmp.end());
    //vector<int>(set_tmp.begin(),set_tmp.end()).swap(tmp);
    vector<T>(set_tmp.begin(),set_tmp.end()).swap(tmp);
}