Hi,

Google is being rather unhelpful, as any search for "sorting vectors" inevitably results in std::sort because the unfortunate name of a dynamic array in C++ is "vector".

I wish to sort the following data structure(s) contained withing a list:

struct Vector2
{
   int x;
   int y;
};
struct Vector3
{
   int x;
   int y;
   int z;
};

The more I play around with the implementation of the overloaded comparison operators, the more I'm lead to believe it's simply not possible to perform the check "A<B" where A and B are both Vector2 or Vector3 objects.

Here's an example program thingy to play around with:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>


template <class T>
class Vector2
{
public:
    Vector2() {}
    Vector2( int x, int y ) : x(x), y(y) {}
    ~Vector2() {}
    int x;
    int y;
    template <class T_> friend inline bool operator==( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator!=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator< ( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator> ( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator<=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
    template <class T_> friend inline bool operator>=( const Vector2<T_>& lhs, const Vector2<T_>& rhs );
};


template <class T>
inline bool operator==( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return ( lhs.x==rhs.x && lhs.y==rhs.y );
}
template <class T>
inline bool operator!=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator==( lhs, rhs );
}
template <class T>
inline bool operator<( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    if( lhs.x>=rhs.x ) return false;
    if( lhs.y>=rhs.y ) return false;
    return true;
}
template <class T>
inline bool operator>( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return operator<( rhs, lhs );
}
template <class T>
inline bool operator<=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator>( lhs, rhs );
}
template <class T>
inline bool operator>=( const Vector2<T>& lhs, const Vector2<T>& rhs )
{
    return !operator<( lhs, rhs );
}


int main()
{


        std::vector< Vector2<int> > myListOfVectors;
        for( int n = 0; n != 10; ++n )
                myListOfVectors.push_back( Vector2<int>(rand()%100,rand()%100) );


        std::sort( myListOfVectors.begin(), myListOfVectors.end() );


        for( std::vector< Vector2<int> >::iterator it = myListOfVectors.begin(); it != myListOfVectors.end(); ++it )
                std::cout << it->x << "," << it->y << std::endl;


        return 0;
}

Any help?

Thanks for the quick reply!

For higher dimensions, would this be correct?

template <class T>
inline bool operator<( const Vector3<T>& lhs, const Vector3<T>& rhs )
{
if (lhs.x < rhs.x) return true;
if (lhs.x > rhs.x) return false;
if( lhs.y < rhs.y) return true;
if( lhs.y > rhs.y) return false;
return lhs.z < rhs.z
}

Yes, that looks right. Note that while this is a valid comparison for the purposes of sorting, it may not be a particularly meaningful sort. In particular when used with floating point numbers, it may not be useful for search.

Noted, thanks.

The purpose of all this is to decrease a bottleneck I have with quickly searching a grid for the existence of an entity. I decided to insert the integer coordinates of the entities I'm interested in into a sorted list so I can do a binary search on the data (O(log n)) instead of having to traverse it (O(n)). The list has well over a thousand entries, so hope this will be more effective.

You could create a sort method that takes in a lambda expression so you can sort differently depending on your case. I can envision a lot of ways to sort vectors (by length, by coordinate, by dot product with another vector, etc.) so you might want to keep your options open.

Sorting by length and dot product is ambiguous, for instance: vec2(1,1).length() == vec2(-1,-1).length(). I can imagine this would require a more elaborate search algorithm, as I think one of the requirements of binary search is each entry in the list needs to be unique.

You're looking for an ordering function.

Sorting by length and dot product is ambiguous, for instance: vec2(1,1).length() == vec2(-1,-1).length(). I can imagine this would require a more elaborate search algorithm, as I think one of the requirements of binary search is each entry in the list needs to be unique.

For your purposes, lexicographic order sounds right, but other purposes other kinds of ordering might be better -- for example, if the question is "does an entity exist at X,Y" lexicographic ordering is good, but if the question was "which entities are located between 3 and 5 units from X, Y" then length (defined as distance from X,Y) is good.

In general, binary searches have to deal with ambiguity in some way -- as in the list [1,2,3,3,4,5] -- if the result is 3, which 3? In some cases it may not matter to you which 3 is returned or the one returned by convention happens to be the one you're interested in, but if it does matter to you, you might need to apply further criteria.

Dot product ordering is good if you want to sweep a cone out too and have all the narrowest angles come up first.