CODEWITHSUNDEEP
c++algorithmstl
Avinash
Avinash

Reputation: 13257

sorting based on x and y co-ordinate

I want to sort a vector based on the x and y co-ordinate . Following is what I have done, but what I want is when I sort based on x , I get proper , but when I go for sorting based on y, i do not want my x order should change.

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

struct item_t {
    int x;
    int y;
    item_t( int h, int w ) : x(h), y(w) {}
    friend std::ostream& operator<<(std::ostream& os, const item_t& gt) {
        os << "(" << gt.x << "," << gt.y << ")";
        return os;
    }
};
typedef std::vector<item_t> item_list_t;
typedef item_list_t::iterator item_list_itr_t;

struct compare_x {
    bool operator ()(const item_t& left, const item_t& rigx) const {
        return left.x < rigx.x;
    }
};
struct compare_y {
    bool operator ()(const item_t& left, const item_t& rigx) const {
        return left.y < rigx.y;
    }
};

int main ( int argc, char **argv) { 
    item_list_t items;

    items.push_back(item_t(15, 176));
    items.push_back(item_t(65, 97));
    items.push_back(item_t(72, 43));
    items.push_back(item_t(102, 6));
    items.push_back(item_t(191, 189));
    items.push_back(item_t(90, 163));
    items.push_back(item_t(44, 168));
    items.push_back(item_t(39, 47));
    items.push_back(item_t(123, 37));

    std::sort( items.begin(), items.end(), compare_x());
    std::copy(items.begin(),items.end(), std::ostream_iterator<item_t>(std::cout," ") );
    std::cout << std::endl;

    std::sort( items.begin(), items.end(), compare_y());
    std::copy(items.begin(),items.end(), std::ostream_iterator<item_t>(std::cout," ") );

    std::cout << std::endl;

}

What I want given a set of points orders in increasing order. i.e. x and y both are increasing.

Upvotes: 2

Views: 4007

Answers (3)

Luca Martini
Luca Martini

Reputation: 1474

You have to create only one comparator and only one call to std::sort:

struct compare_xy {
    bool operator ()(const item_t& left, const item_t& right) const {
        return (left.x < right.x) || ((left.x == right.x) && (left.y < right.y));
    }
};

Upvotes: 4

James Kanze
James Kanze

Reputation: 153909

It's not totally clear to me what you're asking. If your goal is to sort by y, with x determining the order when the y's are equal, then a single call to sort with a comparison function:

struct OrderYThenX
{
    bool operator()( item_t const& lhs, item_t const& rhs ) const
    {
        return lhs.y < rhs.y
            || (!(rhs.y < lhs.y) && lhs.x < rhs.x);
    }
};

This will result in items having the same order as it finally has in your code.

If, as seems more likely from parts of your description and your example, you want the order between objects with equal ys to be unchanged when you sort by y, regardless of how the values were ordered with respect to x, you should use std::stable_sort. Just be aware that it could be slower than std::sort.

Upvotes: 1

Mat
Mat

Reputation: 206689

You should do the sort in a single pass:

struct compare_xy {
    bool operator ()(const item_t& left, const item_t& right) const {
        return (left.x == right.x ? left.y < right.y : left.x < right.x);
    }
};

Upvotes: 6

Related Questions