How to sort arrays on class members?

[realmsinthemists]

Refrasing the question: How to sort an array of pointers to classes on the class its members, or better yet to members of a member (cCharacter::_properties::these_members)?

There are probably a lot of examples on sorting to find all around the internet. However I'd like to keep things within irrlicht first to understand entirely the engine.

Code: Select all

 
    // truncated class
    class cCharacter
    {
    public:
        ...
 
        struct sProperties
        {
 
            irr::core::stringw      _name_first;
            irr::core::stringw      _name_last;
 
            irr::s32                _age_in_days; // just a unixtime style date
            irr::s32                _date_of_birth; // just a unixtime style date
 
            ...
 
        };
 
    /* protected: <-- inconvenient for now */
        class cApplication*         _application;
        cCharacterManager*          _manager;
        irr::s32                    _identifier; // unique identifier of this class withhin the array
 
    /* DATA TO SORT WITHIN ITS CONTAINER -> cCharacterManager::_characters */
    sProperties                 _properties; 
    sProperties                 _properties_old; // track what has changed
 
    };
 
    typedef irr::core::array<class cCharacter*> cCharacterArray;
    
    class cCharacterManager
    {
    protected:
        cCharacterArray _characters;
    }
 

The sorted should be done as follows:

_name_last
or...
_date_of_birth
or...
_name_last; then _date_of_birth

whatever, you'll get it.

Having copied the heapsort and heapsink templates into a convenient place and renamed them; templates removed (as for now).

Code: Select all

 
    //! Sinks an element into the heap.
    void charsink( cCharacter** array, irr::s32 element, irr::s32 max )
    {
        while( ( element << 1 ) < max ) // there is a left child
        {
            s32 j = ( element << 1 );
 
            if( j + 1 < max && array[ j ] < array[ j + 1 ] )
                j = j + 1; // take right child
 
            if( array[ element ] < array[ j ] )
            {
                cCharacter* t = array[ j ]; // swap elements
                array[ j ] = array[ element ];
                array[ element ] = t;
                element = j;
            }
            else
                return;
        }
    }
 
 
    //! Sorts an array with size 'size' using heapsort.
    inline void charsort( cCharacter** array_, s32 size )
    {
        // for heapsink we pretent this is not c++, where
        // arrays start with index 0. So we decrease the array pointer,
        // the maximum always +2 and the element always +1
 
        cCharacter** virtualArray = array_ - 1;
        s32 virtualSize = size + 2;
        s32 i;
 
        // build heap
 
        for( i = ( ( size - 1 ) / 2 ); i >= 0; --i )
            charsink( virtualArray, i + 1, virtualSize - 1 );
 
        // sort array, leave out the last element (0)
        for( i = size - 1; i>0; --i )
        {
            cCharacter* t = array_[ 0 ];
            array_[ 0 ] = array_[ i ];
            array_[ i ] = t;
            charsink( virtualArray, 1, i + 1 );
        }
    }

and calling it:

Code: Select all

 
        cCharacter** data = _characters.pointer();
        sortChar( data, sizeof( cCharacter ) * _characters.size() );
 

The outcome is, ofcourse, the same as calling: _characters.sort();

How to find the offset to (*(cCharacter**))->_properties and then those members?

r,

[CuteAlien]

In short - it's not easy to do with Irrlicht because Irrlicht's sort doesn't take custom functions. It works only with classes which have operator < defined. In theory you could wrap it - like using another struct which contains the pointer you need and then write an operator< in that struct (or class) which makes sure the content of your pointer is sorted.

Personally I tend to use STL for this (std::vector and sort from the algorithms header). Which takes any kind of functor.

[realmsinthemists]

Thanks for the reply.

Always thinking too difficult. ANd, eh, yes I'll keep it short too . Need to do something about my search on google too since I didn't new about the std::sort();

Can't find a way with the [operator<] to sort on different members (yet), so this is what I came up with. This can be used in for example a switch(){} to sort on different members and types.

Code: Select all

 
// just plain use of std::sort(...);
std::vector<cCharacter*> _characters;
...
std::sort( _characters.begin(), _characters.end(), []( cCharacter* const& a, cCharacter* const& b ) { return a->_properties._name_last < b->_properties._name_last; } );
 

Test sort on stringw:

Code: Select all

 
size() = 500000 -> 1.149 seconds
size() =   5000 -> 0.006 seconds
 

[kornwaretm]

to define an operator, just put the implementation like this to override the operator

Code: Select all

 
class yourClass
{
   .............
   bool operator<(const yourClass &other)
   {
        return this.attributeValue < other.attributeValue;
   }
   ..............
};
 

this way you now can control the irr::core::array<yourClass>.sort() works. i'm not sure but i think you have to do < , > , >= , <= operators ?

[CuteAlien]

@kornwaretm: Sort in STL only needs operator< but in his case it's a little tricky because he only has pointers to objects (so overloading won't work for sort). But using lambdda as he did now is pretty perfect (old alternative would have been a functor, but I prefer lambdas most of the time).