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]

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());  }}

use a set

edit: made it clicky. Also see UniqueAssociativeContainer

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

std::set<int> mySet(myList.begin(), myList.end());

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

(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;}

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());} 

ok. Thank you Anonymous Poster. The generic version is great. Obviously it works perfect. !! Very simple and clever!

Tahnk you all for help.

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]

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.