2017-12-14
259
| Операция | Назначение |
| flst.unique() | Удаляет из списка дубликаты |
| flst.unique(op) | Удаляет из списка дубликаты, для которых op возвращает true |
| flst.splice_after(pos, flst1) | Перемещает все элементы списка flst1 в список flst и размещает их сразу за позицией итератора pos |
| flst.splice_after(pos, flst1,pos1) | Перемещает элемент, занимаю-щий позицию pos1 в списке flst1, в список flst и размещает его сразу за позицией итератора pos (списки flst и flst1 могут совпадать) |
| flst.splice_after(pos, flst1,beg1,end1) | Перемещает все элементы из диапазона [beg1,end1) списка flst1 в flst после элемента, заданного итератором pos |
| flst.sort() | Сортирует все элементы списка с помощью оператора < |
| flst.sort(op) | Сортирует все элементы списка по критерию, заданному бинар-ным предикатом op |
| flst.merge(flst1) | Сливает два отсортированных списка: вставляет все элементы списка flst1 в список flst с сохранением сортировки; список flst1 после этого пуст |
| flst.merge(flstl,op) | Сливает два отсортированных списка: вставляет все элементы списка flst1 в список flst с сохранением сортировки по критерию op; список flst1 после этого пуст |
| flst.reverse() | Изменяет порядок следования всех элементов на противо-положный |
|
|
|
Рассмотрим пример программы, демонстрирующей использование специальных функций-членов однонаправленных списков.
//Листинг 26.2
#include <forward_list>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
void printLists(const string s,
const forward_list<int> & lst1,
const forward_list<int> & lst2)
{
cout << s << endl;
cout << " listl:";
copy(lst1.cbegin(), lst1.cend(),
ostream_iterator<int>(cout, " "));
cout << endl << " list2:";
copy(lst2.cbegin(), lst2.cend(),
ostream_iterator<int>(cout, " "));
cout << endl;
}
int main()
{
// создаем два однонаправленных списка
forward_list<int> listl = { 1, 2, 3, 4 };
forward_list<int> list2 = { 77, 88, 99 };
printLists("initial:", listl, list2);
// вставляем шесть новых элементов
//в начало однонаправленного списка list2
list2.insert_after(list2.before_begin(),
99);
list2.push_front(10);
list2.insert_after(list2.before_begin(),
{ 10, 11, 12, 13 });
printLists("6 new elems:", listl, list2);
//вставляем все элементы однонаправленного
//списка list2 в начало списка listl
listl.insert_after(listl.before_begin(),
list2.begin(),
list2.end());
printLists("list2 into listl:",
listl, list2);
// удаляем второй элемент и элементы,
// расположенные после элемента,
// имеющего значение 99
list2.erase_after(list2.begin());
list2.erase_after(find(list2.begin(),
list2.end(), 99),
list2.end());
printLists("delete 2nd and after 99:",
listl, list2);
// сортируем последовательный список listl,
// присваиваем его списку list2 и
// удаляем дубликаты
listl.sort();
list2 = listl;
list2.unique();
printLists("sorted and unique:",
listl, list2);
// объединяем упорядоченные списки
// в списке listl
listl.merge(list2);
printLists("merged:", listl, list2);
}
Результаты выполнения программы:
initial:
listl:1 2 3 4
list2:77 88 99
6 new elems:
listl:1 2 3 4
list2:10 11 12 13 10 99 77 88 99
list2 into listl:
|
|
|
listl:10 11 12 13 10 99 77 88 99 1 2 3 4
list2:10 11 12 13 10 99 77 88 99
delete 2nd and after 99:
listl:10 11 12 13 10 99 77 88 99 1 2 3 4
list2:10 12 13 10 99
sorted and unique:
listl:1 2 3 4 10 10 11 12 13 77 88 99 99
list2:1 2 3 4 10 11 12 13 77 88 99
merged:
listl:1 1 2 2 3 3 4 4 10 10 10 11 11 12 12 13 13 77 77 88 88 99 99 99
list2:
Рассмотрим задачу:
Создать следующие классы: класс студент с полями: фамилия и номер зачетной книжки; класс группа студентов.
В классе студент перегрузить операции помещения и извлечения из потока.
В классе группа студентов в качестве поля использовать контейнер двунаправленный список. В классе реализовать методы добавления в список объектов, удаления из списка и поиск в списке, используя методы контейнера. Перегрузить операции помещения и извлечения из потока.
Для осуществления поиска по фамилии и сортировки по фамилии и номеру зачетной книжки создать функциональный класс.
Написать программу, демонстрирующую работу с данными классами.
Решение задачи:
По условию задачи в программе определены три класса: student, group и функциональный класс funct.
В классе student два поля-данных (name и num), два конструктора: без параметров и с двумя параметрами, методы доступа к полям класса. Для перегрузки операций помещения в поток и извлечения из потока используются дружественные функции.
В классе group одно поле - двунаправленный список, элементами которого являются объекты класса student (list<student>). При реализации методов добавления и сортировки используем методы класса list<student>. При реализации поиска и удаления используются методы класса list<student> и алгоритмы STL:
Алгоритм count_if():
difference_type count_if(Iterator beg,
Iterator end, UnaryPredicate op);
подсчитывает элементы в интервале [beg,end), для которых унарный предикат op возвращает значение true. Возвращаемое значение difference_type соответствует типу разности итераторов (как правило, long).
Алгоритм find_if():
Iterator find_if(Iterator beg,Iterator end,
UnaryPredicate op);
возвращает итератор, указывающий на найденное значение, или итератор конца интервала, если требуемое значение не найдено. В качестве первых двух параметров задается интервал, на котором осуществляется поиск, а качестве третьего параметра – унарный предикат, задающий условие поиска.
Операции помещения в поток и извлечения из потока реализованы как дружественные функции.
В функциональном классе funct два поля: mode и fam, два конструктора (первый - для инциализации поля mode, второй – для инициализации поля fam), перегруженная операция вызова функции: для задания критерия поиска - функция с одним параметром типа student, возвращающая булевское значение; для задания критерия сортировки - бинарный предикат, два параметра которого имеют тип student. По условию задачи для типа данных student должны быть определены два критерия сортировки: по фамилии и по номеру зачетки. В зависимости от значения поля mode в бинарном предикате выполняется сравнение либо по полю name (при mode=0), либо по полю num (при mode=1) двух объектов класса student, передаваемых как параметры функции. В реализации критерия поиска по фамилии используется поле fam, значение которого сравнивается со значением поля name передаваемого в качестве параметра объекта класса student.
В функции main() создается объект класса group и тестируются методы данного класса и перегруженные операции включения в поток и извлечения из потока.
//Листинг 26.3
#include <iostream>
#include<fstream>
#include <list>
#include<algorithm>
#include <cstring>
#include<iterator>
using namespace std;
//Класс студент
class student{
char name[20]; // фамилия студента
int num; //номер зачетной книжки
public:
//конструктор без параметров
student(){}
//конструктор с параметрами
student(char *fam, int nm){
strcpy_s(name, fam);
num = nm;
}
const char* getname()
{
return name;
}
int getnum()
{
return num;
}
//перегруженные функции помещения в поток
//и извлечения из потока
friend ostream& operator<<(ostream &stream,
student ob);
friend istream& operator>>(istream &stream,
|
|
|
student &ob);
};
ostream& operator<<(ostream &stream,
student ob)
{
stream << ob.name << "\t";
stream << ob.num << "\n";
return stream;
}
istream& operator>>(istream &stream,
student &ob)
{
stream >> ob.name;
stream >> ob.num;
return stream;
}
//функциональный класс
//с перегруженными операциями вызова функции
class funct
{
int mode;
char fam[30];
public:
//конструктор c умолчанием
funct(int a=0)
{
mode = a;
}
//конструктор с параметром
funct(char * s)
{
strcpy_s(fam, s);
}
//унарный предикат
//критерий поиска
//по фамилии для класса student
bool operator()(student a)
{
if (strcmp(fam, a.getname()) == 0)
return true;
return false;
}
//бинарный предикат
//с разными критериями сортировки
//для класса student
bool operator()(student a, student b)
{
//по фамилии
if (mode == 0){
if (strcmp(a.getname(), b.getname())<0)
return true;
return false;
}
//по номеру зачетки
if (mode == 1)
return a.getnum()<b.getnum();
}
};
//класс группа студентов
class group{
//в качестве поля используем
//контейнер двунаправленный список
list<student> l;
public:
//добавление объекта класса
//студент в конец списка
void dobav(student stud)
{
l.push_back(stud);
}
//сортировка по фамилии
void sortname()
{
funct sravn;
//Сортирует все элементы по критерию sravn
//при mode=0
l.sort(sravn);
}
//сортировка по номеру зачетки
void sortnum()
{
funct sravn(1);
//Сортирует все элементы по критерию sravn
// при mode=1
l.sort(sravn);
}
//поиск и вывод на экран
//студентов с данной фамилией
void find(char * fam)
{
//создаем итераторы для работы со списком
list<student>::iterator ptr, p;
funct poisk(fam);
//определяем сколько студентов
//имеют данную фамилию
int n = count_if(l.begin(),
l.end(), poisk);
if (n>0){
p = l.begin();
for (int i = 1; i <= n; i++)
{
ptr = find_if(p, l.end(), poisk);
cout << *ptr;
ptr++;
p = ptr;
}
}
else
cout << "Студентов с фамилией "
<< fam << " нет!" << endl;
}
//удаление из списка всех студентов
//с данной фамилией
void del(char * fam)
{
//создаем итераторы для работы со списком
list<student>::iterator ptr, p;
funct poisk(fam);
//определяем сколько студентов
//имеют данную фамилию
int n = count_if(l.begin(),
l.end(), poisk);
if (n>0){
p = l.begin();
for (int i = 1; i <= n; i++)
{
ptr = find_if(p, l.end(), poisk);
l.erase(ptr);
p = l.begin();
}
}
else
cout << "Студентов с фамилией "
<< fam << " нет!" << endl;
|
|
|
}
//перегруженная операция вставки в поток
friend ostream& operator<<(ostream& st,
group &o)
{
for (auto ptr = o.l.begin();
ptr!= o.l.end(); ++ptr)
st << *ptr;
return st;
}
//перегруженная операция
//извлечения из потока
friend istream& operator>>(istream& st,
group &o)
{
student ob;
st >> ob;
o.l.push_back(ob);
return st;
}
};
int main()
{
setlocale(LC_CTYPE, "Russian");
//создаем список
group ob;
//добавляем объекты класса student
// в конец списка
ob.dobav(student("Petrov", 128));
ob.dobav(student("Sidorov", 456));
ob.dobav(student("Antonov", 345));
ob.dobav(student("Petrov", 555));
cout << "Список группы:" << endl
<< ob << endl;
//сортировка списка группы по фамилиям
ob.sortname();
cout <<
"Список группы после сортировки по фамилии:"
<< endl << ob << endl;
//сортировка списка группы
//по номерам зачеток
ob.sortnum();
cout <<
"Список группы после сортировки по номеру зачетки:"
<< endl << ob << endl;
//поиск в списке группы студентов
//с данной фамилией
cout << "Введите фамилию для поиска:"
<< endl;
char temp[20];
cin >> temp;
ob.find(temp);
cout << endl;
//удаление из списка группы
//студентов с данной фамилией
ob.del(temp);
cout <<
"Список группы после удаления студентов с фамилией"
<< temp << ":"<< endl << ob << endl;
cout<<"Введите информацию о студенте с
клавиатуры:"<< endl;
cin >> ob;
cout <<
"Список группы после ввода с клавиатуры:"
<< endl << ob << endl;
return 0;
}
Результаты выполнения программы:
Список группы:
Petrov 128
Sidorov 456
Antonov 345
Petrov 555
Список группы после сортировки по фамилии:
Antonov 345
Petrov 128
Petrov 555
Sidorov 456
Список группы после сортировки по номеру зачетки:
Petrov 128
Antonov 345
Sidorov 456
Petrov 555
Введите фамилию для поиска:
Petrov
Petrov 128
Petrov 555
Список группы после удаления студентов с фамилией Petrov:
Antonov 345
Sidorov 456
Введите информацию о студенте с клавиатуры
Dedov 1234
Список группы после ввода с клавиатуры:
Antonov 345
Sidorov 456
Dedov 1234
Задание:
Создать классы согласно варианту.
В классе из пункта а) варианта перегрузить операции помещения и извлечения из потока.
В классе из пункта б) варианта в качестве поля использовать контейнер однонаправленный список. В классе реализовать методы добавления, удаления и замены элементов в список объектов, используя методы контейнера. Перегрузить операции помещения и извлечения из потока.
Для осуществления поиска и сортировки по критериям создать функциональный класс.
При поиске осуществлять сохранение выбранных записей в контейнер - двунаправленный список.
Можно добавить другие методы.
Написать программу, демонстрирующую работу с данными классами.
Вариант 1
а) Класс аналогово-цифровой преобразователь (АЦП) содержит поля: название микросхемы, название фирмы производителя, тип АЦП, разрядность выходных данных, скорость преобразования аналогового сигнала в цифровую форму.
б) Класс список аналогово-цифровых преобразователей. Поиск и сортировку выполнять по названию микросхемы, по названию фирмы производителя, по разрядности выходных данных.
Вариант 2:
а) Класс цифро-аналоговый преобразователь (ЦАП) содержит поля: название микросхемы, название фирмы производителя, тип ЦАП, разрядность, максимальная частота дискретизации, динамический диапазон.
б) Класс список цифро-аналоговых преобразователей. Поиск и сортировку выполнять по названию микросхемы, по названию фирмы производителя, максимальной частоте дискретизации.
Вариант 3
а) Класс сигнал содержит поля: тип сигнала, длительность сигнала, динамический диапазон, ширина спектра сигнала.
б) Класс список сигналов. Поиск и сортировку выполнять по типу сигнала, длительности сигнала, ширине спектра сигнала.
Вариант 4
а) Класс файл содержит поля: каталог, имя файла, расширение, дата и время создания, атрибуты «только чтение», «скрытый», «системный», признак удаления, количество выделенных секторов (размер сектора принять равным 512 байт).
б) Класс список файлов. Поиск и сортировку выполнять по каталогу, дате создания, по признаку удаления.
Вариант 5
а) Класс модель компьютера содержит поля: код и название марки компьютера, тип процессора, частота работы процессора, объем оперативной памяти, объем жесткого диска, объем памяти видеокарты, стоимость компьютера в условных единицах и количество экземпляров, имеющихся в наличии.
б) Класс список моделей компьютера. Поиск и сортировку выполнять по типу процессора, объему ОЗУ, памяти жесткого диска.
Вариант 6
а) Класс звуковой формат содержит поля: название формата, расширение файла, квантование, частота дискретизации, число каналов, величина потоков данных с диска, степень сжатия.
б) Класс список звуковых форматов. Поиск и сортировку выполнять по названию формата, расширению файла, степени сжатия.
Вариант 7
а) Класс модем содержит поля: название марки модема, название фирмы производителя, тактовая частота сигнального процессора, объем оперативной памяти, количество портов ввода-вывода, потребляемая мощность.
б) Класс список модемов. Поиск и сортировку выполнять по названию марки модема, названию фирмы производителя, объему оперативной памяти.
Вариант 8
а) Класс кабель связи «витая пара» содержит поля: название фирмы производителя, число жил, тип конструкции экрана, материал изоляции, категория кабеля.
б) Класс список кабелей связи «витая пара». Поиск и сортировку выполнять по названию фирмы производителя, числу жил, категории кабеля.
Вариант 9
а) Класс волоконно-оптический кабель содержит поля: название фирмы производителя, материал изготовления сердцевины, диаметр сердцевины, показатель преломления сердцевины, показатель преломления оболочки.
б) Класс список волоконно-оптических кабелей. Поиск и сортировку выполнять по названию фирмы производителя, материалу изготовления сердцевины, диаметру сердцевины.
Вариант 10
а) Класс коаксиальный кабель содержит поля: название фирмы производителя, волновое сопротивление, область использования, материал внутреннего проводника, материал изоляции.
б) Класс список коаксиальных кабелей. Поиск и сортировку выполнять по названию фирмы производителя, волновому сопротивлению, материалу внутреннего проводника.
Вариант 11
а) Класс микроконтроллер содержит поля: название модели; название фирмы производителя, разрядность ядра, объем ОЗУ, объем флеш-памяти, тактовая частота ядра.
б) Класс список микроконтроллеров. Поиск и сортировку выполнять по названию модели, названию фирмы производителя, разрядности ядра.
Вариант 12
а) Класс интернет-соединение содержит поля: название организации интернет-провайдера, вид соединения, скорость передачи данных, колебание сетевой задержки.
б) Класс список интернет-соединений. Поиск и сортировку выполнять по названию организации интернет-провайдера, виду соединения, скорости передачи данных.
Вариант 13
а) Класс пассивный элемент электрических цепей содержит поля: название элемента, сопротивление, емкость, индуктивность.
б) Класс список пассивных элементов электрических цепей. Поиск и сортировку выполнять по названию элемента, сопротивлению, емкости.
Вариант 14
а) Класс гармонический сигнал содержит поля: фаза, амплитуда, частота.
б) Класс список гармонических сигналов. Поиск и сортировку выполнять по фазе, амплитуде, частоте.
Вариант 15
а) Класс система связи содержит поля: название, тип связи, скорость передачи данных.
б) Класс список систем связи. Поиск и сортировку выполнять по названию, типу связи, скорости передачи данных.
Практическое занятие 3. Ассоциативные контейнеры: множество и мультимножество
Множество (set) и мультимножество (multiset) – это ассоциативные контейнеры. Элементы в этих контейнерах хранятся отсортированными. Чтобы использовать множество или мультимножество в программе, необходимо включить в нее заголовочный файл <set>. Они отличаются только тем, что мультимножества могут содержать дубликаты, а множества — нет (рис. 27.1.).
Множество Мультимножество
|
Рис. 27.1. Множество и мультимножество
Типы множества и мультимножества определяются как шаблоны классов в пространстве имен std:
namespace std {
template <class Т,class Compare = less<T>,
class Allocator = allocator< T > >
class set;
template <class T, class Compare =less<T>,
class Allocator = allocator<T> >
class multiset;
}
Элементы множества или мультимножества относятся к произвольному типу Т, поддерживающему присваивание, копирование и сравнение по критерию сортировки. Необязательный второй параметр шаблона определяет критерий сортировки. По умолчанию используется критерий less. Объект функции less сортирует элементы, сравнивая их оператором <. Необязательный третий параметр шаблона определяет модель памяти. По умолчанию используется модель allocator, определенная в стандартной библиотеке С++.
Сравнение элементов при упорядочении осуществляется в соответствии с заданным критерием. Критерий сравнения должен определять строгое слабое упорядочение (strict weak orderning), определяемое следующими четырьмя свойствами:
1. Антисимметричностью.
Для оператора < это значит, что если выражение x < y имеет значение true, то выражение y < x имеет значение false. Для предиката pred() это значит, что если выражение pred(x, y) имеет значение true, то выражение pred(y, x) имеет значение false.
2. Транзитивностью.
Для оператора < это значит, что если выражение x < y равно true и значение выражения y < z равно true, то значение выражения x < z равно true. Для предиката pred() это значит, что если выражение pred(x, y) равно true и значение выражения pred(y, z) равно true, то значение выражения pred(x, z) равно true.
3. Иррефлексивностью.
Для оператора < это значит, что значение выражения x < x всегда равно false. Для предиката pred() это значит, что значение выражения pred(x, x) всегда равно false.
4. Транзитивностью эквивалентности (tratsitivity of equivalence), которое, грубо говоря, означает следующее: если объект a эквивалентен объекту b, а объект b эквивалентен объекту c, то объект а эквивалентен объекту c.
Для оператора < это значит, что если значение выражения !(a < b) &&!(b < a) равно true и значение выражения !(b < c) &&!(c < b) равно true, то значение выражения !(a < c) &&!(c < a) равно true. Для предиката pred() это означает, что если значения выражений pred(a, b), pred(b, a), pred(b, c) и pred(c, b) равны false, то значения выражений pred(a, c) и pred(c, a) равны false.
Это значит, что следует различать отношения «меньше» и «равно». Оператор <= не удовлетворяет этому требованию.
Основываясь на этих требованиях, можно использовать критерий ссравнения и для проверки эквивалентности. Иначе говоря, два элемента считаются дубликатами, если ни один из них не меньше другого (оба выражения a < b и b < a равны false или и pred(x, y), и pred(y, x) равны false).
Для мультимножеств порядок эквивалентных элементов является случайным, но устойчивым. Таким образом, вставки и удаление сохраняют относительный порядок следования эквивалентных элементов (это гарантируется стандартом С++11).
Множества set и мультимножества multiset в STL реализуются в виде сбалансированных красно-чёрных деревьев.
Операции с множествами и мультимножествами рассмотрим по группам (табл. 27.1 – 27.6).
Таблица 27.1
