Archived

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

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

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

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 on other sites
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 on other sites
use a set

edit: made it clicky. Also see UniqueAssociativeContainer

[edited by - petewood on March 25, 2004 2:11:46 PM]

Share on other sites
std::set<int> mySet(myList.begin(), myList.end());

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 on other sites
(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 on other sites
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 on other sites
ok. Thank you Anonymous Poster. The generic version is great. Obviously it works perfect. !! Very simple and clever!

Tahnk you all for help.

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 on other sites
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.

1. 1
Rutin
34
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• 9
• Forum Statistics

• Total Topics
633332
• Total Posts
3011403
• Who's Online (See full list)

There are no registered users currently online

×