Not sure what STL function I am looking for

[BobMcGee123]

I have been cruising through SGI's STL website:

http://www.sgi.com/tech/stl/table_of_contents.html

I have a complex data structure X that only defines operator==(). I have a std::vector<X>, and I am trying to find the unique elements of this vector, using std::unique.

I can use std::unique on this data structure if data type X defines operator==(), but std::unique also requires that similar entires are grouped together. For an integral type, calling std::sort will do this for me, such as this bunch of code:

				
//MatRef is an std::vector<int>
std::sort(MatRef.begin(), MatRef.end());
std::vector<X>::iterator	RetVal;
//This should be renamed to 'NewEnd'
RetVal = std::unique(MatRef.begin(),MatRef.end());

I am looking for a function contained in <algorithm> that will group identical entires of a complex data structure together


Here is what I am trying to achieve:

void	NT_MODEL::BuildFromMS3DModel(CMS3D_MODEL	&	model)
{
	std::vector<NT_VERTEX>	all_model_vertexes; //not necessarily unique at this point
	std::vector<NT_VERTEX>	unique_vertexes;

	ConvertMS3DVertsToNT_Verts(model,all_model_vertexes);

	//In order for unique to work, operator== must be overloaded, and the entries must be 'sorted'
	//which, in this case, means all of the same vertexes are grouped together
	//works on any data structure that defines operator == 
	//std::sort(all_model_vertexes.begin(),all_model_vertexes.end());//doh, can't do this

	std::vector<NT_VERTEX>::iterator	new_end = 
	std::unique(all_model_vertexes.begin(),all_model_vertexes.end());
	
	std::copy(all_model_vertexes.begin(),new_end,unique_vertexes.begin());
}

I could easily write my own implementation of this, but I have a hard time believing this isn't already implemented in the stl.

[Ancient Dragon]

std::sort can sort any kind of objects -- all you have to do is define your own operator. Here is an example that I use

struct IAscendingSort
{
     bool operator()(const COLS& rpStart,const COLS& rpEnd)
     {
		 int s1 = atoi(rpStart[SortCol].c_str());
		 int s2 = atoi(rpEnd[SortCol].c_str());
		  bool val = s1 < s2;
		  // If not sorting by tcn or palid, and the previous comparison
		  // was true, then check the tcn or pallet id.
		  if(SortCol != 1 && s1 == s2)
		  {
				val = rpStart[1] < rpEnd[1];
		  }
		  return val;
     }
};

<snip>

std::sort(m_pal_data.m_data.begin(),m_pal_data.m_data.end(),IAscendingSort());

[BobMcGee123]

Hmm, this is still somewhat confusing to me. I simply do not see how I could implement an operator(), according to what sort requires, in a way that I can get it to put a complex non-integral type such that the same entries are grouped next to each other.

But, I am just simply going to write my own routine to accomplish that much, and the rest from the stl will work according to plan!

I wrote this, instead...it seems to work, and I don't actually think that I could write operator() in such a way that would guarantee what I am looking for, otherwise this may be overkill:

	//Make sure that similar groupings are next to each other, so that unique() will work
	for(std::vector<NT_VERTEX>::iterator	ptr = all_model_vertexes.begin()+1; ptr != all_model_vertexes.end(); ptr++)
	{
		NT_VERTEX	&	prev_ref = *(ptr-1);
		if(prev_ref == *ptr)
			continue;	//these entries already in order
		else
		{
			for(std::vector<NT_VERTEX>::iterator in_ptr = ptr+1; in_ptr != all_model_vertexes.end(); in_ptr++)
			{
				if(*in_ptr == prev_ref)
				{
					std::swap(ptr,in_ptr);	
				}
			}
		}
	}

[Mario F.]

You couldn't use the operator() solely, no. But std::sort relies on the < operator for vectors.

A combination of an overloaded operator< and a object function like suggested by ancient dragon will do this for you.

EDIT: Actually you might not even need to create an object function. Once you define how your complex class objects relate to each other by overloading the < operator, a normal std:sort will work as expected.