Solved

# sort stl vector using stl algorithm sort() EZ points =)

Posted on 2004-04-10
22,338 Views
I need to sort vertices in space by either x,y, or z position. Here's my vertex data class:

class VERTEX3
{
float x, y,z;
};

I hold all my vertexes in an stl vector:

vector<VERTEX3> VertexList;

So now I want to sort be able to arbitrarily sort the list by either x y or z. Here's what I have so far:

----------------------------------------------------------------------
#include <vector>
#include <algorithm>

vector<VERTEX3> VertexList;

// populate vector with vertexes...blah blah blah....

//suppose i want to sort by x value now...it will be something like
sort(VertexList.begin(), VertexList.end(),  ???? );
------------------------------------------------------------------------

Basically, what goes in the "????" spot. I know it involves a custom function, but does it need to be a member of the vertex class? Operator overloading the < operator wont work either, since it doesnt allow me to specify sort by x,y,z. An example would really help. Thanks!
0
Question by:Fippy_Darkpaw
• 3
• 3
• 3
• +2

LVL 9

Expert Comment

Hi Fippy_Darkpaw,

I guess that checking

http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20724639.html

will do all the work

Hope this helps

Tincho
0

LVL 9

Expert Comment

Fippy_Darkpaw,

In a few words....

If the comparison function is already defined
(for built in types or operator< implemented for the template parameter class>

there is no need for the third parameter

a very simple example is

class Foo
{
public:
Foo( ) {;}
Foo( int id ) : _id( id ) {;}

// Rest of code

bool operator<( const Foo & otherFoo ) { return this._id < otherFoo._id; }

private:
int _id;
};

vector<Foo> vec;

vec.push_back( new Foo( 1 ) );
vec.push_back( new Foo( 4 ) );
vec.push_back( new Foo( 2 ) );
vec.push_back( new Foo( 5 ) );
vec.push_back( new Foo( 8 ) );
vec.push_back( new Foo( 7 ) );

sort( vec.begin(), vec.end() );

If not, you can.......

Finally

The case where you use the third parameter is when you want to define a custom comparison and not use the one implemented or in case operator< is not implemented.

class Foo
{
public:
Foo( ) {;}
Foo( int id ) : _id( id ) {;}

// Rest of code

private:
int _id;
};

struct Comparer
{
bool operator()( const Foo & a, const Foo & b )
{
return *a < *b;
}
};

vector<Foo> vec;

vec.push_back( new Foo( 1 ) );
vec.push_back( new Foo( 4 ) );
vec.push_back( new Foo( 2 ) );
vec.push_back( new Foo( 5 ) );
vec.push_back( new Foo( 8 ) );
vec.push_back( new Foo( 7 ) );

sort( vec.begin(), vec.end(), Comparer() );

you can also check

http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20848151.html

Hope this helps

Tincho
0

LVL 3

Expert Comment

Hi Fippy_Darkpaw,

float getX(VERTEX3 v) { return v.x; }
float getY(VERTEX3 v) { return v.y; }
float getZ(VERTEX3 v) { return v.z; }

sort(VertexList.begin(), VertexList.end(), compose2(less<float>(), getX, getX));

Cheers!
0

LVL 10

Expert Comment

//EXAMPLE
// alg_sort.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // For greater<int>( )
#include <iostream>

// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 )
{
return elem1 > elem2;
}

int main( )
{
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;

int i;
for ( i = 0 ; i <= 5 ; i++ )
{
v1.push_back( 2 * i );
}

int ii;
for ( ii = 0 ; ii <= 5 ; ii++ )
{
v1.push_back( 2 * ii + 1 );
}

cout << "Original vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

sort( v1.begin( ), v1.end( ) );
cout << "Sorted vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

// To sort in descending order. specify binary predicate
sort( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "Resorted (greater) vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

// A user-defined (UD) binary predicate can also be used
sort( v1.begin( ), v1.end( ), UDgreater );
cout << "Resorted (UDgreater) vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
}
//*********************************************
Output
Original vector v1 = ( 0 2 4 6 8 10 1 3 5 7 9 11 )
Sorted vector v1 = ( 0 1 2 3 4 5 6 7 8 9 10 11 )
Resorted (greater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )
Resorted (UDgreater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )

0

LVL 86

Expert Comment

>>Basically, what goes in the "????" spot

A predicate object like

class VERTEX3Sort {

public:
bool operator() ( const VERTEX3& a, const VERTEX3& b) {
return [true or false based on your sort criteria];
}
};

//...

sort(VertexList.begin(), VertexList.end(),  VERTEX3Sort() );
0

LVL 3

Expert Comment

sorry, that compose2 returns a unary function h such that h(v) is equivalent to less(getX(v), getX(v)); which is always false. there doesn't seem to be a nice function to do it so hear is my_compose.

template<class A, class B, class C>
class my_compose : binary_function<typename B::argument_type, typename C::argument_type, typename A::result_type>
{
protected:
A fn;
B fn_1;
C fn_2;
public:
my_compose(const A& a, const B& b, const C& c) : fn(a), fn_1(b), fn_2(c) {}

typename _Operation1::result_type
operator()(const typename B::argument_type& b, const typename C::argument_type& c) const
{
return fn(fn_1(b), fn_2(c));
}
}

then simple change compose2 to my_compose
0

LVL 3

Expert Comment

oops change _Operation1 to A

template<class A, class B, class C>
class my_compose : binary_function<typename B::argument_type, typename C::argument_type, typename A::result_type>
{
protected:
A fn;
B fn_1;
C fn_2;
public:
my_compose(const A& a, const B& b, const C& c) : fn(a), fn_1(b), fn_2(c) {}

typename A::result_type
operator()(const typename B::argument_type& b, const typename C::argument_type& c) const
{
return fn(fn_1(b), fn_2(c));
}
}
0

LVL 4

Author Comment

Ok getting really close here. Based on the suggestions I have the following test program with nearly the exact data structures I am using. In case it helps, I am partitioning space for a ray-tracing program.

Every object in the scene is surrounded by a BoundingBox (for fast intersection). So I have a class called BoundedObject. A BoundedObject can be anything, but it must have a BoundingBox. A BoundingBox is simply 2 x,y,z points in space .

I am sorting the vector of objects the scene based on their BoundingBox.min atrribute - which has xyz coordinates.  I get an "illegal indirection" compile error at the spot marked below.

-----------------------------------------------------------------------------------------------------------
---test program- works in VC++ 6.0/win xp----------------------------------------------------------
-----------------------------------------------------------------------------------------------------------
#include <algorithm>
#include <vector>
#include <iostream>
#include <stdlib.h>
using namespace std;

class vector3
{
public: float x,y,z;
};

class BoundingBox // box surrounding an object specified by 2 points
{
public: vector3 max;
vector3 min;
};

class BoundedObject // an object in the scene, has a bounding box
{
public: // atributes like position....
// orientation....
// textures info...
// etc....

BoundingBox BBOX; // bounding box of the object
};

struct sortByBBoxMinX  // custom function for sorting
{
public: bool operator() (BoundedObject &a, BoundedObject &b)
{
return *a.BBOX.min.x < *b.BBOX.min.x; // illegal indirection compile error here
}
};

// sortByBBoxMinY

// sortByBBoxMinZ

void main(int argc, char* argv[])
{
vector<BoundedObject>ObjectList;  // vector i want to sort

for(int i=0; i<10; i++)  // initialize with some random numbers
{
BoundedObject BObj;

BObj.BBOX.min.x = -50.0f + (float)(rand()%100); // set BBOX min
BObj.BBOX.min.y = -50.0f + (float)(rand()%100);
BObj.BBOX.min.z = -50.0f + (float)(rand()%100);

ObjectList.push_back(BObj);
}

cout << "Unsorted:" << endl;
for(i=0; i<ObjectList.size(); i++) // print unsorted
{
cout      << "X: " << ObjectList[i].BBOX.min.x << " "
<< "Y: " << ObjectList[i].BBOX.min.y << " "
<< "Z: " << ObjectList[i].BBOX.min.z << endl;
}

sort(ObjectList.begin(), ObjectList.end(), sortByBBoxMinX() ); // heres the sort

cout << "Sorted:" << endl;
for(i=0; i<ObjectList.size(); i++) // print sorted
{
cout << "X: " << ObjectList[i].BBOX.min.x << " "
<< "Y: " << ObjectList[i].BBOX.min.y << " "
<< "Z: " << ObjectList[i].BBOX.min.z << endl;
}
}

------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------

So anyone see what the problem is? I need 3 similar functions to sort the vector of BoundedObjects by either BoundedObject.BBOX.min.x, BoundedObject.BBOX.min.y, BoundedObject.BBOX.min.z.
0

LVL 9

Accepted Solution

tinchos earned 125 total points
I guess that as a.BBOX.min.x is a float you should not use the * operator

try with

struct sortByBBoxMinX  // custom function for sorting
{
public: bool operator() (BoundedObject &a, BoundedObject &b)
{
return a.BBOX.min.x < b.BBOX.min.x; // illegal indirection compile error here
}
};

Hope this helps

Tincho
0

LVL 4

Author Comment

woot it works perfectly now. you rule tincho. hehe.

thanks for all the other comments from everyone else =)
0

LVL 86

Expert Comment

Um, sorry, but how was

Comment from jkr  Date: 04/10/2004 09:43PM CEST
>>Basically, what goes in the "????" spot

A predicate object like

class VERTEX3Sort {

public:
bool operator() ( const VERTEX3& a, const VERTEX3& b) {
return [true or false based on your sort criteria];
}
};

//...

sort(VertexList.begin(), VertexList.end(),  VERTEX3Sort() );

incorrect then?
0

LVL 4

Author Comment

I ran both. Seems like these 2 forms do exactly the same thing:

struct sortByBBoxMinX
{
public: bool operator() (BoundedObject &a, BoundedObject &b)
{
return a.BBOX.min.x < b.BBOX.min.x;
}
};

class sortByBBoxMinX
{
public: bool operator() (BoundedObject &a, BoundedObject &b)
{
return a.BBOX.min.x < b.BBOX.min.x;
}
};

sort(ObjectList.begin(), ObjectList.end(), sortByBBoxMinX() );

Both are equally ugly notation hehe but seem to work exactly the same. I guess maybe using a class over a struct as your customized sort function would make more "sense".
0

LVL 86

Expert Comment

I don't think you got my point...
0

## Featured Post

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generatâ€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.