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

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!
LVL 4
Fippy_DarkpawAsked:
Who is Participating?
 
tinchosConnect With a Mentor Commented:
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
 
tinchosCommented:
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
 
tinchosCommented:
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
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

 
monkesdbCommented:
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
 
dkloeckCommented:
//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
 
jkrCommented:
>>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
 
monkesdbCommented:
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
 
monkesdbCommented:
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
 
Fippy_DarkpawAuthor Commented:
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
 
Fippy_DarkpawAuthor Commented:
woot it works perfectly now. you rule tincho. hehe.

thanks for all the other comments from everyone else =)
0
 
jkrCommented:
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
 
Fippy_DarkpawAuthor Commented:
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
 
jkrCommented:
I don't think you got my point...
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.