You can''t solve this in any less than n^2 anyhow if you can''t sort the data. Simply because you have to compare each element to each other element to be able to say that theyr''e not unique.
The best solution would be making them sortable and then using std::unique or similar.
STL vectors unique algo - Why this doesnt work...
Slightly faster vector only version, note that it won''t keep elements in the sme order as in the original.
template <typename T>void unique_vector( std::vector<T> &v){ typedef typename vector<T>::iterator iterator; iterator e = v.end(); for( iterator b = v.begin(); b != e;) { typename vector<T>::reference r = *b; for( iterator m = ++b; m != e;) if( *m == r) std::iter_swap( m, --e); else ++m; } v.erase( e, v.end());}
quote:Original post by Anonymous Posterquote:Original post by JeffF
If you look at AP's solution it is very similar to a selection sort. Isn't it O(n^2)?
It certainly is, and that sucks to some degree. I'm operating under the assumption that the data needs to be unsorted before being used. sort + unique would be better in any other case.
Ahh good point, it is possible that the original poster meant that he wants the present order preserved, but the duplicates removed, not that vector3d cannot be sorted, or something like that.
[edited by - JeffF on March 26, 2004 12:48:22 PM]
Yes Jeff. I meant that. I did not want to sort vertors which is obviously possible. I just wanted to remove duplicates and preserve whatever the order is.
Actualy I have one more question realted to vector sorting.
Say if I store all my vectors into list or vector and wish to sort it using STL sort() func but I do not want to add comapre operator to my Vector3D class. Can I still do that using some local function? As far as I know providing the Vector3D class with greater/less operator just like operator+ will solve that but is there any other way?
Actualy I have one more question realted to vector sorting.
Say if I store all my vectors into list or vector and wish to sort it using STL sort() func but I do not want to add comapre operator to my Vector3D class. Can I still do that using some local function? As far as I know providing the Vector3D class with greater/less operator just like operator+ will solve that but is there any other way?
That is the solution I gave: a function or a function object you pass into the sort algorithm.
An example:
http://www.josuttis.com/libbook/stl/sort1.cpp.html
An example:
http://www.josuttis.com/libbook/stl/sort1.cpp.html
Actually you can do this in O(n log n) if you use some extra storage, if you can order them (and you can with 3D vectors).
You could simply have a temporary vector and a set using a custom comparison object then you simply try to insert each element from the original vector into the set and if it succeeds you put it into the temporary vector, when you''ve done this for the whole original vector the temporary vector will contain all unique values in their original order so simply swap the temporary and the original and your''e done.
You could simply have a temporary vector and a set using a custom comparison object then you simply try to insert each element from the original vector into the set and if it succeeds you put it into the temporary vector, when you''ve done this for the whole original vector the temporary vector will contain all unique values in their original order so simply swap the temporary and the original and your''e done.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement