сортировка по координатам x и y

Question

Я хочу отсортировать vector на основе координат x и y. Вот что я сделал, но то, что я хочу, это когда я сортирую по x, у меня все получается, но когда я иду к сортировке по y, я не хочу, чтобы мой x порядок изменился. 1007 *

#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;

}

Что я хочу, учитывая набор пунктов заказов в порядке возрастания. то есть x и y оба увеличиваются.

Answer 1

Вы должны сделать сортировку за один проход:

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);
    }
};

Answer 2

Вы должны создать только один компаратор и только один вызов 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));
    }
};

Answer 3

Мне не совсем понятно, о чем ты спрашиваешь.Если ваша цель состоит в сортировке по y, с x определением порядка, когда y равны, то один вызов для сортировки с функцией сравнения:

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);
    }
};

Это будетв результате items будет иметь тот же порядок, что и в конечном итоге в вашем коде.

Если, как кажется более вероятным из частей вашего описания и вашего примера, вам нужен порядок между объектами с равными y sчтобы быть неизменным при сортировке по y, независимо от того, как были упорядочены значения относительно x, следует использовать std::stable_sort.Просто знайте, что это может быть медленнее, чем std::sort.