Solved

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

Posted on 2004-04-10
13
22,338 Views
Last Modified: 2013-12-14
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
Comment
Question by:Fippy_Darkpaw
  • 3
  • 3
  • 3
  • +2
13 Comments
 
LVL 9

Expert Comment

by:tinchos
Comment Utility
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

by:tinchos
Comment Utility
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

by:monkesdb
Comment Utility
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

by:dkloeck
Comment Utility
//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

by:jkr
Comment Utility
>>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

by:monkesdb
Comment Utility
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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
LVL 3

Expert Comment

by:monkesdb
Comment Utility
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

by:Fippy_Darkpaw
Comment Utility
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

by:
tinchos earned 125 total points
Comment Utility
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

by:Fippy_Darkpaw
Comment Utility
woot it works perfectly now. you rule tincho. hehe.

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

Expert Comment

by:jkr
Comment Utility
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

by:Fippy_Darkpaw
Comment Utility
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

by:jkr
Comment Utility
I don't think you got my point...
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now