hàm equal_range (algorithm)

Language C++

Thư viện algorithm

Biên soạn: Nguyễn Đức Tâm

Tài liệu tham khảo: http://www.cplusplus.com/reference/algorithm/

Hàm equal_range:

Cấu trúc hàm:

template<class ForwardIterator, class T>

            pair<ForwardIterator, ForwardIteator>

                        equal_range(ForwardIterator first, ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>

            pair<ForwardIterator, ForwardIterator>

                        equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

·        Trả về dãy con lớn nhất trong khoảng [first, last) chứa các phần tử có giá trị là value.

·        Nếu giá trị value không tìm thấy thì hàm sẽ trả về cặp giá trị có chiều dài là 0, tại vị trí mà giá trị của nó gần value nhất. Ngược lại nếu giá trị value cần tìm lớn hơn tất cả các phần tử hiện có thì nó trả về cặp giá trị có chiều dài là 0, cụ thể là <last, last>.

·        Để hàm thực hiện đúng đắn các phần tử trong khoảng phải được sắp theo trật tự tăng dần (phép toán so sánh < trong ver 1 hoặc comp trong ver 2).

Hàm equal_range được xây dựng từ nền tảng của hai hàm lower_bound và upper_bound. Có thể được viết lại như sau:

template<class  ForwardIterator, class T>

            pair<ForwardIterator, ForwardIterator>

                        equal_range(ForwardIterator first, ForwardIterator last, const T& value)

{

            ForwardIterator it = lower_bound(first, last, value);

            return make_pair ( it, upper_bound(first, last, value) );

}

Tham số:

Ví dụ:

/*

            Coder: Nguyen Duc Tam

            For: C++_Giaotrinh

*/

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

#define ALL(c) (c).begin(), (c).end()

#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)

#define X first

#define Y second

#define DEBUG false

int main()

{

            freopen("output.txt","w",stdout);

            // bounds chua gia tri tra equal_range

            pair<vector<int>::iterator, vector<int>::iterator> bounds;

            // khoi tao mot mang a

            int a[] = {144, 47, 75, 335,47};

            // tinh so phan tu cua mang a

            int n = sizeof(a) / sizeof(int);

            // khoi tao mo vector tu mang a

            vector<int> v(a, a + n);

            // sap xep cac phan tu trong vector a

            sort(ALL(v));

            // su dung ham equal_range

            bounds = equal_range(ALL(v), 47);

            // test ket qua

            FOR(it,v)

                        cout << *it << " ";

            cout << endl;

            cout << "first: " << distance(v.begin(), bounds.X ) << endl;

            cout << "last: " << distance(v.begin(), bounds.Y) << endl;

            cout << "range: " << bounds.Y - bounds.X << endl;

           

            // dung lai de xem

            if(DEBUG)

                        system("pause");

            return 0;         

}

Sau khi chaỵ chương trình trên, bạn mở file output.txt sẽ thấy nội dung file như sau:

47 47 75 144 335

first: 0

last: 2

range: 2

Còn bạn sửa lại câu lệnh “bounds = equal_range(ALL(v),456 );”, bạn mở file output.txt thì nội dung sẽ thay đổi như sau:

47 47 75 144 335

first: 5

last: 5

range: 0

Trên đây, tôi đã nói và viết một cách khái quát về hàm equal_range trong thư viện algorithm của C++.