Hello,

I´m wondering if the STL is offering a solution to this problem:

I´m building a chart from a sequence of arbitrary length. To avoid displaying multiple vertexes that share a common position I decided only to display vertexes that differ from every other vertexes by 5%. The brute force approach is to check new vertexes to all existing ones, which is painfully slow for huge numbers of vertexes (of course). After refining the data structure to a sorted container (in my case vector) of vertexes I can use a binary search algorithm on that container. Unfortunately there´s no binary_find_if or binary_search_if for containers that fits my needs, binary_search only returns true/false and lower_bound doesn´t work for reasons I already forgot

However, that´s the solution I came up with:
Code:
struct CloudVertex
{
   double  XValue;
   double  YValue;
   
   CloudVertex( double X, double Y ) :
      XValue( X ),
      YValue( Y )
   {
   }

   bool operator<( const CloudVertex& other ) const
   {
       if( XValue == other.XValue )
       {
          return YValue < other.YValue;
       }
       return XValue < other.XValue;
   }
};

struct VertexVicinityComparator
{
   double XTolerance;
   double YTolerance;

   VertexVicinityComparator( double XTol, double YTol ) :
      XTolerance( fabs( XTol ) ),
      YTolerance( fabs( YTol ) )      
   {
   }

   bool operator()( const CloudVertex& op1, const CloudVertex& op2 ) const
   {
      bool bPartX = false;
      bool bPartY = false;

      if( 0 == op1.XValue )
      {
         bPartX = op2.XValue == 0;
      }
      else
      {
         bPartX = fabs( (fabs( op1.XValue - op2.XValue ) / op1.XValue) ) < XTolerance;
      }
      if( 0 == op1.YValue )
      {
         bPartY = op2.YValue == 0;
      }
      else
      {
         bPartY = fabs( (fabs( op1.YValue - op2.YValue ) / op1.YValue) ) < YTolerance;
      }
      return bPartX && bPartY;
   }
};

// binary_search_if function
template<typename IteratorType, typename value, typename Predicate>
IteratorType binary_search_if( IteratorType first, IteratorType last,
                                 const value& val, Predicate pred )
{
   IteratorType end = last;

   int len = distance( first, last );

   while( len > 0 )
   {
      IteratorType mid = first;
      advance( mid, len /2 );

      if( true == pred( *mid, val ) )
      {
         return mid;
      }
      else
      {
         // exclude mid from range
         if( val < *mid )
         {
            // search left interval
            advance( mid, -1 );
            last = mid;
         }
         else
         {
            // search right interval
            advance( mid, 1 );
            first = mid;
         }
         len = distance( first, last );
      }
   }
   if( first != end && true == pred( *first, val ) )
   {
      return first;
   }
   return end;
}

// this is my insertion code
void insert_vertex( double X, double Y )
{
   // both tolerances set to 5%
   VertexVicinityComparator Comparator( 0.05, 0.05 );
   CloudVertex Vertex( X, Y );

   std::vector<CloudVertex>::iterator pos;
   pos  = binary_search_if( AllVertexes.begin(), AllVertexes.end(), Vertex, Comparator );
   if( AllVertexes.end() == pos )
   {
      // Vertex must be inserted 
     pos = lower_bound( AllVertexes.begin(), AllVertexes.end(), Vertex, Comparator );
     AllVertexes.insert( pos, Vertex );
   }
}
I think there´s plenty of room for improvement since vector has to move its elements when there´s an elemented inserted. Unfortunately neither set or map offer a find_if method for lookup and I´m wondering if there´s a better solution to this.

I know this won´t compile, but I think the code helps to explain my problem.