2017-12-14
316
| Операция | Назначение |
| s.insert(elem) | Вставляет копию elem и возвращает позицию нового элемента; для множеств также возвращается признак успешного выполнения операции |
| s.insert(pos,elem) | Вставляет копию elem и возвращает позицию нового элемента (pos определяет рекомендуемую позицию, с которой следует начинать поиск позиции вставляемого элемента) |
| s.insert(beg,end) | Вставляет копию всех элементов интервала [beg,end) (и не возвращает значения) |
| s.insert(initlist) | Вставляет копию всех элементов списка инициализации initlist (не возвращает ничего) (стандарт С++ 11) |
| s.erase(elem) | Удаляет все элементы со значением elem и возвращает количество удаленных элементов |
| s.erase(pos) | Удаляет элемент в позиции ите-ратора pos и возвращает сле-дующую позицию (до стандарта С++ 11 не возвращал ничего) |
| s.erase(beg,end) | Удаляет все элементы из интервала [beg,end) и возвращает следующую позицию (до стандарта С++ 11 не возвращал ничего) |
| s.clear() | Удаляет все элементы (контейнер остается пустым) |
Рассмотрим пример программы, демонстрирующей операции с множествами:
|
|
|
//Листинг 27.2
#include<iostream>
#include<set>
#include<iterator>
using namespace std;
int main() {
/* Тип коллекции:
* - дубликаты запрещены
* - элементы типа int
* - сортировка по убыванию
*/
typedef set<int,greater<int> > IntSet;
IntSet coll1; // Пустое множество
// Вставка элементов в произвольном порядке
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(1);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
// Перебор и вывод всех элементов
IntSet::iterator pos;
for(pos=coll1.begin();pos!=coll1.end();
++pos)
{ cout<<*pos<<' ';}
cout<<endl;
// Попытка повторной вставки значения 4
// и обработка возвращаемого значения
pair<IntSet::iterator,bool> status
=coll1.insert(4);
if(status.second) {
cout<<"4 inserted as element "
<<distance(coll1.begin(),status.first)
+ 1<< endl;}
else {
cout<<"4 already exists"<<endl;}
// Присваивание элементов другому множеству,
// упорядоченному по возрастанию
set<int> coll2(coll1.begin(),coll1.end());
// Вывод всех элементов копии
copy(coll2.begin(),coll2.end(),
ostream_iterator<int>(cout," "));
cout<<endl;
// Удаление всех элементов до зпемента
// со значением 3
coll2.erase(coll2.begin(),coll2.find(3));
// Удаление всех элементов со значением 5
int num;
num = coll2.erase(5);
cout<<num<<" element(s) removed" << endl;
// Вывод всех элементов
copy(coll2.begin(),coll2.end(),
ostream_iterator<int>(cout," "));
cout<<endl;
return 0;
}
Результаты выполнения программы:
6 5 4 3 2 1
4 already exists
1 2 3 4 5 6
1 element(s) removed
3 4 6
Сначала определение типа создает сокращенное имя типа для множества целых чисел, упорядоченного по убыванию:
typedef set<int.greater<int> > IntSet;
Затем создается пустое множество и вставляется в него несколько элементов функцией insert():
IntSet coll1;
coll1.insert(4);
Элемент со значением 5 вставляется дважды. Вторая вставка игнорируется, поскольку дубликаты в множествах запрещены.
|
|
|
После вывода всех элементов программа снова пытается вставить элемент 4.
Следующая команда создает новое множество элементов типа int, упорядоченных по возрастанию, и инициализирует его элементами прежнего множества:
set<int> coll2(coll1.begin(),coll1.end());
Контейнеры используют разные критерии сортировки, поэтому их типы различаются, а прямое присваивание или сравнение невозможно. Тем не менее алгоритмы обычно способны работать с разными тинами контейнеров, если типы их элементов совпадают или могут быть преобразованы друг к другу.
Следующая команда удаляет все элементы, предшествующие элементу со значением 3:
col12.erase (col12.begin(),col12.find(3));
При этом элемент со значением 3 находится на открытом конце интервала и поэтому не удаляется.
В конце программы из контейнера удаляются все элементы со значением 5:
int num;
num = coll2.erase(5);
cout <<num<<" element(s) removed"<<endl;
Для мультимножеств эта программа выглядит несколько иначе и выводит другие результаты:
//Листинг 27.3
#include <iostream>
#include <set>
#include<iterator>
using namespace std;
int main() {
/* Тип коллекции;
* - дубликаты разрешены
* - элементы типа int
* - сортировка по убыванию */
typedef multiset<int,greater<int> > IntSet;
IntSet coll1; // Пустое мультимножество
// Вставка элементов в произвольном порядке
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(1);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
//Перебор и вывод всех элементов
IntSet::iterator pos;
for(pos= coll1.begin();pos!=coll1.end();
++pos)
{ cout<<*pos<<' ';}
cout<<endl;
// Повторная вставка значения 4
//и обработка возвращаемого значения
IntSet::iterator ipos = coll1.insert(4);
cout << "4 inserted as element "
<<distance(coll1.begin(),ipos)
+1 <<endl;
// Присваивание элементов другому множеству.
// упорядоченному по возрастанию
multiset<int> coll2(coll1.begin(),
coll1.end());
// Вывод всех элементов копии
copy(coll2.begin(),coll2.end(),
ostream_iterator<int>(cout," "));
cout << endl;
// Удаление всех элементов
//до элемента со значением 3
coll2.erase(coll2.begin(),coll2.find(3));
// Удаление всех элементов со значением 5
int num;
num = coll2.erase(5);
cout << num << " element(s) removed"
<< endl;
// Вывод всех элементов
copy(coll2.begin(),coll2.end(),
ostream_iterator<int>(cout," "));
cout << endl;
return 0;
}
Результат выполнения программы:
6 5 5 4 3 2 1
4 inserted as element 5
1 2 3 4 4 5 5 6
2 element(s) removed
3 4 4 6
Тип set везде заменен типом multiset. Кроме того, возвращаемое значение функции insert() обрабатывается иначе:
IntSet::iterator ipos = coll1.insert(4);
cout <<"4 inserted as element "
<< distance(colll.begin().ipos)
+1<<endl;
Поскольку в мультимножествах разрешены дубликаты, вставка завершится неудачей только при сгенерированном исключении. По этой причине в возвращаемом значении передается только итератор с позицией нового элемента.
Рассмотрим следующую задачу:
Заданы три множества, элементами которых могут быть следующие числа {1, 3, 5, 7, 9}.
Определить:
- Какие числа принадлежат всем трем множествам?
- Какие числа принадлежат хотя бы одному множеству?
- Какие числа из допустимых не принадлежат ни одному из множеств?
Написать программу на языке С++, в которой используется ассоциативный контейнер STL множество и его операции.
Решение задачи:
Для задания допустимых значений элементов множества зададим перечислимый тип mn, определяющий пять именованных констант с соответствующими инициализаторами.
В программе будем работать с объектами класса set<mn> и определим следующие функции:
- функция vvod(), предназначенная для заполнения множества случайным образом. В качестве параметра функции передается ссылка на set<mn>, функция ничего не возвращает. Для генерации случайных чисел используется функция rand(), а для добавления подходящего элемента в множество операция insert();
- функция output (), имеющая один параметр типа set<mn>, выводящая на экран содержимое множества или соответствующее сообщение, если множество пусто. Вывод осуществляется с помощью итератора. Для проверки множества на пустоту используется операция empty().
|
|
|
- функция f1(), определяющая элементы, при-надлежащие всем трем множествам. Функция имеет три параметра типа set<mn>. Выводит на экран либо элементы, либо сообщение, если элементов нет. Для определения принадлежности элемента множеству используется операция count(elem), возвращающая 1, если elem принадлежит множеству, и 0 в противном случае.
- аналогичные функции: f2(), определяющая элементы, принадлежащие хотя бы одному множеству, и f3(), определяющая какие допустимые числа не являются элементами ни одного множества.
В функциях f1(), f2() и f3() используются логические операции.
В функции main() создаются три множества, случайным образом заполняются, выводятся на экран. Демонстрируется работа функций f1(), f2() и f3(), которым в качестве параметров передаются эти три множества.
//Листинг 27.4
#include<iostream>
#include<time.h>
#include<set>
using namespace std;
//определяем числа
//которые могут быть элементами множества
enum mn { one = 1, three = 3, five=5, seven=7,
nine=9};
//функция заполнения множества
//случайным образом
void vvod(set<mn> &s)
{
int n, m;
n = rand() * 30 / RAND_MAX + 1;
for (int i = 1; i <= n; ++i)
{
m = rand() * 9 / RAND_MAX + 1;
if (m % 2!= 0) s.insert((mn)m);
}
}
//функция вывода на экран элементов множества
void output(set<mn> s)
{
if (s.empty())
cout << "Множество пусто"<< endl;
else
for(auto ptr=s.begin(); ptr!= s.end();
++ptr)
cout << *ptr << " ";
cout << endl;
}
//функция, определяющая элементы,
// принадлежащие всем множествам
void f1(set<mn> s1, set<mn> s2, set<mn> s3)
{
int count = 0;
for (int i = 1; i <= 9; i += 2)
if (s1.count((mn)i) && s2.count((mn)i) &&
s3.count((mn)i))
{
cout << i << " ";
++count;
}
if (count == 0) cout << "Элементов нет";
cout << endl;
}
//функция, определяющая элементы,
//принадлежащие хотя бы одному множеству
void f2(set<mn> s1, set<mn> s2, set<mn> s3)
{
int count = 0;
for (int i = 1; i <= 9; i += 2)
if (s1.count((mn)i) || s2.count((mn)i) ||
s3.count((mn)i))
{
cout << i << " ";
++count;
}
if (count == 0) cout << "Элементов нет";
cout<<endl;
}
//функция, определяющая какие допустимые числа
//не являются элементами ни одного множества
|
|
|
void f3(set<mn> s1, set<mn> s2, set<mn> s3)
{
int count = 0;
for (int i = 1; i <= 9; i += 2)
if ((s1.count((mn)i) || s2.count((mn)i) ||
s3.count((mn)i)) == 0)
{
cout << i << " ";
++count;
}
if (count == 0) cout << "Чисел нет";
cout << endl;
}
int main()
{
setlocale(LC_ALL, "Russian");
srand(time(NULL));
//создаем три множества
set<mn> s1, s2, s3;
//заполняем множества случайным образом
vvod(s1);
vvod(s2);
vvod(s3);
//выводим на экран элементы трех множеств
cout << "Множество 1:" << endl;
output(s1);
cout << "Множество 2:" << endl;
output(s2);
cout << "Множество 3:" << endl;
output(s3);
cout <<
"Элементы,принадлежащие всем множествам:"
<< endl;
f1(s1, s2, s3);
cout <<
"Элементы, принадлежащие хотя бы одному
множеству:" << endl;
f2(s1, s2, s3);
cout << "Допустимые числа, не принадлежащие
ни одному множеству:" << endl;
f3(s1, s2, s3);
return 0;
}
Результаты выполнения программы:
Запуск 1:
Множество 1:
3 7 9
Множество 2:
Множество пусто
Множество 3:
1 3 5 7 9
Элементы, принадлежащие всем множествам:
Элементов нет
Элементы, принадлежащие хотя бы одному множеству:
1 3 5 7 9
Допустимые числа, не принадлежащие ни одному множеству:
Чисел нет
Запуск 2:
Множество 1:
3 5 7 9
Множество 2:
Множество 3:
5 7 9
Элементы, принадлежащие всем множествам:
Элементы, принадлежащие хотя бы одному множеству:
3 5 7 9
Допустимые числа, не принадлежащие ни одному множеству:
Задание:
Написать программу на языке С++. Использовать множества/мультимножества подходящего типа. Для выполнения операций с множествами/мультимножествами воспользоваться алгоритмами работы с множествами/мультимножествами из STL.
Вариант 1
В системе связи можно одновременноиспользовать несколькоаналогово-цифровых преобразователей (АЦП) разных типов. Типы АЦП могут быть следующими: параллельные прямого преобразования, параллельно-последовательные прямого преобразования, конвейерные, последовательные прямого преобразования, дифференциального кодирования. Были созданы три системы связи.
Определить: какого типа АЦП используются во всех системах связи; какого типа АЦП используются хотя бы в одной системе связи; какого типа АЦП не используются ни в одной системе связи.
Вариант 2
Дан текст из цифр и строчных латинских букв, за которыми следует точка. Определить, каких букв — гласных или согласных — больше в этом тексте; вывести в алфавитном порядке все согласные буквы, которые входят только в одно слово.
Вариант 3
В системе связи можно одновременноиспользовать несколькоцифро-аналоговых преобразователей (ЦАП) разных типов. Типы ЦАП могут быть следующими: широко-импульсный модулятор, передискретизации, взвешивающего типа, лестничного типа. Были созданы три системы связи.
Определить: какого типа ЦАП используются во всех системах связи; какого типа ЦАП используются только в одной системе связи; какого типа ЦАП используются хотя бы в двух системах связи.
Вариант 4
Дан текст из строчных латинских букв, за которыми следует точка. Вывести все буквы, входящие в текст не менее двух раз; все согласные буквы, входящие только в одно слово.
Вариант 5
В системе связи можно одновременноиспользовать кабель связи «витая пара» с различным материалом изоляции. Материал изоляции может быть следующим: поливинилхлорид, полипропилен, полиэтилен, вспененный полиэтилен, тефлон. Были созданы четыре системы связи.
Определить какой материал изоляции не использовался ни в одной системе; какой материал изоляции использовался хотя бы в двух системах связи; какой материал изоляции использовался только в одной системе связи.
Вариант 6
Дан текст на русском языке. Вывести в алфавитном порядке все гласные буквы, присутствующие в каждом слове; все согласные, которые не входят хотя бы в одно слово.
Вариант 7
В системе связи можно одновременноиспользовать волоконно-оптический кабель с различным материалом изготовления сердцевины. Материал изготовления сердцевины может быть следующим: кварцевое стекло, фторцирконат, фторалюминат, халькогенидные стекла, полиметилметакрилат. Были созданы три системы связи.
Определить какой материал сердцевины использовался во всех системах связи; какой материал сердцевины использовался только в двух системах связи; какой материал сердцевины не использовался ни в одной системе связи.
Вариант 8
Дан текст на русском языке. В алфавитном порядке вывести все гласные буквы (а, е, ё, и, й, о, у, ы, э, ю, я), входящие в этот текст более двух раз; все согласные, которые входят только в одно слово.
Вариант 9
В системе связи можно одновременноиспользовать коаксиальный кабель с различным материалом внутреннего проводника. Материал изготовления внутреннего проводника может быть следующим: медь, алюминиевый сплав, омеднённая сталь, омеднённый алюминий, посеребрённая медь. Были созданы три системы связи.
Определить какой материал внутреннего проводника использовался во всех системах связи; какой материал внутреннего проводника использовался только в двух системах связи; какой материал внутреннего проводника использовался только в одной системе связи.
Вариант 10
Дан текст из строчных латинских букв, за которыми следует точка. Вывести все буквы, входящие в текст по одному разу; все согласные, которые входят в каждое слово.
Вариант 11
В системе связи можно одновременноиспользовать кабель связи «витая пара» с различным типом конструкции экрана. Тип конструкции экрана может быть следующим: U/UTP, F/UTP, S/UTP, SF/UTP, F/FTP, S/FTP, SF/FTP. Были созданы три системы связи.
Определить какой тип экрана не использовался ни в одной системе; какой тип экрана использовался хотя бы в двух системах связи; какой тип экрана использовался хотя бы в одной системе связи.
Вариант 12
Дан текст на русском языке. Вывести в алфавитном порядке все согласные буквы, не найденные ни в одном слове; все гласные буквы, которые входят в текст более двух раз.
Вариант 13
В системе связи можно одновременноиспользовать коаксиальный кабель с различным материалом изоляции. Материал изоляции может быть следующим: полиэтилен, вспененный полиэтилен, сплошной фторопласт, фторопластовая лента, кордельно-трубчатый повив, шайбы. Были созданы четыре системы связи.
Определить какой материал изоляции использовался во всех системах связи; какой материал изоляции использовался только в трех системах связи; какой материал использовался хотя бы в одной системе связи.
Вариант 14
Дан текст на русском языке. Вывести в алфавитном порядке все согласные буквы, не найденные ни в одном слове; все гласные буквы, которые входят в текст более двух раз.
Вариант 15
Дан текст на русском языке. Вывести в алфавитном порядке все звонкие согласные буквы, которые найдены хотя бы в одном слове; все гласные буквы, которые не входят только в одно.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. Дейтел Х.М., Дейтел П.Дж. Как программировать на С++. –М.: Бином-Пресс, 2011. – 1456 с.
2. Джосаттис Н.М. Стандартная библиотека С++: справочное руководство, 2-е изд. – М.: ООО «И.Д.Вильямс», 2014. -1136 с.
3. Клюшин Д.А. Полный курс C++. Профессиональная работа. – М.: Издательский дом «Вильямс», 2004. – 672 с.
4. Лаптев В.В. С++. Объектно-ориентированное програм-мирование. Учебное пособие. – СПб.: Питер, 2008. – 464 с.
5. Лаптев В.В., Морозов А.В., Бокова А.В. С++. Объектно-ориентированное программирование. Задачи и упражнения. – Спб.: Питер, 2007. – 288 с.
6. Леен Аммерааль STL для программистов на С++. – М.: ДМК Пресс, 2002. – 240 с.
7. Мюссер Д.Р., Дердж Ж.Дж., Сейни А. С++ и STL: справочное руководство. – М.:ООО «И.Д.Вильямс», 2010. – 432 с.
8. Павловская Т.А. С/С++. Процедурно и объектно-ориентированное программирование. Учебник для вузов. - СПб.: Питер, 2015. - 496 с.
9. Подбельский В.В. Стандартный Си++. Учебное пособие. – М.: Финансы и статистика, 2008. – 688 с.
10. Прата С. Язык программирования С++. Лекции и упражнения. – М.: Издательский дом «Вильямс», 2015. – 1244 с.
11. Шилдт Г. C++: базовый курс. – М.: Издательский дом «Вильямс», 2015. – 624 с.
12. Шилдт Г. Полный справочник по C++. – М.: Издательство Вильямс, 2014. – 795 с.
СОДЕРЖАНИЕ
Практическое занятие 1. Работа с последовательными контейнерами вектор и двусторонняя очередь. 3
Практическое занятие 2. Работа со списками в STL. 33
Практическое занятие 3. Ассоциативные контейнеры: множество и мультимножество. 71
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.. 96
