Lập Trình Không Khó

Học lập trình theo cách riêng của bạn!

Bạn đang ở:Trang chủ / Chia sẻ / Thư viện algorithm – Danh sách các hàm trong thư viện algorithm C++

Thư viện algorithm – Danh sách các hàm trong thư viện algorithm C++

by Để lại bình luận

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ư viện algorithm C/C++

Để thêm thư viện algorithm vào code C/C++, bạn chỉ cần thêm dòng này.

#include <algorithm>

Các hàm của thư viện algorithm trong C++

1. std::for_each 

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.

// 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

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.

// 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 myintsn";

  // 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 myvectorn";

  return 0;
}

3. std::count

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.

// 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

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.

// 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

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.

// 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.

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

// 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

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

// 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

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

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.

// 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

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.

// 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

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.

// 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

template <class ForwardIterator>
  ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

Trả về phần tử có giá trị nhỏ nhất trong [first, last).

// 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

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

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

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

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

Tài liệu tham khảo

  1. http://www.cplusplus.com/reference/algorithm/
  2. https://en.cppreference.com/w/cpp/algorithm
5/5 - (1 bình chọn)

Bài viết liên quan

Học lập trình cho người mới bắt đầu
Học lập trình online với mức giá ưu đãi
Minh họa thuật toán sắp xếp bubble sort
Bài 47. Thuật toán sắp xếp nổi bọt
Bài 48. Thuật toán sắp xếp chọn (Selection sort)

Reader Interactions

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

DMCA.com Protection Status