Erasing

[Mickey01]

Could you tell me how to erase elements in a vector without sorting and unique-ing it ? Do I have to create two loops running around checking for equality then delete the second if it turns to be tha same as the first although this would cost O(N*N) running time for the worst case ? Any possible ways you have in mind, because I don't have anything else in mind right now.--lol-

Thank you very much,

[Kheun]

You can try using std::set rather than std::vector. std::set is automatically sorted whenever an element is being inserted. Beside that, it doesn't allow duplicated element.

[Philip Nicoletti]

As Kheun mentioned, you can use set from the start. If you want
to use vector without sorting, you can try the following:

One thing you can do is to loop thru the vector,
inserting the elements into a set. If the insert
fails, then the element is already present in the
set (and the vector). You would erase that element.
To make it a little more efficient, you could store
pointers to the elements in the set, so potentially
expensive copying does not have to take place. This
will essentially be O(n*logn) for the "find" part.
(at the cost of extra memory) The erasing from the
vector can be expensive, especially if the elements
in the vector are expensive to copy. It can be made
a little less expensive by erasing the elements
at the end of the vector first (at the cost of some
extra memory). See code below for example of each.

#include <iostream>
#include <vector>
#include <set>
#include <functional>
#include <list>

using namespace std;

template <typename T>
struct indirect_less : public std::binary_function<T,T,bool> // #include <functional>
{
    bool operator () (const T & lhs , const T & rhs) const
    {
        return *lhs < *rhs;
    }
};

template <typename T>
void RemoveDuplicates(vector<T> & v)
{
    set<T*,indirect_less<T*> > s;

    vector<T>::iterator it = v.begin();

    while (it != v.end())
    {
        if (!s.insert( &(*it) ).second) 
            it = v.erase(it);
        else
            ++it;
    }

    return;
}



template <typename T>
void RemoveDuplicatesReverse(vector<T> & v)
{
    set<T*,indirect_less<T*> > s;
    list<vector<T>::iterator> iter_list;

    vector<T>::iterator it = v.begin();

    while (it != v.end())
    {
        if (!s.insert( &(*it) ).second) 
        {
            iter_list.push_front(it);
        }

        ++it;
    }

    list<vector<T>::iterator>::iterator lit = iter_list.begin();
    while (lit != iter_list.end())
    {
        v.erase(*lit);
        ++lit;
    }

    return;
}

int main()
{
    int temp[] = {1,2,56,32,2,5,2,1,100,32};

    vector<int> v(temp,temp+10);

    RemoveDuplicatesReverse(v);

    vector<int>::iterator it = v.begin();

    it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    return 0;
}

[Mickey01]

Thanks Kheun,
Thanks Phlip so much...--lol

Most of questions made as far as i have read, are only to remove duplicate elements, but what if i would like to get only duplicates of two different arrays ?
Do you know any ways to make its algorithm 's running time less than O(SizeOfArray1*SizeOfArray2) ?
Philip, Can Philip give me an example of arrays whose elements are little bit more meaningful ? Philip help me Okay ?

Thanks Philip again much much.

[Guysl]

The following post might help:
http://www.codeguru.com/forum/showthread.php?t=300630

Regards,
Guy