Thư viện algorithm – Danh sách các hàm trong thư viện algorithm C++
Thư viện algorithm trong C++ là một thư viện có sẵn được thiết kế đặc biệt để thao tác với dữ liệu mảng theo phạm vi.
Phạm vi có thể hiểu là một chuỗi các đối tượng có thể truy cập thông qua biến lặp hoặc con trỏ. Các hàm này sẽ thực thi trực tiếp trên giá trị nhưng sẽ không tác động đến cấu trúc dữ liệu của đối tượng nó tác động đến(không làm thay đổi kích thước và không gian bộ nhớ của đối tượng).
Bài viết này Nguyễn Văn Hiếu sẽ tổng hợp các hàm hữu dụng nhất mà tác giả thường sử dụng. Nội dụng trình bày cho từng hàm sẽ là: cú pháp, chức năng và ví dụ minh họa. Các bạn có thể xem tất cả các hàm của thư viện này ở link cuối bài viết.
Để thêm thư viện algorithm vào code C/C++, bạn chỉ cần thêm dòng này.
|
1 |
#include <algorithm> |
NỘI DUNG BÀI VIẾT
Các hàm của thư viện algorithm trong C++
1. std::for_each
|
1 2 |
template <class InputIterator, class Function> Function for_each (InputIterator first, InputIterator last, Function fn); |
Gọi lệnh thực thi thi hàm fn cho từng phần tử có chỉ số trong phạm vi [first; last).
Lưu ý: Hãy chú ý cặp ngoặc [first; last). Cặp này có nghĩa là mọi chỉ số x với first <= x < last.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// for_each example #include <iostream> // std::cout #include <algorithm> // std::for_each #include <vector> // std::vector void myfunction (int i) { // function: std::cout << ' ' << i; } struct myclass { // function object type: void operator() (int i) {std::cout << ' ' << i;} } myobject; int main () { std::vector<int> myvector; myvector.push_back(10); myvector.push_back(20); myvector.push_back(30); std::cout << "myvector contains:"; for_each (myvector.begin(), myvector.end(), myfunction); std::cout << '\n'; // or: std::cout << "myvector contains:"; for_each (myvector.begin(), myvector.end(), myobject); std::cout << '\n'; return 0; } |
2. std::find
|
1 2 |
template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val); |
Trả về chỉ số của phần tử đầu tiên trong [first, last) nếu nó bằng với giá trị val. If không tìm được phần tử nào, hàm trả về giá trị last.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// find example #include <iostream> // std::cout #include <algorithm> // std::find #include <vector> // std::vector int main () { // using std::find with array and pointer: int myints[] = { 10, 20, 30, 40 }; int * p; p = std::find (myints, myints+4, 30); if (p != myints+4) std::cout << "Element found in myints: " << *p << '\n'; else std::cout << "Element not found in myints\n"; // using std::find with vector and iterator: std::vector<int> myvector (myints,myints+4); std::vector<int>::iterator it; it = find (myvector.begin(), myvector.end(), 30); if (it != myvector.end()) std::cout << "Element found in myvector: " << *it << '\n'; else std::cout << "Element not found in myvector\n"; return 0; } |
3. std::count
|
1 2 3 |
template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val); |
Trả về số phần tử trong [first, last) có giá trị bằng với val.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// count algorithm example #include <iostream> // std::cout #include <algorithm> // std::count #include <vector> // std::vector int main () { // counting elements in array: int myints[] = {10,20,30,30,20,10,10,20}; // 8 elements int mycount = std::count (myints, myints+8, 10); std::cout << "10 appears " << mycount << " times.\n"; // counting elements in container: std::vector<int> myvector (myints, myints+8); mycount = std::count (myvector.begin(), myvector.end(), 20); std::cout << "20 appears " << mycount << " times.\n"; return 0; } |
4. std::copy
|
1 2 |
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result); |
Hàm std::copy trong thư viện algorithm thực hiện copy toàn bộ giá trị mảng trong [first, last) sang sang mảng mới bắt đầu ở biến lặp result.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// copy algorithm example #include <iostream> // std::cout #include <algorithm> // std::copy #include <vector> // std::vector int main () { int myints[]={10,20,30,40,50,60,70}; std::vector<int> myvector (7); std::copy ( myints, myints+7, myvector.begin() ); std::cout << "myvector contains:"; for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } |
5. std::swap
|
1 |
template <class T> void swap (T& a, T& b); |
Thư viện algorithm trong C++ có hàm std::swap giúp bạn nhanh chóng hoán đổi giá trị của a và b.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// swap example #include <iostream> // std::cout #include <algorithm> // std::swap #include <vector> // std::vector int main () { int x=10, y=20; // x:10 y:20 std::swap(x,y); // x:20 y:10 std::vector<int> foo (4,x), bar (6,y); // foo:4x20 bar:6x10 std::swap(foo,bar); // foo:6x10 bar:4x20 std::cout << "foo contains:"; for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } |
6. std::sort
Một hàm rất hay trong thư viện algorithm đó chính là hàm sắp xếp này. Hàm này có tốc độ sắp xếp còn nhanh hơn thuật toán quick sort đấy.
|
1 2 |
template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
Sắp xếp dãy theo thứ tự tăng dần(mặc định). Nếu muốn sắp xếp theo thứ tự ngược lại, bạn sẽ cần truyền vào hàm comp.
Với các kiểu dữ liệu nguyên thủy, có hàm comp mặc định là std::greater và std::less. Xem ví dụ để hiểu rõ hơn
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// sort algorithm example #include <iostream> // std::cout #include <algorithm> // std::sort #include <vector> // std::vector bool myfunction (int i, int j) { return (i < j); } int main () { int myints[] = {32, 71, 12, 45, 26, 80, 53, 33}; std::vector<int> myvector (myints, myints + 8); // 32 71 12 45 26 80 53 33 // using default comparison (operator <): std::sort (myvector.begin(), myvector.begin() + 4); //(12 32 45 71)26 80 53 33 // using function as comp std::sort (myvector.begin() + 4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80) // using exist comp function std::sort (myvector.begin(), myvector.end(), std::greater<int>()); // std::less<int>() by default // print out content: std::cout << "myvector contains:"; for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } |
Các hàm tiếp theo trong thư viện algorithm trong C++ (có chỉ mục là 7,8,9) là các hàm thực thi dựa trên ý tưởng của thuật toán tìm kiếm nhị phân.
7. std::lower_bound
|
1 2 3 |
template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); |
Trả về iterator trỏ đến phần tử đầu tiên trong [first, last) không nhỏ hơn val. Nếu tất cả các phần tử nhỏ hơn val, trả về last
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// lower_bound/upper_bound example #include <iostream> // std::cout #include <algorithm> // std::lower_bound, std::upper_bound, std::sort #include <vector> // std::vector int main () { int myints[] = {10,20,30,30,20,10,10,20}; std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::sort (v.begin(), v.end()); // sorted arr: 10 10 10 20 20 20 30 30 std::vector<int>::iterator low,up; low=std::lower_bound (v.begin(), v.end(), 20); // ^ up= std::upper_bound (v.begin(), v.end(), 20); // ^ std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; } |
8. std::upper_bound
|
1 2 3 |
template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); |
Trả về iterator đầu tiên trong [first, last) lớn hơn val. Nếu không tồn tại, trả về last
Ví dụ xem ở mục 7.
9. std::binary_search
|
1 2 3 |
template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val); |
Trả về true nếu tồn tại phần tử trong [first, last) bằng với val. Ngược lại, trả về false.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// binary_search example #include <iostream> // std::cout #include <algorithm> // std::binary_search, std::sort #include <vector> // std::vector bool myfunction (int i,int j) { return (i<j); } int main () { int myints[] = {1,2,3,4,5,4,3,2,1}; std::vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1 // using default comparison: std::sort (v.begin(), v.end()); std::cout << "looking for a 3... "; if (std::binary_search (v.begin(), v.end(), 3)) std::cout << "found!\n"; else std::cout << "not found.\n"; // using myfunction as comp: std::sort (v.begin(), v.end(), myfunction); std::cout << "looking for a 6... "; if (std::binary_search (v.begin(), v.end(), 6, myfunction)) std::cout << "found!\n"; else std::cout << "not found.\n"; return 0; } |
10. std::min
|
1 |
template <class T> const T& min (const T& a, const T& b); |
Trả về phần tử nhỏ hơn giữa a và b. Nếu a = b, trả về a.
|
1 2 3 4 5 6 7 8 9 10 11 |
// min example #include <iostream> // std::cout #include <algorithm> // std::min int main () { std::cout << "min(1,2)==" << std::min(1,2) << '\n'; std::cout << "min(2,1)==" << std::min(2,1) << '\n'; std::cout << "min('a','z')==" << std::min('a','z') << '\n'; std::cout << "min(3.14,2.72)==" << std::min(3.14,2.72) << '\n'; return 0; } |
11. std::max
|
1 |
template <class T> const T& max (const T& a, const T& b); |
Trả về phần tử lớn hơn giữa a và b. Nếu a = b, trả về a.
|
1 2 3 4 5 6 7 8 9 10 11 |
// max example #include <iostream> // std::cout #include <algorithm> // std::max int main () { std::cout << "max(1,2)==" << std::max(1,2) << '\n'; std::cout << "max(2,1)==" << std::max(2,1) << '\n'; std::cout << "max('a','z')==" << std::max('a','z') << '\n'; std::cout << "max(3.14,2.73)==" << std::max(3.14,2.73) << '\n'; return 0; } |
12.std::min_element
|
1 2 |
template <class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last); |
Trả về phần tử có giá trị nhỏ nhất trong [first, last).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// min_element/max_element example #include <iostream> // std::cout #include <algorithm> // std::min_element, std::max_element bool myfn(int i, int j) { return i<j; } struct myclass { bool operator() (int i,int j) { return i<j; } } myobj; int main () { int myints[] = {3,7,2,5,6,4,9}; // using default comparison: std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7) << '\n'; // using function myfn as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myfn) << '\n'; // using object myobj as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << '\n'; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myobj) << '\n'; return 0; } |
13. std::max_element
|
1 2 |
template <class ForwardIterator> ForwardIterator max_element (ForwardIterator first, ForwardIterator last); |
Trả về phần tử có giá trị lớn nhất trong [first, last).
Xem ví dụ ở mục 12.
14. std::next_permutation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); Trả về hoán vị tiếp theo có thự tự sắp xếp cao hơn so với hoán vị hiện tại. // next_permutation example #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort int main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); // first must be lowest std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( std::next_permutation(myints,myints+3) ); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; return 0; } |
15. std::prev_permutation
|
1 2 3 |
template <class BidirectionalIterator> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last ); |
Tương tự, trả về hoán vị tiếp theo có thứ tự sắp xếp thấp hơn hoán vị hiện tại
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// next_permutation example #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort, std::reverse int main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); std::reverse (myints,myints+3); std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( std::prev_permutation(myints,myints+3) ); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; return 0; } |
