Archived

This topic is now archived and is closed to further replies.

STL vectors unique algo - Why this doesnt work...

This topic is 5009 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi. I would like to make my container containing only unique values (eg. Vector3D) using STL. I know that I could use the STL unique() algorithm but that will only remove items that are adjecent ie. the list must be sorted. eg. STL unique will convert this line: 1113334444 into 134 which is cool but my vector3D cannot be sorted so the list of vectors I have is not sorted and the STL unique doesnt help. Am I right or there is a way to use it for unsorted lists? Ok. I tried to write my own unique which works ok but it crashes in the end once I have a unique list of numbers extracted. It seems to me that the p!=list.end() doesnt stop at the end() and it just crashes after the container is reduced. Obviously I am doing something wrong. Can anybody help please or show some even more clever ways of doing it please. #include <list> #include <algorithm> void main() { std::list list; std::list::iterator p, where; list.push_back( 5 ); list.push_back( 2 ); list.push_back( 8 ); list.push_back( 2 ); list.push_back( 5 ); list.push_back( 2 ); list.push_back( 8 ); list.push_back( 2 ); list.push_back( 5 ); list.push_back( 2 ); list.push_back( 8 ); list.push_back( 2 ); for( p=list.begin(); p!=list.end() { int i = *p; ++p; int size1 = list.size(); if( p!= list.end() ) { where = remove(p, list.end(), i ); list.erase( where, list.end() ); } int size2 = list.size(); } for( p=list.begin(); p!= list.end(); p++) { int i = *p; } int size2= list.size(); } NOTE: this examples contains numbers not Vector3D but it is same thing. I dont want to sort the container. I just need to get rid of all repeating values. Thank you. [edited by - robert_s on March 25, 2004 1:08:45 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Erase invalidates iterators only to objects that are erased.

Your code makes it possible for p to be erased and still referenced.

Try this (untested):

for( p=list.begin(); p!=list.end(); p++)
{
int i = *p;
if( p+1 != list.end() )
{
list.erase (remove (p+1, list.end(), i ), list.end());
}
}

Share this post


Link to post
Share on other sites
ok Thank you Anonymous Poster but p+1 wont work p++ is ok but not p+1. I tried this too.


petewood
Yes set could be a good solution as it wont invalidate iterators.
I will try this once I get fed up with my code above.

Anyone else has any new ideas?


Thanks

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
(Same AP)

This works fine and is a little cleaner:

#include <list>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>

using namespace std;

int main ()
{
list<int> mylist;

for (int i = 0; i < 1000; i++)
{
mylist.push_back (rand()%100);
}

// Start unique

list<int>::iterator cur, end;
end = mylist.end();
cur = mylist.begin();
while (cur != end)
{
int i = *cur;
end = remove (++cur, end, i);
}
mylist.erase (end, mylist.end());
// End unique


copy (mylist.begin(), mylist.end(), ostream_iterator<int>(cout, " "));
return 0;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Generic version (should work with most containers):
template<typename T> void unique (T &con)
{
typename T::iterator cur, end;
cur = con.begin();
end = con.end();
while (cur != end)
{
typename T::value_type i = *cur;
end = remove (++cur, end, i);
}
con.erase (end, con.end());
}

Share this post


Link to post
Share on other sites
quote:
Original post by robert_s
my vector3D cannot be sorted


I don't think it is possible for something that can be compared to be unsortable. The sorting order might be arbitrary but you can still put identical items next to each other so they can be quickly removed.

If you look at AP's solution it is very similar to a selection sort. Isn't it O(n^2)?

The existing stl way of doing it (sort then unique) will require timeToSort + timeToUnique with timeToSort being O(nlogn) and timeToUnique O(n).

Now sorting vectors in an arbitrary way is not something you probably want to overload thier comparison operators with, but you can make a function or a function object stl can sort with with (provided set would not be better anyway).

Make one that does a test like:

bool compareVector(const myVector& a, const myVector& b)
if a.x < b.x
return true
else if a.x == b.x
if a.y < b.y
return true
else if a.y == b.y
if a.z < b.z
return true

return false


Another option, anyhow.

PS to use a set you have to make a comparitor of some type as well because set is a sorted container.

[edited by - JeffF on March 25, 2004 10:01:58 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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());
}

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
quote:
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]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
and then he''s back at having to order them...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
preserve original order, efficenct

choose one.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites