Trying to understand std::find and std::equal_range

[cmisip]

I am trying to see which Points are close ( within 5 pixels in both the x and y dimensions) to a specific point in a vector of points. I am getting different results with different permutations of the vector. I can see that the vectors are sorted differently each time.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x;
    int y;
    Point(int ix, int iy): x(ix), y(iy){};
    bool operator==(const Point &other){
        //return ((y == other.y ) && (x == other.x));
        return (y == other.y );
    }
    
    bool operator<(const Point &other) const{
        return ( (this->y+5) < other.y) || ( (this->y-5) > other.y) && ( (this->x+5) < other.x) || ( (this->x-5) > other.x) ;
    }  
    
    
    
};

int main(int argc, char** argv) {
    
    //Find out all values that are within 5 pixels of Point 6,7
    //Range would be for the y 7-5=2 to 7+5=12
    //Range would be for the x 6-5=3 to 6+5=11
    //Answer: {11,3}, {7,3}, {8,5}, {3,9} //x from 3 to 11, and y from 2 to 12
    
    Point value ( 6, 7 ); 
    
    //First permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> v = {{11,3}, {7,3}, {8,5}, {3,9}, {3,25}, {3,14}, {25,3}};
    
    std::cout << "ORIGINAL" << std::endl;
    for_each(v.begin(), v.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    sort(v.begin(), v.end());
    std::cout << std::endl<< "SORTED" << std::endl;
    for_each(v.begin(), v.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    auto p = std::equal_range(v.begin(),v.end(),value);
    std::cout << "Equal range" << std::endl;
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->x << ',' << i->y << " " << std::endl;
    
    //Second permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> w = {{3,25}, {3,14}, {25,3}, {11,3}, {7,3}, {8,5}, {3,9} };
   
    std::cout << "ORIGINAL" << std::endl;
    for_each(w.begin(), w.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    sort(w.begin(), w.end());
    std::cout << std::endl<< "SORTED" << std::endl;
    for_each(w.begin(), w.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    
     p = std::equal_range(w.begin(),w.end(),value);
    std::cout << "Equal range" << std::endl;
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->x << ',' << i->y << " " << std::endl;
    
    //Third permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> x = {{25,3}, {11,3}, {7,3}, {3,25}, {3,14},  {8,5}, {3,9} };
    
    std::cout << "ORIGINAL" << std::endl;
    for_each(x.begin(), x.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    sort(x.begin(), x.end());
    std::cout << std::endl<< "SORTED" << std::endl;
    for_each(x.begin(), x.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    
     p = std::equal_range(x.begin(),x.end(),value);
    std::cout << "Equal range" << std::endl;
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->x << ',' << i->y << " " << std::endl;
    
	return 0;
}

This is the output that I get:

ORIGINAL
11,3 7,3 8,5 3,9 3,25 3,14 25,3 
SORTED
25,3 3,9 11,3 7,3 8,5 3,14 3,25 
Equal range
3,9 
11,3 
7,3 
8,5 
-------------------------------------------------------
ORIGINAL
3,25 3,14 25,3 11,3 7,3 8,5 3,9 
SORTED
3,9 25,3 11,3 7,3 8,5 3,14 3,25 
Equal range
11,3 
7,3 
8,5 
-------------------------------------------------------
ORIGINAL
25,3 11,3 7,3 3,25 3,14 8,5 3,9 
SORTED
8,5 3,14 3,25 25,3 11,3 7,3 3,9 
Equal range
11,3 
7,3 
3,9 

I think the key is to get the proper operator== algorithm that results in the same sorting all the time. Any ideas on how I could arrive at the same result with whatever vector permutations?

Thanks,
Chris

[JLBorges]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <utility>

struct point : std::pair<int,int>
{
    using std::pair<int,int>::pair ;

    int& x() { return first ; }
    constexpr int x() const { return first ; }
    int& y() { return second ; }
    constexpr int y() const { return second ; }

    friend std::ostream& operator<< ( std::ostream& stm, point pt )
    { return stm << '(' << pt.x() << ',' << pt.y() << ')' ; }
};

unsigned int max_delta( point a, point b ) // max of delta x, delta y
{ return std::max( std::abs( a.x() - b.x() ), std::abs( a.y() - b.y() ) ) ; }

std::vector<point> get_nearby_points( std::vector<point> pts, point from, unsigned int delta = 5 )
{
    const auto is_nearby = [delta,from] ( point pt ) { return max_delta( pt, from ) <= delta ; };
    return { pts.begin(), std::partition( pts.begin(), pts.end(), is_nearby ) };
}

int main()
{
    std::vector<point> vec = { {11,3}, {7,3}, {8,5}, {3,9}, {3,25}, {3,14}, {25,3} };
    std::cout << "                 original: " ;
    for( auto pt : vec ) std::cout << pt << ' ' ;
    std::cout << '\n' ;

    const point my_pt { 5, 5 } ;

    // get all points within 5 pixels (in both the x and y dimensions) from my_pt
    const auto neighbours = get_nearby_points( vec, my_pt ) ;
    std::cout << "               neighbours: " ;
    for( auto pt : neighbours ) std::cout << pt << ' ' ;
    std::cout << '\n' ;

    // sort using operator< of pair: sort on ascending x (primary), ascending y (secondary)
    std::sort( vec.begin(), vec.end() ) ;
    std::cout << "            sorted on x,y: " ;
    for( auto pt : vec ) std::cout << pt << ' ' ;
    std::cout << '\n' ;


    // sort on max_delta from my_pt
    const auto cmp_delta = [my_pt]( point a, point b )
    { return max_delta(a,my_pt) < max_delta(b,my_pt) ; };
    std::sort( vec.begin(), vec.end(), cmp_delta ) ;
    std::cout << "sorted on neighbourliness: " ;
    for( auto pt : vec ) std::cout << pt << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/672c2d6e231c8b76

[cmisip]

It will take me some time to digest this but it did give some ideas that I did not consider because I simply was not exposed to the possibilities.

I am looking for the fastest implementation because I need to integrate it into a realtime video processing system and it seems std::partition is the answer using a lambda function. std::sort and std::equal_range is a two step solution. It would be better if std::sort simply gave me a sub vector with the appropriate elements, and it seems this is what std::partition does. Here is my reworked code. I hope there are no errors.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: cmisip
 *
 * Created on June 6, 2017, 10:46 PM
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

struct Point {
    int x;
    int y;
    Point(int ix, int iy): x(ix), y(iy){};
    
    bool operator<(const Point &other) const{
        return ( (this->y+5) < other.y) || ( (this->y-5) > other.y) && ( (this->x+5) < other.x) || ( (this->x-5) > other.x) ;
    }  
};

 bool myfunction(Point a, Point b){
     //sort according to manhattan distance
    Point p(6,7);
    return (( abs(a.x -p.x) + abs(a.y-p.y) ) < (abs(b.x -p.x) + abs(b.y-p.y)));
}

int main(int argc, char** argv) {
    
    //Find out all values that are within 5 pixels of Point 6,7
    //Range would be for the y 7-5=2 to 7+5=12
    //Range would be for the x 6-5=3 to 6+5=11
    //Answer: {11,3}, {7,3}, {8,5}, {3,9} //x from 3 to 11, and y from 2 to 12
    
    Point pt( 6, 7 );
    
    //First permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> v = {{11,3}, {7,3}, {8,5}, {3,9}, {3,25}, {3,14}, {25,3}};
    
    std::cout << "ORIGINAL" << std::endl;
    for_each(v.begin(), v.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    sort(v.begin(), v.end(), [pt](Point a, Point b){return (( abs(a.x -pt.x) + abs(a.y-pt.y) ) < (abs(b.x -pt.x) + abs(b.y-pt.y)));  }); //manhattan distance lambda
    std::cout << std::endl<< "SORTED" << std::endl;
    for_each(v.begin(), v.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    auto p = std::equal_range(v.begin(),v.end(),pt);
    std::cout << "Equal range" << std::endl;
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->x << ',' << i->y << " " << std::endl;
    
    //Second permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> w = {{3,25}, {3,14}, {25,3}, {11,3}, {7,3}, {8,5}, {3,9} };
   
    std::cout << "ORIGINAL" << std::endl;
    for_each(w.begin(), w.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    sort(w.begin(), w.end(),myfunction); //manhattan distance in a function
    std::cout << std::endl<< "SORTED" << std::endl;
    for_each(w.begin(), w.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    
     p = std::equal_range(w.begin(),w.end(),pt);
    std::cout << "Equal range" << std::endl;
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->x << ',' << i->y << " " << std::endl;
    
    //Third permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> x = {{25,3}, {11,3}, {7,3}, {3,25}, {3,14},  {8,5}, {3,9} };
    
    auto it = std::partition(x.begin(), x.end(), [pt](Point i){ return ( (abs(pt.x - i.x) + abs(pt.y -i.y)) < 10 ); }); // predicate that prioritizes a manhattan distance of < 10
    std::cout << "ORIGINAL" << std::endl;
    for_each(x.begin(), x.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << "\nPartitioned vector:\n    ";
    for_each(x.begin(), it, [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
    
    //Fourth permutation
    std::cout << "-------------------------------------------------------" << std::endl;
    std::vector<Point> z = {{3,14},  {8,5}, {25,3}, {11,3}, {7,3}, {3,25},  {3,9} };
    
    it = std::partition(z.begin(), z.end(), [pt](Point i){ return ( (abs(pt.x - i.x) + abs(pt.y -i.y)) < 10 ); }); // just to see if I still get the same results
    std::cout << "ORIGINAL" << std::endl;
    for_each(z.begin(), z.end(), [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << "\nPartitioned vector:\n    ";
    for_each(z.begin(), it, [](Point n){std::cout << n.x << "," << n.y << " "; });
    std::cout << std::endl;
    
	return 0;
}

This is now the only part of the code I need to migrate to my video processing project.

auto it = std::partition(vert_points.begin(), vert_points.end(), [j,min_vector_cluster_distance](cv::Point i){ return ( (abs(j.x - i.x) + abs(j.y -i.y)) < min_vector_cluster_distance ); });
                           if ((it-vert_points.begin()) > min_vectors_filter) //vector is close to other vectors 

Thanks,
Chris

[JLBorges]

> it seems std::partition is the answer using a lambda function.
> std::sort and std::equal_range is a two step solution.

The complexity of std::sort is O(N·log(N)) and the complexity of std::partition is O(N)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iterator>

struct point
{
    int x = 0 ;
    int y = 0 ;

    friend std::ostream& operator<< ( std::ostream& stm, point pt )
    { return stm << '(' << pt.x << ',' << pt.y << ')' ; }
};

struct is_nearby
{
    static unsigned int max_delta( point a, point b )
    { return std::max( std::abs( a.x - b.x ), std::abs( a.y - b.y ) ) ; }

    bool operator() ( point pt ) const // unary predicate for partition
    { return max_delta( pt, target ) <= allowed_delta ; }

    point target ;
    unsigned int allowed_delta ;
};

int main()
{
    point target{ 6, 7 } ;
    std::ostream_iterator<point> stdout_iter( std::cout, " " ) ;

    std::vector<point> vec{ {11,3}, {3,14}, {7,3}, {3,25}, {1,12}, {8,5}, {3,9}, {25,3} };
    std::copy( vec.begin(), vec.end(), stdout_iter ) ;
    std::cout << '\n' ;

    const auto partition_end = std::partition( vec.begin(), vec.end(), is_nearby{ target, 5 } ) ;
    std::copy( vec.begin(), partition_end, stdout_iter ) ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/71cd8db6425e5265

[cmisip]

I am still working on other parts of the code and have not gotten to integrating this yet. I am trying to keep the thread from archiving.

Thanks,
Chris