3. Алгоритмы stl

Алгоритмы STL применяются для решения задач, связанных с обработкой элементов в контейнерах. Все функции принимают в качестве параметра итераторы, что обеспечивает универсальность алгоритмов.

Ниже рассмотрены примеры применения алгоритмов max_element, min_element, accumulate, find, iter_swap.

#include <iostream>

#include <vector>

#include <fstream>

#include <algorithm>

#include <numeric>

using namespace std;

bool absLess (int X1, int X2);

int main (){

vector <int> vec;

ifstream in ("input_task3.txt");

while(!in.eof()){

int x;

in>>x;

vec.push_back (x);

}

in.close();

/*max_element. Поиск наибольшего числа и наибольшего по

модулю*/

vector <int>::iterator iter_max = max_element (vec.begin (),

vec.end ());

vector <int>::iterator iter_max_abs = max_element

(vec.begin(), vec.end(), absLess);

/*min_element. Поиск наименьшего числа и наименьшего по

модулю*/

vector <int>::iterator iter_min = min_element (vec.begin (),

vec.end ());

vector <int>::iterator iter_min_abs = min_element

(vec.begin(), vec.end(), absLess);

/*accumulate. В первом примере складываются все числа с числом

-100.Во втором примере все числа умножаются*/

int acc = accumulate (vec.begin (), vec.end (), -100);

int acc_multi = accumulate (vec.begin (), vec.end (), 1,

multiplies <int>());

/*find. Поиск чисел 9 и 56*/

vector <int>::iterator iter_find = find (vec.begin (), vec.end

(), 9);

vector <int>::iterator iter_not_find = find (vec.begin (),

vec.end (), 56);

ofstream out ("output.txt");

out<<"maximum: "<<*iter_max<<"\nminimum: "<<*iter_min;

out<<"\nmaximum of absolute values: "

<<*iter_max_abs<<"\nminimum of absolute values: "

<<*iter_min_abs;

out<<"\n\nsum: "<<acc<<"\nproduct: "<<acc_multi;

(iter_find == vec.end())? out<<"\n\nvector does not contains:

9" : out<<"\n\nvector contains: 9" ;

(iter_not_find == vec.end())? out<<"\nvector does not

contains: 56" : out<<"\nvector contains: 56" ;

/*iter_swap. Меняет местами первый и последний элементы*/

vector <int>::iterator iter_last=vec.end();

iter_swap (vec.begin(),--iter_last);

out<<"\n\nvector after iter_swap:\n";

for (vector<int>::iterator iter = vec.begin(); iter !=

vec.end(); ++iter){

out<<*iter<<" ";

}

out.close();

return 0;

}

/*предикат для сравнения модулей чисел*/

bool absLess (int X1, int X2)

{

return abs(X1)<abs(X2);

}

Содержимое входного файла:

3 2 1 5 9 4 -10 -1 4

Результат работы программы:

maximum: 9

minimum: -10

maximum of absolute values: -10

minimum of absolute values: 1

sum: -83

product: 43200

vector contains: 9

vector does not contains: 56

vector after iter_swap:

4 2 1 5 9 4 -10 -1 3

4. Адаптеры контейнеров

В STL реализовано три адаптера контейнеров:

• Стек.

• Очередь.

• Очередь с приоритетами.

Стек представляет собой структуру данных, которая допускает только две операции, изменяющие её размер: push (для добавления элемента в конце) и pop (для удаления элемента в конце). Иными ловами, стек работает по принципу "последний пришёл – первый ушёл". [3]

Очередь является структурой данных, в которую можно добавлять элементы с одного конца, сзади, и удалять с другого конца, спереди. Можно узнать и изменить значения элементов спереди и сзади. [3]

Очередь с приоритетами является структурой данных, из которой, если она не пуста, можно удалить только наибольший элемент. [3]

Ниже представлен листинг программы, которая демонстрирует работу стека, очереди и очереди с приоритетами. Элементы из файла копируются в данные структуры, а потом выводятся в другой файл.

#include <iostream>

#include <fstream>

#include <stack>

#include <queue>

using namespace std;

int main ()

{

queue<int> qu;

stack<int> st;

priority_queue<int> p_qu;

ifstream in("input.txt");

ofstream out("output.txt");

out<<"input:\n";

/*копирование элементов в стек, очередь и очередь с

приоритетами*/

while (!in.eof()){

int x;

in>>x;

out<<x<<" ";

st.push(x);

qu.push(x);

p_qu.push(x);

}

in.close();

out<<"\n\nstack:\n";

/*вывод элементов стека*/

while (st.size()){

out<<st.top()<<" ";

st.pop();

}

out<<"\n\nqueue:\n";

/*вывод элементов из очереди*/

while (qu.size()){

out<<qu.front()<<" ";

qu.pop();

}

out<<"\n\npriority_queue:\n";

/*вывод элементов из очереди с приоритетами*/

while (p_qu.size()){

out<<p_qu.top()<<" ";

p_qu.pop();

}

out.close();

return 0;

}

Содержимое входного файла:

3 2 1 5 9 4 -10 -1 4

Результат работы программы:

input:

3 2 1 5 9 4 -10 -1 4

stack:

4 -1 -10 4 9 5 1 2 3

queue:

3 2 1 5 9 4 -10 -1 4

priority_queue:

9 5 4 4 3 2 1 -1 -10