§ 20. Выкарыстанне бібліятэчных функцый для сартавання і пошуку даных

20.1. Лінейны пошук элемента

Для арганізацыі лінейнага пошуку элемента ў масіве можна выкарыстоўваць наступныя функцыі:

find

Знаходзяць значэнне ў дадзеным дыяпазоне

count

Вяртае колькасць элементаў, якая адпавядае дадзенаму значэнню

find_if

Шукае першае ўваходжанне элемента, для якога дакладна значэнне функцыі кампаратара

count_if

Вяртае колькасць элементаў, для якіх значэнне функцыі кампаратара з’яўляецца праўдай 

Ва ўсіх гэтых функцый тры параметры. Першыя два параметры з'яўляюцца ітэратарамі, якія вызначаюць дыяпазон для пошуку ў масіве, трэці задае ўмову пошуку. Пры гэтым левая мяжа дыяпазону ўваходзіць у вобласць пошуку, а правая — не. Гэта значыць дыяпазон пошуку з’яўляецца паўінтэрвалам. Калі пошук ажыццяўляецца ва ўсім вектары, то выкарыстоўваюцца ітэратры begin() и end().

У якасці выніку функцыі find і find_if выдаюць значэнне ітэратара, які паказвае на першы элемент, што адпавядае пошукаваму запыту.

Кампаратар для функцый, якія рэалізуюць пошук элемента ў дыяпазоне, мае адзін параметр. Кампаратар вяртае значэнне true, калі элемент задавальняе ўмову пошуку, і false, калі не. Функцыя пошуку перадае ў кампаратар па чарзе значэнні з дыяпазону пошуку. Як толькі для якога-небудзь значэння атрымалі true, работа пошукавай функцыі спыняецца.

Калі элемент не знойдзены, функцыя вяртае ітэратар на правую мяжу вобласці пошуку.

Прыклад 20.1. Дадзены лінейны масіў цэлых лікаў. Напісаць праграму, якая:

1) знойдзе пазіцыю элемента, роўнага x;

2) знойдзе пазіцыю элемента, кратнага x;

3) палічыць колькасць элементаў, роўных x;

4) палічыць колькасць элементаў, кратных x.

Этапы выканання задання

I. Зыходныя даныя: пераменныя n — колькасць лікаў у масіве, a — масіў.

II. Вынік: пазіцыі элементаў n1 і n2 (пункты 1 і 2) і колькасць элементаў k1 і k2 (пункты 3 і 4).

III. Алгарытм рашэння задачы.

1. Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
2. Будзем выкарыстоўваць наступныя функцыі:

2.1. find для пункта 1.
2.2. find_if для пункта 2.
2.3. count для пункта 3.
2.4. count_if для пункта 4.

3. Вывад выніку.

IV. Апісанне пераменных: n, k1, k2, n1, n2, x – int, a –  vector<int>.

Функцыі min_element і max_element і max_element вяртаюць ітэратар на мінімальнае і максімальнае значэнні элементаў у дыяпазоне.

Прыклад 20.2. Дадзены лінейны масіў цэлых лікаў. Напісаць праграму, якая знойдзе мінімальны і максімальны элементы ў масіве.

Этапы выканання задання

I. Зыходныя даныя: пераменныя n — колькасць лікаў у масіве, a — масіў.

II. Вынік: пазіцыі мінімальнага і максімальнага элементаў nmin і nmax і іх значэнні.

III. Алгарытм рашэння задачы.

  1. Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
  2. Будзем выкарыстоўваць адпаведныя функцыі.
  3. Вывад выніку.
IV. Апісанне пераменных: n, n1, n2 – int, a –  vector<int>.

Прыклад 20.1.

V. Праграма:

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

 

using namespace std;

 

int x;

 

bool comp(int t)

{

  return (t % x == 0);

}

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector<int> a(n);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout<<endl;

//пошук элемента x у масіве

  cout << "x = ";

  cin >> x;

  int n1 = find(a.begin(), a.end(), x) - a.begin();

  if(n1 < a.size())

    cout << "chislo na meste " << n1 << endl;

  else

    cout << "net chisla = x" << endl;

//пошук па ўмове: лік кратны x

  int n2 = find_if(a.begin(), a.end(), comp) - a.begin();

  if (n2 < a.size()){

    cout << "chislo " << a[n2];

    cout << " na meste " << n2;

    cout << endl;

  }

  else

    cout << "net kratnyh chisel" << endl;

//колькасць элементаў, роўных х

  int k1 = count(a.begin(), a.end(), x);

  cout << "ravno x - " << k1 << endl;

//колькасць элементаў, кратных х

  int k2 = count_if(a.begin(), a.end(), comp);

  cout << "kratno x - " << k2 << endl;

  return 0;

}

 VI. Тэсціраванне.

VII. Аналіз вынікаў. Індэкс ліку 3 у масіве роўны 1, а таксама гэты лік кратны самому сабе. У масіве адзін лік, роўны 3, і два лікі (3 і 18), кратныя 3.

Звярніце ўвагу на тое, што пераменная x апісана як глабальная пераменная, паколькі яна выкарыстоўваецца як у функцыі main, так і ў кампаратары comp.

Прыклад 20.2.

 V. Праграма:

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector<int> a(n);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout<<endl;

  //пошук мінімальнага і 

  //максімальнага

  int nmin = min_element(a.begin(), a.end()) - a.begin();

  cout << "min element = " << a[nmin];

  cout << " na meste - " << nmin << endl;

  int nmax = max_element(a.begin(), a.end()) - a.begin();

  cout << "max element = " << a[nmax];

  cout << " na meste - " << nmax << endl;

  return 0;

}

 VI. Тестирование.

Функцыі  min_element  і  max_element   могуць мець трэці параметр — кампаратар, які вызначае правіла парадку для элементаў паказанага дыяпазону.