Hỏi về cách sắp xếp pair

#1

Em hỏi cách sắp xếp dữ liệu pair với ạ.

Ví dụ sắp xếp theo giá trị tăng dần của phần tử thứ 2

bool cmp (chỗ này ghi gì ạ){
        return(a.second < b.second);
}

int main(){
        sort(a+1, a+n+1, cmp());
}

đại loại gì vậy mọi người giúp em với

#2

Bình thường sort số dạng pair thì nó ưu tiên sort theo first trước. Nếu bạn viết như vậy thì nó sẽ sort ưu tiên second nào nhỏ hơn trước.
VD: (3, 1) ; (7, 6) ; (2, 5);
Nếu sort bình thường thì sẽ được: (2, 5); (3, 1); (7, 6);
còn theo cách trên sẽ là: (3, 1); (2, 5); (7; 6);

4 Likes
#3

mình hiểu r nhưng k biết viết như nào ấy ạ giúp với

#4

mảng cmp so sánh các số dạng pair thì ghi pair thôi :v

bool cmp(pair <int, int> a, pair <int, int> b){
....
}
5 Likes
#5

Nên dùng lambda đỡ phải đặt tên :smiley: có thể bị trùng rất khó chịu.

4 Likes
#6

Cho mình hỏi là dùng lambda có khiến chương trình chạy chậm hơn so với tự viết ko?

#7

ko. Lambda là 1 đối tượng của anonymous struct có quá tải toán tử () thôi.

“hàm” trong C++ có 2 loại: free function và member function. Free function là hàm như hàm trong C. Member function là hàm thuộc về 1 struct/class nào đó. Nếu 1 struct/class có quá tải toán tử () thì đối tượng của struct/class đó có thể gọi obj(..) như gọi hàm f(..), và struct/class đó được gọi là function object :V

Lambda trong C++ là function object mà trình dịch tự đặt tên :V Nếu ko có “capture” gì thì tuy nó là function object nhưng khi được tối ưu thì hiệu năng của nó ko khác gì free function. Nếu có capture thì hiệu năng của nó cũng ko khác gì viết struct/class riêng có từng thuộc tính được captured ra :V

ví dụ mảng a = {1,2,3,4}, muốn đếm trong a các số > 2 ta có thể viết free function:

bool greaterThan2(int x) { return x > 2; }

rồi truyền vào hàm std::count_if:

int gt2Count = std::count_if(begin(a), end(a), greaterThan2);

nếu viết theo kiểu function object thì phải viết 1 struct

struct GreaterThan2 {
  bool operator()(int x) const { return x > 2; }
};

// sử dụng
GreaterThan2 gt2;
int gt2Count = std::count_if(begin(a), end(a), gt2);

// hoặc viết tắt
int gt2Count = std::count_if(begin(a), end(a), GreaterThan2{});

tuy viết theo kiểu function object có tạo 1 object nhưng trình biên dịch khi tối ưu nó sẽ xài thẳng toán tử () của struct GreaterThan2 nên hiệu năng ngang ngửa free function

viết function object khá dài dòng, có thể viết kiểu lambda cho ngắn gọn:

int gt2Count = std::count_if(begin(a), end(a), [](int x) { return x > 2; });

code này ko khác gì code xài function object, nên hiệu năng nó như function object và như free function.

cái hay của function object là nó có thể có state riêng của nó, khác với free function là stateless. Ví dụ struct GreaterThanN muốn tìm số lớn hơn n = bao nhiêu cũng được, free function ko làm được điều này :V vì hàm count_if chỉ truyền vào hàm so sánh 1 giá trị x, nếu free function muốn so sánh với n phải truyền 2 giá trị: void greaterThanN(int n, int x). Xài function object thì làm được:

struct GreaterThanN {
  int n;
  GreaterThanN(int n) : n{n} {}
  bool operator()(int x) const { return x > n; }
};

// sử dụng
int n = ...;
int gtNCount = std::count_if(begin(a), end(a), GreaterThanN{n});

xài lambda cho ngắn gọn:

int n = ...;
int gtNCount = std::count_if(begin(a), end(a), [n](int x) { return x > n; });
                                             // ^ capture n ở đây

n được capture ở đây có kiểu là const int tương đương với 1 struct thế này:

struct anonymous_function object??? {
  const int n; // n ở đây có const
  anonymous_function object???(int n) : n{n} {}
  bool operator()(int x) const { return x > n; }
};

mặc định capture là const hết, nên code generate ra có khi còn lẹ hơn viết function object bằng tay mà quên bỏ const cho các thuộc tính ko thay đổi khi xài toán tử () nữa :V (nghe đồn nếu để mặc định mọi thứ là const, chỉ biến số thay đổi được mới ko có const thì code biên dịch ra có thể lẹ hơn :V)

edit: sửa lại bây giờ tên gọi functor ko ai xài nữa mà xài function object :sleepy:

6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?