Solved

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

Posted on 2004-04-10
13
22,342 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
ID: 10798024
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
ID: 10798049
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
ID: 10798056
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
ID: 10798064
//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
ID: 10798065
>>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
ID: 10798222
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 3

Expert Comment

by:monkesdb
ID: 10798233
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
ID: 10799803
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
ID: 10800034
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
ID: 10800064
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
ID: 10801373
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
ID: 10801424
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
ID: 10801488
I don't think you got my point...
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
mixing C++ & C# in Vis Studio 2013 7 141
C++ finding a sting in a char* string from a text file 3 99
eclipse compiler vs Installed JREs option 3 77
Angular JS Route 3 54
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

862 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

21 Experts available now in Live!

Get 1:1 Help Now