Пары
Тип pair позволяет работать с двумя величинами как с единым целым. Данный тип применяется чаще всего при работе с объектами, которые представляют собой пары "ключ/значение", или, например, когда необходимо получить функцию, возвращающую два значения.[1]
Ниже представлен листинг программы, которая выводит имена по заданной дате. В программе использовался контейнер vector, содержащий пары, в которых первый элемент – имя, а второй – дата.
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <utility>
using namespace std;
int main()
{
vector<pair<string, string>> vec;
string name, date, date_find;
fstream in ("input_task1.txt");
pair<string, string> temp_pair;
/* заполнение вектора пар,
где первый (first) элемент пары - имя, а второй (second) –
дата*/
while (in.peek()!=EOF){
getline(in,name);
getline(in,date);
temp_pair.first=name;
temp_pair.second=date;
vec.push_back (temp_pair);
}
in.close();
/*ввод даты, поиск и вывод имён по заданной дате*/
cout<<"enter date:";
getline (cin,date_find);
for (vector<pair<string, string>>::iterator iter=vec.begin();
iter<vec.end(); ++iter){
if(date_find == iter->second)
cout<<iter->first<<endl;
}
return 0;
}
Содержимое входного файла:
Name1
Name2
Name3
Name4
Name5
Name6
Name7
Name8
Name9
Результат работы программы:
enter date:2000
Name1
Name3
Name8
Контейнеры STL
Контейнеры в STL представляют собой объекты, которые хранят коллекции других объектов.
В STL имеются следующие контейнеры. [2]
· vector <T>. Вектором называется абстрактная модель, имитирующая динамический массив при операциях с элементами. Элементы вектора копируются во внутренний динамический массив. Элементы всегда хранятся в определённом порядке. Вектор обеспечивает произвольный доступ к своим элементам. Итераторы вектора являются итераторами произвольного доступа, что позволяет применять к векторам все алгоритмы STL. [1]
· deque <T>. Дек тоже работает с элементами, оформленными в динамический массив, поддерживает произвольный доступ и обладает практически тем же интерфейсом. Различие заключается в том, что динамический массив дека открыт с обоих концов. [1]
· list <T>. Обеспечивает линейное время доступа к последовательности переменной длины, но с константным временем вставки и удаления в любом месте последовательности. [2]
Ниже приведён листинг программы, которая удаляет из вектора, дека и списка повторяющиеся числа, оставляя лишь один экземпляр.
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <fstream>
#include <time.h>
using namespace std;
int main()
{
ifstream in("input_task2.txt");
list<double> lt;
deque<double> deq;
vector<double> vec;
double element;
while(!in.eof()) {
in>>element;
vec.push_back (element);
deq.push_back (element);
lt.push_back (element);
}
in.close();
/*удаление элементов в векторе*/
clock_t startClock = clock();
for (vector<double>::iterator iter = vec.begin(); iter!=
vec.end(); ++iter){
for(vector<double>::iterator iter1 = iter + 1; iter1!=
vec.end(); ++iter1){
if(*iter==*iter1){
vec.erase(iter1--);
}
}
}
clock_t endClock=clock();
double vectorTime = difftime(endClock,startClock);
/*удаление элементов в деке*/
startClock=clock();
for (int i=0; i<deq.size(); ++i){
for (int j=i+1; j<deq.size(); ++j){
if (deq[i] == deq[j]){
deq.erase(deq.begin() + j);
j--;
}
}
}
endClock=clock();
double dequeTime = difftime(endClock,startClock);
/*удаление элементов в списке*/
startClock=clock();
list<double>::iterator iter_lt=lt.begin();
for (list<double>::iterator iter=lt.begin(); iter!=lt.end();
++iter){
iter_lt=iter;
++iter_lt;
while(iter_lt!=lt.end()){
if(*iter_lt==*iter){
lt.erase(iter_lt--);
}
++iter_lt;
}
}
endClock=clock();
double listTime = difftime(endClock,startClock);
ofstream out ("output.txt");
/*запись результата работы вектора в фаил*/
out<<"vector:\n";
for (vector<double>::iterator iter=vec.begin();
iter<vec.end(); ++iter){
out<<*iter<<" ";
}
out<<"\ntime: "<<vectorTime;
/*запись результата работы дека в фаил*/
out<<"\n\n\ndeque:\n";
for (deque<double>::iterator iter=deq.begin(); iter<deq.end();
++iter){
out<<*iter<<" ";
}
out<<"\ntime: "<<dequeTime;
/*запись результата работы списка в фаил*/
out<<"\n\n\nlist:\n";
for (list<double>::iterator iter=lt.begin(); iter!=lt.end();
++iter){
out<<*iter<<" ";
}
out<<"\ntime: "<<listTime;
out.close();
return 0;
}
Входной файл содержит числа: 3 2 1 4 2 3 4 8 9 17 9 2 3 4 2 9 9… Эта последовательность чисел повторяется несколько раз, чтобы измерить скорость удаления элементов.
Результат работы программы:
vector:
3 2 1 4 8 9 17
time: 8
deque:
3 2 1 4 8 9 17
time: 169
list:
3 2 1 4 8 9 17
time: 7
Алгоритмы 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
Адаптеры контейнеров
В 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
Ассоциативные контейнеры