Làm cách nào để sắp xếp vectơ các cặp dựa trên phần tử thứ hai của cặp?

Question

Nếu tôi có một vector của các cặp:

std::vector<std::pair<int, int> > vec; 

Có và cách dễ dàng để sắp xếp danh sách theo thứ tự tăng dựa trên các yếu tố thứ hai của cặp?

Tôi biết tôi có thể viết một đối tượng hàm nhỏ sẽ thực hiện công việc, nhưng có cách nào để sử dụng các phần hiện có của STL và std::less để thực hiện công việc trực tiếp không?

EDIT: Tôi hiểu rằng tôi có thể viết một hàm hoặc lớp riêng để chuyển đến đối số thứ ba để sắp xếp. Câu hỏi đặt ra là liệu tôi có thể xây dựng nó ra khỏi công cụ tiêu chuẩn hay không. Tôi thực sự cái gì đó trông giống như:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>()); 

Answer 1

Bạn có thể sử dụng tăng như thế này:

std::sort(a.begin(), a.end(), 
      boost::bind(&std::pair<int, int>::second, _1) < 
      boost::bind(&std::pair<int, int>::second, _2)); 

Tôi không biết một cách tiêu chuẩn để làm điều này bằng nhau ngắn gọn và súc tích, nhưng bạn có thể lấy boost::bind tất cả đều bao gồm tiêu đề.

Answer 2

Bạn sẽ phải dựa vào một tiêu chuẩn không select2nd

Answer 3

EDIT: sử dụng C++ 14, giải pháp tốt nhất là rất dễ dàng để viết nhờ để lambdas mà bây giờ có thể có các tham số của loại auto. Đây là giải pháp của tôi yêu thích hiện nay

std::sort(v.begin(), v.end(), [](auto &left, auto &right) { 
    return left.second < right.second; 
}); 

---

Chỉ cần sử dụng một so sánh tùy chỉnh (đó là một cuộc tranh cãi 3 tùy chọn để std::sort)

struct sort_pred { 
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) { 
     return left.second < right.second; 
    } 
}; 

std::sort(v.begin(), v.end(), sort_pred()); 

Nếu bạn đang sử dụng một trình biên dịch C++ 11 , bạn có thể viết cùng một cách sử dụng lambdas:

std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) { 
    return left.second < right.second; 
}); 

EDIT: để đáp ứng với sửa đổi của bạn cho câu hỏi của bạn, sau đây là một vài suy nghĩ ... nếu bạn thực sự muốn được sáng tạo và có khả năng tái sử dụng khái niệm này rất nhiều, chỉ cần làm cho một mẫu:

template <class T1, class T2, class Pred = std::less<T2> > 
struct sort_pair_second { 
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) { 
     Pred p; 
     return p(left.second, right.second); 
    } 
}; 

sau đó bạn có thể làm điều này quá:

std::sort(v.begin(), v.end(), sort_pair_second<int, int>()); 

hoặc thậm chí

std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >()); 

Mặc dù phải trung thực, đây là tất cả một chút quá mức cần thiết, chỉ cần viết các chức năng dòng 3 và được thực hiện với nó :-P

Answer 4

Đối với một cái gì đó tái sử dụng:

template<template <typename> class P = std::less > 
struct compare_pair_second { 
    template<class T1, class T2> bool operator()(const std::pair<T1, T2>& left, const std::pair<T1, T2>& right) { 
     return P<T2>()(left.second, right.second); 
    } 
}; 

Bạn có thể sử dụng nó như

std::sort(foo.begin(), foo.end(), compare_pair_second<>()); 

hoặc

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>()); 

Answer 5

Với C++ 0x chúng ta có thể sử dụng chức năng lambda:

using namespace std; 
vector<pair<int, int>> v; 
     . 
     . 
sort(v.begin(), v.end(), 
    [](const pair<int, int>& lhs, const pair<int, int>& rhs) { 
      return lhs.second < rhs.second; }); 

Trong ví dụ này, kiểu trả về bool được suy luận ngầm.

Lambda kiểu trả về

Khi một lambda chức năng có một tuyên bố duy nhất, và đây là một sự trở lại-tuyên bố, trình biên dịch có thể suy ra kiểu trả về. Từ C++ 11, §5.1.2/4:

...

• Nếu hợp chất-tuyên bố có dạng { return expression ; } kiểu của biểu thức trở lại sau khi giá trị trái-to-rvalue chuyển đổi (4.1), chuyển đổi mảng-thành-con trỏ (4.2) và chuyển đổi hàm-to-con trỏ (4.3);
• nếu không, void.

Để chỉ định rõ kiểu dữ liệu trở lại sử dụng mẫu []() -> Type { }, như trong:

sort(v.begin(), v.end(), 
    [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool { 
      if (lhs.second == 0) 
       return true; 
      return lhs.second < rhs.second; }); 

Answer 6

của nó khá đơn giản bạn sử dụng chức năng sắp xếp từ thuật toán và thêm chức năng riêng so sánh của bạn

vector< pair<int,int > > v; 
sort(v.begin(),v.end(),myComparison); 

Bây giờ bạn phải thực hiện so sánh dựa trên lựa chọn thứ hai để khai báo cho bạn "myComp arison "as

bool myComparison(const pair<int,int> &a,const pair<int,int> &b) 
{ 
     return a.second<b.second; 
} 

Answer 7

Hãy thử đổi phần tử của các cặp để bạn có thể sử dụng std::sort() như bình thường.