Thư Viện Thuật Toán Algorithm Trong C++

View: 310

Thư viện thuật toán – Algorithm trong C++ là một trong số các thư viện được sử dụng thường xuyên. Thư viện này cung cấp cho các bạn các hàm liên quan đến các thuật toán quan trọng như hàm sắp xếp – sort, tìm min, max…

1. Hàm sắp xếp Sort

Thư viện Algorithm cung cấp hàm Sort giúp bạn thực hiện sắp xếp dãy số dạng mảng, vector trong C++ cực kì nhanh. Là một hàm được biên soạn sẵn, bạn chỉ cần áp dụng vào và sử dụng. Mặc định là sắp xếp tăng dần. Sử dụng hàm này, bạn sẽ tối ưu hóa được thuật toán, đặc biệt là nó còn sắp xếp nhanh hơn cả thuật toán Quick sort.

– Cú pháp:

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)

Trong đó:

• First là phần tử đầu của dãy
• Last là phần tử cuối cùng của dãy + 1 ( tức là nó sẽ sắp xếp từ vị trí bắt đầu đến trước phần tử last)
• Comp (compare) là tham số giúp bạn chọn sắp xếp tăng hay giảm. Nếu bạn không truyền tham số này mặc định sẽ là sắp xếp tăng dần.Có 2 tham số để truyền: greater (dùng cho sắp xếp giảm) less (dùng cho sắp xếp tăng)

Ví dụ:

#include <iostream> #include <algorithm> using namespace std; int main() { int n; int a[1000]; cout << "Nhap so phan tu: "; cin >> n; cout << endl << "Nhap day so: " << endl; for (int i = 0; i < n; i++) { cin >> a[i]; } // sap xep tang: sort(a, a + n); // Hien thi: cout << endl << "Day so sap xep tang dan: "; for (int i = 0; i < n; i++) { cout << a[i] << " "; } // Sap xep giam: sort(a, a + n, greater<int>()); // Hien thi: cout << endl << "Day so sap xep giam dan: "; for (int i = 0; i < n; i++) { cout << a[i] << " "; } return 0; }

2. Hàm đổi chỗ swap

swap là hàm thực hiện hoán đổi giá trị giữa hai phần tử a và b một cách nhanh nhất. Hàm này có thể thực hiện cho nhiều kiểu dữ liệu khác nhau. Nhưng hai dữ liệu cần đổi chỗ cần cùng một loại. Thông thường ta thường sử dụng hàm này trong việc hoán đổi dữ liệu kiểu số (int, doube, . . .).

Cú pháp:

template <class T> void swap ( T& a, T& b ) { T c(a); a=b; b=c; }

Ví dụ:

#include<iostream> #include<algorithm> using namespace std; int main() { int a = 5; int b = 6; swap(a,b); cout << "a = " << a << endl; cout << "b = " << b; return 0; }

3. Hàm min, max

Hàm min, max có tác dụng trả về giá trị tương ứng là phần tử lớn nhất, nhỏ nhất trong hai số a, b truyền vào với cùng kiểu dữ liệu. Hàm này chúng ta có thể hoànn toàn tự định nghĩa được, tuy nhiên trong một số trường hợp thì sử dụng hàm được viết sẵn sẽ giúp bạn tiết kiệm rất nhiều thời gian.

Xét ví dụ dưới đây:

#include <iostream> #include <algorithm> using namespace std; int main() { int a = 17; int b = 12; cout << "Min = " << min(a, b) << endl; cout << "Max = " << max(a, b); return 0; }

Bạn có thể tìm hiểu thêm về thư viện này với rất nhiều hàm trong thư viện Algorithm được thống kê dưới đây nhé:

adjacent_find Tìm kiếm hai phần tử liền kề bằng nhau hoặc thỏa mãn một điều kiện cụ thể.

all_of Trả về truekhi có một điều kiện tại mỗi phần tử trong phạm vi đã cho.

any_of Trả về truekhi điều kiện có ít nhất một lần trong phạm vi phần tử được chỉ định.

binary_search Kiểm tra xem có phần tử nào trong phạm vi đã sắp xếp bằng với một giá trị đã chỉ định hoặc tương đương với phần tử đó theo nghĩa được chỉ định bởi một vị từ nhị phân hay không.clamp

copy Gán giá trị của các phần tử từ phạm vi nguồn đến phạm vi đích, lặp lại qua chuỗi nguồn của các phần tử và gán chúng vị trí mới theo hướng về phía trước.

copy_backward Gán giá trị của các phần tử từ một phạm vi nguồn đến một phạm vi đích, lặp lại qua chuỗi nguồn của các phần tử và gán chúng vị trí mới theo hướng ngược lại.

copy_if Sao chép tất cả các phần tử trong một phạm vi đã cho để kiểm tra truemột điều kiện cụ thểcopy_n Sao chép một số phần tử được chỉ định.

count Trả về số phần tử trong một dải ô có giá trị khớp với một giá trị được chỉ định.

count_if Trả về số phần tử trong một dải ô có giá trị phù hợp với một điều kiện đã chỉ định.

equal So sánh hai phạm vi từng phần tử cho bằng nhau hoặc tương đương theo nghĩa được chỉ định bởi một vị từ nhị phân.

equal_range Tìm một cặp vị trí trong một phạm vi có thứ tự, vị trí đầu tiên nhỏ hơn hoặc tương đương với vị trí của một phần tử được chỉ định và vị trí thứ hai lớn hơn vị trí của phần tử, trong đó cảm giác tương đương hoặc thứ tự được sử dụng để thiết lập các vị trí trong chuỗi có thể được chỉ định bởi một vị từ nhị phân.

fill Gán cùng một giá trị mới cho mọi phần tử trong một phạm vi được chỉ định.

fill_n Gán một giá trị mới cho một số phần tử được chỉ định trong một phạm vi bắt đầu bằng một phần tử cụ thể.

find Định vị vị trí của lần xuất hiện đầu tiên của một phần tử trong một phạm vi có giá trị được chỉ định.

find_end Tìm trong một phạm vi cho dãy con cuối cùng giống với một dãy được chỉ định hoặc tương đương theo nghĩa được chỉ định bởi một vị từ nhị phân.

find_first_of Tìm kiếm lần xuất hiện đầu tiên của bất kỳ giá trị nào trong một số giá trị trong phạm vi mục tiêu hoặc lần xuất hiện đầu tiên của bất kỳ phần tử nào trong số một số phần tử tương đương theo nghĩa được chỉ định bởi một vị từ nhị phân cho một tập hợp phần tử cụ thể.

find_if Xác định vị trí của lần xuất hiện đầu tiên của một phần tử trong một phạm vi thỏa mãn một điều kiện xác định.

find_if_not Trả về phần tử đầu tiên trong phạm vi được chỉ định không thỏa mãn điều kiện.

for_each Áp dụng một đối tượng hàm đã chỉ định cho từng phần tử theo thứ tự chuyển tiếp trong một phạm vi và trả về đối tượng hàm.for_each_n

generate Gán các giá trị được tạo bởi một đối tượng hàm cho từng phần tử trong một phạm vi.

generate_n Gán các giá trị được tạo bởi một đối tượng hàm cho một số phần tử được chỉ định là một dải ô và trở về vị trí trước giá trị được gán cuối cùng.

includes Kiểm tra xem một dải ô đã sắp xếp có chứa tất cả các phần tử có trong một dải ô được sắp xếp thứ hai hay không, trong đó tiêu chí thứ tự hoặc tính tương đương giữa các phần tử có thể được chỉ định bởi một vị từ nhị phân.

inplace_merge Kết hợp các phần tử từ hai phạm vi được sắp xếp liên tiếp thành một phạm vi được sắp xếp duy nhất, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

is_heap Trả về truenếu các phần tử trong phạm vi được chỉ định tạo thành một đống.

is_heap_until Trả về truenếu phạm vi được chỉ định tạo thành một đống cho đến phần tử cuối cùng.

is_partitioned Trả về truenếu tất cả các phần tử trong phạm vi đã cho kiểm tra truemột điều kiện đứng trước bất kỳ phần tử nào kiểm tra false.

is_permutation Xác định xem các phần tử trong một phạm vi nhất định có tạo thành một hoán vị hợp lệ hay không.

is_sorted Trả về truenếu các phần tử trong phạm vi đã chỉ định có thứ tự được sắp xếp.

is_sorted_until Trả về truenếu các phần tử trong phạm vi đã chỉ định có thứ tự được sắp xếp.

iter_swap Trao đổi hai giá trị được tham chiếu bởi một cặp trình vòng lặp được chỉ định.

lexicographical_compare So sánh từng phần tử giữa hai dãy để xác định dãy nào nhỏ hơn trong hai dãy.

lower_bound Tìm vị trí của phần tử đầu tiên trong một phạm vi có thứ tự có giá trị lớn hơn hoặc tương đương với một giá trị được chỉ định, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

make_heap Chuyển đổi các phần tử từ một phạm vi được chỉ định thành một đống trong đó phần tử đầu tiên là lớn nhất và tiêu chí sắp xếp có thể được chỉ định bằng một vị từ nhị phân.

max So sánh hai đối tượng và trả về đối tượng lớn hơn trong hai đối tượng, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

max_element Tìm lần xuất hiện đầu tiên của phần tử lớn nhất trong một phạm vi được chỉ định trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

merge Kết hợp tất cả các phần tử từ hai phạm vi nguồn được sắp xếp thành một phạm vi đích duy nhất được sắp xếp, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

min So sánh hai đối tượng và trả về giá trị nhỏ hơn của hai đối tượng, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

min_element Tìm lần xuất hiện đầu tiên của phần tử nhỏ nhất trong một phạm vi xác định trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

minmax So sánh hai tham số đầu vào và trả về chúng dưới dạng một cặp, theo thứ tự từ ít nhất đến lớn nhất.

minmax_element Thực hiện công việc được thực hiện bởi min_elementvà max_elementtrong một cuộc gọi.

mismatch So sánh hai phạm vi từng phần tử cho bằng nhau hoặc tương đương theo nghĩa được chỉ định bởi một vị từ nhị phân và xác định vị trí đầu tiên nơi xảy ra sự khác biệt.

<alg> move Di chuyển các phần tử được liên kết với một phạm vi được chỉ định.

move_backward Di chuyển các phần tử của một trình lặp này sang trình lặp khác. Việc di chuyển bắt đầu với phần tử cuối cùng trong một phạm vi được chỉ định và kết thúc với phần tử đầu tiên trong phạm vi đó.

next_permutation Sắp xếp lại các phần tử trong một phạm vi để thứ tự ban đầu được thay thế bằng hoán vị lớn hơn tiếp theo về mặt từ vựng nếu nó tồn tại, trong đó ý nghĩa tiếp theo có thể được chỉ định bằng một vị từ nhị phân.

none_of Trả về truekhi một điều kiện không bao giờ có giữa các phần tử trong phạm vi đã cho.

nth_element Phân chia một dãy các phần tử, xác định vị trí chính xác phần tử thứ n của dãy trong dãy sao cho tất cả các phần tử đứng trước nó nhỏ hơn hoặc bằng nó và tất cả các phần tử theo sau nó trong dãy đều lớn hơn hoặc bằng nó.

partial_sort Sắp xếp một số lượng cụ thể của các phần tử nhỏ hơn trong một phạm vi thành một thứ tự không tăng dần hoặc theo một tiêu chí sắp xếp được chỉ định bởi một vị từ nhị phân.

partial_sort_copy Sao chép các phần tử từ một phạm vi nguồn vào một phạm vi đích trong đó các phần tử nguồn được sắp xếp theo thứ tự nhỏ hơn hoặc một vị từ nhị phân được chỉ định khác.

partition Phân loại các phần tử trong một phạm vi thành hai tập hợp rời rạc, với những phần tử thỏa mãn vị từ một ngôi đứng trước những phần tử không thỏa mãn nó.

partition_copy Sao chép các phần tử có một điều kiện truetới một điểm đến và điều kiện là một điểm falseđến khác. Các phần tử phải đến từ một phạm vi xác định.

partition_point Trả về phần tử đầu tiên trong phạm vi đã cho không thỏa mãn điều kiện. Các phần tử được sắp xếp để những phần tử thỏa mãn điều kiện đến trước những phần tử không thỏa mãn điều kiện.

pop_heap Loại bỏ phần tử lớn nhất từ phía trước của một đống đến vị trí tiếp theo đến cuối cùng trong phạm vi và sau đó tạo một đống mới từ các phần tử còn lại.

prev_permutation Sắp xếp lại các phần tử trong một phạm vi để thứ tự ban đầu được thay thế bằng hoán vị lớn hơn tiếp theo về mặt từ vựng nếu nó tồn tại, trong đó ý nghĩa tiếp theo có thể được chỉ định bằng một vị từ nhị phân.

push_heap Thêm một phần tử ở cuối một phạm vi vào một đống hiện có bao gồm các phần tử trước đó trong phạm vi.

random_shuffle Sắp xếp lại một dãy gồm N phần tử trong một phạm vi thành một trong N ! sắp xếp có thể được lựa chọn một cách ngẫu nhiên.

remove Loại bỏ một giá trị được chỉ định khỏi một phạm vi nhất định mà không làm xáo trộn thứ tự của các phần tử còn lại và trả về phần cuối của một phạm vi mới không có giá trị đã chỉ định.

remove_copy Sao chép các phần tử từ một phạm vi nguồn sang một phạm vi đích, ngoại trừ các phần tử của một giá trị đã chỉ định sẽ không được sao chép mà không làm xáo trộn thứ tự của các phần tử còn lại và trả về phần cuối của một phạm vi đích mới.

remove_copy_if Sao chép các phần tử từ một phạm vi nguồn sang một phạm vi đích, ngoại trừ việc thỏa mãn một vị từ sẽ không được sao chép, mà không làm xáo trộn thứ tự của các phần tử còn lại và trả về phần cuối của một phạm vi đích mới.

remove_if Loại bỏ các phần tử thỏa mãn một vị từ khỏi một phạm vi nhất định mà không làm xáo trộn thứ tự của các phần tử còn lại và trả về phần cuối của một phạm vi mới không có giá trị đã chỉ định.

replace Kiểm tra từng phần tử trong một phạm vi và thay thế nó nếu nó khớp với một giá trị được chỉ định.

replace_copy Kiểm tra từng phần tử trong một phạm vi nguồn và thay thế nó nếu nó khớp với một giá trị được chỉ định trong khi sao chép kết quả vào một phạm vi đích mới.

replace_copy_if Kiểm tra từng phần tử trong một phạm vi nguồn và thay thế nó nếu nó thỏa mãn một vị từ được chỉ định trong khi sao chép kết quả vào một phạm vi đích mới.

replace_if Kiểm tra từng phần tử trong một phạm vi và thay thế nó nếu nó thỏa mãn một vị từ được chỉ định.

reverse Đảo ngược thứ tự của các phần tử trong một phạm vi.

reverse_copy Đảo ngược thứ tự của các phần tử trong phạm vi nguồn trong khi sao chép chúng vào phạm vi đích

rotate Trao đổi các phần tử trong hai phạm vi liền kề.

rotate_copy Trao đổi các phần tử trong hai phạm vi liền kề trong một phạm vi nguồn và sao chép kết quả vào một phạm vi đích.

search Tìm kiếm lần xuất hiện đầu tiên của một chuỗi trong phạm vi mục tiêu có các phần tử bằng với các phần tử trong một chuỗi phần tử nhất định hoặc có phần tử tương đương theo nghĩa được chỉ định bởi một vị từ nhị phân cho các phần tử trong chuỗi đã cho.

search_n Tìm kiếm dãy con đầu tiên trong một phạm vi của một số phần tử cụ thể có một giá trị cụ thể hoặc một mối quan hệ với giá trị đó như được chỉ định bởi một vị từ nhị phân.

set_difference Hợp nhất tất cả các phần tử thuộc một phạm vi nguồn được sắp xếp, nhưng không thuộc phạm vi nguồn được sắp xếp thứ hai, thành một phạm vi đích được sắp xếp duy nhất, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

set_intersection Hợp nhất tất cả các phần tử thuộc cả hai phạm vi nguồn được sắp xếp thành một phạm vi đích duy nhất, được sắp xếp, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

set_symmetric_difference Hợp nhất tất cả các phần tử thuộc về một, chứ không phải cả hai, của phạm vi nguồn được sắp xếp thành một phạm vi đích duy nhất, được sắp xếp, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

set_union Hợp nhất tất cả các phần tử thuộc ít nhất một trong hai phạm vi nguồn được sắp xếp thành một phạm vi đích duy nhất, được sắp xếp, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

sort Sắp xếp các phần tử trong một phạm vi được chỉ định thành một thứ tự không tăng dần hoặc theo một tiêu chí sắp xếp được chỉ định bởi một vị từ nhị phân.

shuffle Xáo trộn (sắp xếp lại) các phần tử cho một phạm vi nhất định bằng cách sử dụng trình tạo số ngẫu nhiên.

sort_heap Chuyển đổi một đống thành một phạm vi được sắp xếp.

stable_partition Phân loại các phần tử trong một phạm vi thành hai tập hợp rời rạc, với những phần tử thỏa mãn vị từ một ngôi đứng trước những phần tử không thỏa mãn nó, bảo toàn thứ tự tương đối của các phần tử tương đương.

stable_sort Sắp xếp các phần tử trong một phạm vi xác định thành một thứ tự không tăng dần hoặc theo một tiêu chí sắp xếp được chỉ định bởi một vị từ nhị phân và bảo toàn thứ tự tương đối của các phần tử tương đương.

swap Trao đổi giá trị của các phần tử giữa hai loại đối tượng, gán nội dung của đối tượng thứ nhất cho đối tượng thứ hai và nội dung của đối tượng thứ hai cho đối tượng thứ nhất.

swap_ranges Trao đổi các phần tử của một dải ô với các phần tử của một dải ô khác có kích thước bằng nhau.

transform Áp dụng một đối tượng hàm đã chỉ định cho từng phần tử trong phạm vi nguồn hoặc cho một cặp phần tử từ hai phạm vi nguồn và sao chép các giá trị trả về của đối tượng hàm vào một phạm vi đích.

unique Loại bỏ các phần tử trùng lặp liền kề nhau trong một phạm vi được chỉ định.

unique_copy Sao chép các phần tử từ một phạm vi nguồn vào một phạm vi đích ngoại trừ các phần tử trùng lặp liền kề với nhau.

upper_bound Tìm vị trí của phần tử đầu tiên trong một phạm vi có thứ tự có giá trị lớn hơn một giá trị được chỉ định, trong đó tiêu chí sắp xếp có thể được chỉ định bởi một vị từ nhị phân.

Nguồn: https://docs.microsoft.com/en-us/cpp/standard-library/algorithm?view=msvc-170