Are pointers the best way?

[cire]

So, somehow I ended up watching a video animation of a sort working on youtube, and I thought it might be interesting to emulate it in SFML. To that end I've implemented the ToSort class.

The ToSort class has a static data member that is a pointer to a function (or a functor) update_func which is called every time a ToSort object is assigned to, moved to or constructed from another ToSort object. This allows me to keep track of when an object is updated in the merge sort function.

The pointer magic, I believe, invokes some implementation defined behavior (I'm comparing pointers that don't necessarily point to the same array.) What I'm wondering is if anyone knows of a better (more portable) approach that doesn't require mucking about with the source for the merge sort function? You can find the pointer stuff in the private members of ToSort.

#include <vector>
#include <limits>
#include <functional>

const unsigned nullindex = std::numeric_limits<unsigned>::max() ;

class ToSort
{
public:
    static std::function<void(unsigned,unsigned, unsigned)> update_func ;
 
    ToSort(const std::vector<ToSort>& v, unsigned id) ;
    ToSort(const ToSort & c);
    ToSort(ToSort && c) ;

    ToSort& operator=(ToSort&&c) ;
    ToSort& operator=(const ToSort& c) ;

    operator unsigned() const { return _id ; } 

private:
    
    const std::vector<ToSort>* _container ;
    unsigned _id ;
    unsigned _prev_pos ;


    void _update_notify() const ;
    bool _in_container() const ;
    unsigned _container_pos() const ;
};


#endif  

#include <vector>
#include <limits>
#include "tosort.h"

 std::function<void(unsigned,unsigned, unsigned)> ToSort::update_func = nullptr ;

 ToSort::ToSort(const std::vector<ToSort>& v, unsigned id)
     : _container(&v), _id(id), _prev_pos(nullindex)
 {
 }

 ToSort::ToSort(const ToSort& c)
     : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
 {
    _update_notify() ;
 }

 ToSort::ToSort(ToSort&& c)
     : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
 {
     _update_notify() ;
 }

 ToSort& ToSort::operator=(ToSort&&c)
 {
     *this = c ;
     c._container = nullptr ;
     return *this ;
 }

 ToSort& ToSort::operator=(const ToSort& c)
 {
     _container = c._container ;
     _id = c._id ;
     _prev_pos = c._container_pos() ;
     _update_notify() ;
     return *this ;
 }

 void ToSort::_update_notify() const
 {
     if ( update_func != nullptr && _container != nullptr )
         update_func(_container_pos(), _id, _prev_pos) ;
 }

 // if we append or push a ToSort to the end of a container,
 // _in_container() may be called before the container has updated
 // its size to reflect the addition, so if this is one past the end
 // of the container we will consider it to be in the container.
 bool ToSort::_in_container() const 
 {
     if ( _container == nullptr )
         return false ;

    ToSort const * array = _container->data() ;

    if ( this >= array && array + _container->size() >= this )
        return true ;

    return false ;
 }

unsigned ToSort::_container_pos() const
{
    if ( _in_container() )
        return this - _container->data() ;
    else
        return nullindex ;
}

If you're interested to see how this interacts with the sort code, you can find the full source code at http://pastebin.com/GPsCwTLj That's been edited so that you should be able to cut and paste into one monolithic file for convenience. Note I haven't implemented anything with SFML yet, this was testing prior to that.

[JLBorges]

> The pointer magic, I believe, invokes some implementation defined behavior
> (I'm comparing pointers that don't necessarily point to the same array.)

A comparison for equality is p1 == p2 is defined.
IIRC, p1 < p2 etc. results in unspecified behaviour if they point to different objects that are not elements of the same array (or non-static members of the same object).



> What I'm wondering is if anyone knows of a better (more portable) approach that doesn't require mucking about with the source for the merge sort function?

An in-place merge sort with std::inplace_merge(), perhaps.

An alternative would be to sort a sequence with unique values (and then use values instead of pointers to track movement)

std::vector<int> seq ;
for( int i = 0 ; i < 100 ; ++i ) seq.push_back(i) ;
std::random_shuffle( seq.begin(), seq.end() ) ;
// sort seq 

[cire]

Thanks for the input.

I was half-thinking the source could serve as a dual-purpose example (both of how to use SFML and how to implement a non-recursive merge sort algorithm,) which is why I used my own merge sort implementation. Of course, it was late and I was a little loopy when the idea occurred to me, and I'm now questioning the idea of whether that would be useful for anyone or not. Reservations aside, though...

I did briefly consider using unique values to track the positions, but the pointer solution seemed more elegant (and much more efficient, yes -- I know -- premature optimization.)

I stubmled across Jerry Coffin's answer at http://stackoverflow.com/questions/4909766/is-it-unspecified-behavior-to-compare-pointers-to-different-arrays-for-equality and it looks like I should be able to rework the code to use the std:: template comparison without depending on the unspecified behavior.