Весна. Лекция 2. Контейнеры

1. ООП Весна. Лекция 2 Контейнеры. std::set и std::multiset, std::map, std:: multimap и std::unordered_map [email protected]

1

2. class Person{ private: //Закрытые данные char* name; int age; public: //Открытые функции void SetName (char* n) (name=n;} //

inline – встраивание функций
class Person{
private: //Закрытые данные
char* name; int age;
public: //Открытые функции
void SetName (char* n) (name=n;} // Инициализация имени
void SetAge(int a){age=a;}
// Инициализация возраста
char* GetName()(return name;}
int GetAge () (return age;}
};
// Чтение имени
// Чтение возраста
Если функции-члены класса описываются непосредственно в теле
класса, в месте их объявления, тогда они становятся встроенными (inline).
Такой способ удобен для коротких функций.
2

3. Если же текст функции занимает много места, нагляднее вынести его за пределы описания класса. В этом случае в теле класса

inline
Если же текст функции занимает много места, нагляднее вынести его за
пределы описания класса. В этом случае в теле класса должен быть
обязательно объявлен прототип функции. Соответствующие строки для
нашего класса (с единственным членом-данных name будут выглядеть
следующим образом:
class Person {
int age; // Закрытый по умолчанию член-данных
public:
void SetAge ( int a) { age=a;} // inline - встроенная функция
int GetAge() ; // объявление невстроенной функции };
};
int Men:: GetAge (){
// Определение объявленной ранее функции-члена
return age;
}
3

4. Если в описании класса указан только прототип функции, а сама функция определена за пределами описания класса, то необходимо

указать, к какому классу она относится.
Имя класса в этом случае помещается перед именем функции,
отделяясь от него квалификатором разрешения области видимости "::".
Обратите внимание на то, что класс, к которому относится функция,
указывается непосредственно перед именем функции, после описания
типа возвращаемого функцией данного.
Функции, описанные вне описания класса (в который в этом случае
помещается лишь прототип функции: ( GetName () в примере),
компилируются обычным для подпрограмм образом: тело функции
включается в состав загрузочного модуля один раз, а все вызовы этой
функции в программе преобразуются в команду процессора call.
Если функция требует аргументов, то перед выполнением оператора
call значения аргументов загружаются в стек, откуда они будут извлечены
в процессе выполнения функции-подпрограммы.
4

5. Функции, описанные внутри описания класса, носят специальное наименование встроенных (inline). Такие функции обрабатываются

компилятором иначе: во всех местах
программы, содержащих вызов inline-функции, компилятор просто
вставляет тело функции.
Операторы call в этом случае отсутствуют, так же как и строки
загрузки аргументов в стек, что благотворно сказывается на
быстродействии программы.
С другой стороны, тело функции встраивается в загрузочный модуль
при каждом ее вызове, что может привести к чрезмерному увеличению
размеров программы, если функция вызывается многократно и имеет
заметный размер.
Очевидно, что в качестве встроенных целесообразно использовать
только короткие функции.
5

6. С. Мейерс. Правило 29. (“Эффективное использование с++”) Избегайте возврата дескрипторов («описателей») внутренних данных.

Константы
С. Мейерс. Правило 29. (“Эффективное использование с++”)
Избегайте возврата дескрипторов («описателей») внутренних данных.
Предположим, есть В - константный объект String:
class String {
public:
String (const char * value) ;
operator char *() const;
// Преобразование String в char*.
private:
char *data;
};
const String В ("Hello World") ;
Поскольку В объявлен как const, было бы лучше всего, если бы значение
В отныне и навсегда оставалось равным "Hello World". Конечно, при этом
предполагается, что программисты, работающие с В, будут вести честную
6
игру.

7. В частности, многое зависит от того, станут ли они посредством грязных приемов обходить константность: // Делаем alsoB другим

именем для В, но без константности.
String& alsoB = const_cast <String&> (В) ;
Если, впрочем, никто не совершает таких злодеяний, то вполне можно
поручиться, что В никогда не изменится.
Или все-таки нет? Рассмотрим следующую последовательность событий:
char *str = В; // Вызов В.operator char*() .
strcpy ( str, "Hi Mom") ; // Модифицируем то, на что указывает str.
Действительно ли значение В по-прежнему равно "Hello World", или оно
неожиданно превратилось в "Hi Mom"? Ответ полностью зависит от
реализации String::operator char*().
Ниже приведена небрежная реализация, которая ведет себя неправильно.
Тем не менее она работает очень эффективно, поэтому многие программисты
попадаются в эту ловушку
// Быстрая, но некорректная реализация.
String::operator char*() const {
7
return data;
}

8. Проблема с. этой функцией заключается в том, что она возвращает дескриптор (в данном случае указатель) для информации,

содержащейся
внутри объекта String, для которого функция вызывается.
Дескриптор дает пользователю неограниченный доступ к тому, на что
указывает закрытый член data. Другими словами, после строчки
char *str = В; // ситуация выглядит следующим образом:
8

9. Ясно, что любая модификация памяти, на которую указывает str, изменит также и фактическое значение В. Таким образом, несмотря

на
то, что В объявлен как const и вызываются только константные
функции-члены В, по ходу выполнения программы он все равно может
принять другое значение.
В частности, если изменится значение, на которое указывает str, то
В также подвергнется изменению.
В том, как написана функция String::operator char*(), нет ничего
плохого. Плохо то, что она может быть использована для константных
объектов.
Если бы функция не была объявлена как const, то проблемы бы не
возникло, поскольку функцию было бы невозможно вызвать для
объектов, подобных В.
9

10. Тем не менее преобразование объекта String (даже константного) в эквивалентный указатель char* кажется вполне разумным, так что

вы
предпочтете оставить объявление этой функции const. Если вам это
необходимо, следует переписать реализацию так, чтобы избежать возврата
дескриптора внутренних данных:
// Более медленная, но и более безопасная реализация.
String::operator char*() const
{
char *copy = new char [ strlen(data) + 1] ;
strcpy(copy, data); return copy;
}
Приведенная в качестве примера реализация безопасна, поскольку она
возвращает указатель на память, содержащую копию данных, на которые
указывает указатель объекта String. Изменение значения объекта String
посредством возвращаемого этой функцией указателя невозможно. За
безопасность, как всегда, приходится платить: данная версия String: :operator
char* медленнее, чем простая версия, приведенная выше.
При вызове этой функции нужно использовать delete для возвращаемого
10
указателя.

11. Если вы считаете, что такая версия operator char*() чересчур медленна, или вас нервирует (по понятным причинам) потенциальная

возможность
утечки памяти, то представляется целесообразным использовать другое
исправление - возвращать указатель на const char:
class String {
public:
operator const char *() const;
};
inline String::operator const char*() const
{ return data; }
Эта функция быстра и безопасна, и, хотя ее спецификация отличается от
изначальной, для большинства приложений она вполне подойдет.
11

12. Указатель - это не единственный способ возврата дескриптора внутренних Данных. Ссылки предоставляют столь же широкое поле для

злоупотреблений.
Вот наиболее распространенный способ действий, опять
подразумевающий использование класса String:
class String {
public:
char& operator [ ] (int index) const { return data(index); }
private:
char *data;
};
String s = "I'm not constant";
s[0] = 'X';
const String cs = "I'm constant cs[0] = 'x';
// Модифицирует константную строку, //но компилятор этого не замечает.
12

13. Заметьте, что String: : operator [ ] возвращает результат по ссылке. Это означает, что пользователь данной функции получает

другой
идентификатор того же внутреннего элемента data [index], и такой
идентификатор может быть использован для модификации внутренних
данных предположительно константного объекта.
С подобной проблемой мы столкнулись ранее, но на этот раз
проблема - ссылка, а не указатель.
Общее решение подобного рода казусов аналогично решению
проблемы указателей: либо сделать функцию неконстантной, либо
переписать ее так, чтобы она не возвращала дескриптора.
13

14. В ассоциативном контейнере данные располагаются не последовательно, доступ к ним осуществляется посредством ключей. Ключи это

std::set
В ассоциативном контейнере данные располагаются не последовательно,
доступ к ним осуществляется посредством ключей.
Ключи это просто номера строк, они обычно используются для
выстраивания хранящихся элементов в определенном порядке и
модифицируются контейнерами автоматически.
Примером может служить обычный орфографический словарь, где слова
сортируются по алфавиту. Вы просто вводите нужное слово ( значение ключа)
, а контейнер конвертирует его в адрес этого элемента в памяти.
14

15. В STL имеется два типа ассоциативных контейнеров: множества (set) и отображения (map). И те и другие контейнеры хранят данные в

виде дерева,
что позволяет осуществлять быструю вставку, удаление и поиск данных.
Множества и отображения являются очень удобными и при этом достаточно
универсальными инструментами, которые могут применяться в очень многих
ситуациях.
std::set<T> хранит набор элементов, содержащих ключи атрибуты,
используемые для упорядочивания данных. Например, множество может
хранить объекты класса person, которые упорядочиваются в алфавитном
порядке. В качестве ключа при этом используется значение name. При такой
организации данных можно очень быстро найти нужный объект, осуществляя
поиск по имени объекта ( ищем объект класса person по атрибуту name) . Если
в множестве хранятся значения одного из встроенных типов, таких, как int,
ключом является сам элемент.
15

16.

template < class T,
// set::key_type / value_type
class Compare = less<T>, // set::key_compare / value_compare
class Alloc = allocator<T>
// set::allocator_type
> class set;
Наборы (множества) - это контейнеры, которые хранят уникальные
элементы в определяемом порядке.
В наборе значение элемента также идентифицирует его (значение
само по себе является ключом типа T), и каждое значение должно быть
уникальным. Значение элементов в наборе нельзя изменить один раз в
контейнере (элементы всегда const), но они могут быть вставлены или
удалены из контейнера.
Внутренне элементы в наборе всегда сортируются по конкретному
строгому критерию порядка, указанному его внутренним объектом
сравнения (типа Compare).
Контейнер set можно интерпретировать как ассоциативный массив,
в котором значения не важны, или как ассоциативный массив без
значений.
16

17. Чем полезны контейнеры set?

Оказывается, существует много проблем, при решении которых
следует помнить, видели ли мы уже какое-то значение или нет. Один из
примеров — перечисление имеющихся продуктов (независимо от цены);
второй пример — составление словарей.
Иной способ использования этого контейнера — множество "записей",
элементы которого являются объектами, потенциально содержащими
много информации, в которых роль ключа играет один из их членов.
17

18. template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc =

template < class T,
class Compare = less<T>,
class Alloc = allocator<T>
> class set;
// set::key_type/value_type
// set::key_compare/value_compare
// set::allocator_type
key_type
The first template parameter (T)
value_type The first template parameter (T)
key_compare
The second template parameter (Compare) : less<key_type>
value_compare The second template parameter (Compare) : less<value_type>
По умолчанию для сортировки используется алгоритм «меньше»: less<T>.
18

19. set::begin()

#include <iostream>
#include <set>
int main ()
{
int myints [ ] = {75,23,65,42,13};
std::set<int> myset (myints,myints+5);
std::cout << "myset contains:";
for (std::set<int>::iterator it=myset.begin(); it!=myset.end();++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
myset contains: 13 23 42 65 75
19

20. find()

#include <iostream>
#include <set>
int main (){
std::set<int> myset;
std::set<int>::iterator it;
for (int i=1; i<=5; i++) myset.insert(i*10);
// set: 10 20 30 40 50
it=myset.find(20);
myset.erase (it);
myset.erase (myset.find(40));
std::cout << "myset contains:";
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
myset contains: 10 30 50
20

21. set::operator=

int main ()
{
int myints [ ]={ 12,82,37,64,15 };
std::set<int> first (myints,myints+5);
std::set<int> second;
second = first;
first = std::set<int>();
std::cout << "Size of first: " << int (first.size()) << '\n';
std::cout << "Size of second: " << int (second.size()) << '\n';
return 0;
}
Output:
Size of first: 0
Size of second: 5
21

22. set::upper_bound и set::lower_bound

#include <iostream>
#include <set>
int main (){
std::set<int> myset;
std::set<int>::iterator itlow, itup;
for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
itlow=myset.lower_bound (30);
itup=myset.upper_bound (60);
myset.erase(itlow,itup);
// 10 20 70 80 90
std::cout << "myset contains:";
for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
myset contains: 10 20 70 80 90
22

23. set::emplace_hint()

template <class... Args>
iterator emplace_hint (const_iterator position, Args&&... args);
Вставляет новый элемент в набор, если он уникален, с подсказкой о
позиции вставки.
Вставка выполняется только в том случае, если ни один другой
элемент в контейнере не эквивалентен помещаемому (элементы в
контейнере набора уникальны).
При вставке это эффективно увеличивает размер контейнера на
единицу.
Значение позиции используется в качестве подсказки для точки
вставки. Тем не менее элемент будет вставлен в соответствующее
положение в порядке, описанном его внутренним объектом сравнения, но
эта подсказка используется функцией для начала поиска точки вставки,
что значительно ускоряет процесс, когда фактическая точка вставки
находится либо в нужном положении, либо близко к ней.
23

24. Пример

#include <iostream>
#include <set>
#include <string>
int main (){
std::set<std::string> myset;
auto it = myset.cbegin();
myset.emplace_hint (it,"alpha");
it = myset.emplace_hint (myset.cend(),"omega");
it = myset.emplace_hint (it,"epsilon");
it = myset.emplace_hint (it,"beta");
std::cout << "myset contains:";
for (const std::string& x : myset)
std::cout << ' ' << x;
std::cout << '\n';
Output:
return 0;
alpha beta epsilon omega
}
24

25. set::insert() и set::erase()

single element (1)
pair<iterator,bool> insert (const value_type& val);
with hint (2)
iterator insert (iterator position, const value_type& val);
range (3)
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
(1)
void erase (iterator position);
(2)
size_type erase (const value_type& val);
(3)
void erase (iterator first, iterator last);
25

26. #include <iostream> #include <set> int main (){ std::set<int> myset; std::set<int>::iterator it; // insert some values: for

#include <iostream>
#include <set>
int main (){
std::set<int> myset;
std::set<int>::iterator it;
// insert some values:
for (int i=1; i<10; i++) myset.insert (i*10); // 10 20 30 40 50 60 70 80 90
it = myset.begin();
++it;
// to 20
myset.erase (it);
myset.erase (40);
it = myset.find (60);
myset.erase (it, myset.end());
std::cout << "myset contains:";
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
Output:
return 0;
myset contains: 10 30 50
}
26

27. multiset

Сбалансированное упорядоченное дерево, в котором может храниться
несколько копий ключа.
Страуструп рекомендует использовать, если нужно отслеживать отдельные
значения.
template < class T,
class Compare = less<T>,
class Alloc = allocator<T> >
> class multiset;
// multiset::key_type/value_type
// multiset::key_compare/value_compare
// multiset::allocator_type
27

28. multiset::insert

single element (1)
iterator insert (const value_type& val);
// возвращает итератор,
// а не pair<iterator, bool>
with hint (2)
iterator insert (iterator position, const value_type& val);
range (3)
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
28

29.

#include <iostream>
#include <set>
int main (){
std::multiset<int> mymultiset;
std::multiset<int>::iterator it;
// set some initial values:
for (int i=1; i<=5; i++) mymultiset.insert (i*10); // 10 20 30 40 50
it=mymultiset.insert(25);
it=mymultiset.insert (it,27); // max efficiency inserting
it=mymultiset.insert (it,29); // max efficiency inserting
it=mymultiset.insert (it,24); // no max efficiency inserting (24<29)
int myints [ ]= {5,10,15};
mymultiset.insert (myints,myints+3);
std::cout << "mymultiset contains:";
for ( it=mymultiset.begin(); it!=mymultiset.end(); ++it )
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output: myset contains: 5 10 10 15 20 24 25 27 29 30 40 50
29

30. Кортеж (std::tuple) и пара (std::pair)

Этот класс объединяет вместе пару значений, которые могут быть разных
типов ( T1и T2). Отдельные значения могут быть доступны через его открытые
члены first и second
Пары - это частный случай std::tuple.( кортеж - упорядоченный набор
фиксированной длины)
std::tie конструирует и возвращает кортеж ссылок
30

31.

Пример
#include <iostream>
#include <tuple>
int main () {
std::tuple<int,char> first;
// default
std::tuple<int,char> second (first);
// copy
std::tuple<int,char> third (std::make_tuple(20,'b')); // move
std::tuple<long,char> fourth (third);
// неявная conversion
std::tuple<int,char> fifth (10,'a');
// initialization
std::tuple<int,char> sixth (std::make_pair(30,'c')); // from pair / move
std::cout << "sixth contains: " << std::get<0>(sixth);
std::cout << " and " << std::get<1>(sixth) << '\n';
return 0;
}
Output:
sixth contains: 30 and c
31

32. pair::pair

Создает pair – объект «пара».
Он включает в себя индивидуальное построение его двух компонентных
объектов, с инициализацией, которая зависит от вызываемой формы
конструктора:
(1) default constructor
pair();
(2) copy / move constructor (и неявное преобразование)
template<class U, class V> pair (const pair<U,V>& pr);
Объект инициализируется с помощью содержимого pr pair объекта.
Соответствующий член pr передается конструктору каждого из его членов.
(3) initialization constructor
pair (const first_type& a, const second_type& b);
Элемент first строится с помощью а и элемент second с b
(4) piecewise constructor // кусочный конструктор
pair (piecewise_construct_t pwc, tuple<Args1...> first_args,
tuple<Args2...> second_args);
Конструирует члены first и second на месте, передавая элементы из
32
first_args в качестве аргументов конструктору first, а элементы из second_args
в конструктор second.

33.

Пример
#include <utility>
// std::pair, std::make_pair
#include <string>
// std::string
#include <iostream> // std::cout
int main () {
std::pair <std::string,double> product1;
// default constructor
std::pair <std::string,double> product2 ("tomatoes",2.30); // value init
std::pair <std::string,double> product3 (product2);
// copy constructor
product1 = std::make_pair (std::string("lightbulbs"),0.99); // using make_pair
product2.first = "shoes";
// the type of first is string
product2.second = 39.90;
// the type of second is double
std::cout << "The price of " << product1.first << " is $" << product1.second << '\n';
std::cout << "The price of " << product2.first << " is $" << product2.second << '\n';
std::cout << "The price of " << product3.first << " is $" << product3.second << '\n';
return 0;
}
Output:
The price of lightbulbs is $0.99
33
The price of shoes is $39.9
The price of tomatoes is $2.3

34. std::make_pair

template <class T1, class T2>
pair<V1,V2> make_pair (T1&& x, T2&& y);
Создает pair объект с его первым элементом, установленным в x, и его
вторым элементом, установленным в у.
Типы шаблонов могут быть неявно выведены из переданных аргументов
make_pair.
pair объекты могут быть построены из других pair объектов, содержащих
различные типы, если соответствующие типы неявно преобразуются.
34

35.

Пример
#include <utility>
#include <iostream>
int main () {
std::pair <int, int> foo;
std::pair <int, int> bar;
foo = std::make_pair (10,20);
bar = std::make_pair (10.5,'A'); // неявное преобразование из пары <double, char>
std::cout << "foo: " << foo.first << ", " << foo.second << '\n';
std::cout << "bar: " << bar.first << ", " << bar.second << '\n';
return 0;
}
Output:
foo: 10, 20
bar: 10, 65
35

36. std::get (pair)

template <size_t I, class T1, class T2>
typename tuple_element< I, pair<T1,T2> >::type& get (pair<T1,T2>& pr)
Возвращает ссылку на элемент first, если I равен 0, или ссылку на элемент
second, если I равен 1.
#include <utility>
#include <iostream>
int main () {
std::pair <int,char> foo (10,'x');
std::get<0>(foo) = 50;
std::cout << "foo contains: ";
std::cout << std::get <0>(foo) << " and " << std::get <1>(foo) << '\n';
return 0;
}
Output:
foo contains: 50 and x
36

37. map

После класса vector вторым по частоте использования является
стандартный контейнер map, представляющий собой упорядоченную
последовательность пар (ключ, значение) и позволяющий находить значение
по ключу; например, элемент my_phonebook [ " Николай" ] может быть
телефонным номером Николая.
Единственным достойным конкурентом класса map по популярности
является класс unordered_map, оптимизированный для ключей,
представляющих собой строки.
Структуры данных, аналогичные контейнерам map и unordered_map,
известны под разными названиями, например ассоциативные массивы
(associative arrays), хеш-таблицы (hash tables) и красно-черные деревья (redblack trees).
template < class Key,
// map::key_type
class T,
// map::mapped_type
class Compare = less<Key>,
// map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;
37

38. map::insert

single element (1)
pair<iterator, bool> insert (const value_type& val);
with hint (2)
iterator insert (iterator position, const value_type& val);
диапазон (3)
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
38

39.

Пример
#include <iostream>
#include <map>
int main (){
std::map<char, int> mymap;
// first insert function version (single parameter):
mymap.insert ( std::pair<char,int>('a',100) );
mymap.insert ( std::pair<char,int>('z',200) );
std::pair< std::map<char,int>::iterator, bool > ret;
ret = mymap.insert ( std::pair<char,int>( 'z', 500) );
if (ret.second == false) {
std::cout << "element 'z' already existed";
std::cout << " with a value of " << ret.first->second << '\n';
}
// second insert function version (with hint position):
std::map<char,int>::iterator it = mymap.begin();
mymap. insert (it, std::pair<char,int>('b',300)); // max efficiency inserting
mymap. insert (it, std::pair<char,int>('c',400)); // no max efficiency inserting
39

40.

// third insert function version (range insertion):
std::map<char,int> anothermap;
anothermap. insert (mymap.begin(),mymap.find('c'));
// вывод результатов:
std::cout << "mymap contains:\n";
for (it=mymap.begin(); it!=mymap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
std::cout << "anothermap contains:\n";
for (it=anothermap.begin(); it!=anothermap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
return 0;
} // конец программы
Output: element 'z' already existed with a value of 200
mymap contains:
a => 100
b => 300
c => 400
z => 200
anothermap contains:
40
a => 100
b => 300

41. Еще пример: map::insert

#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef map<int, string,less<int> > INTSTR;
void main(){
INTSTR theMap; // 1. Create a map of ints to strings
INTSTR ::iterator theIterator;
string theString = "";
int index;
// Fill it with the digits 0 - 9, each mapped to its // string counter part
// Note: value_type is a pair for maps...
theMap.insert( pair<int, string >(0,"Zero"));
theMap.insert( INTSTR::value_type(1,"One"));
theMap.insert( INTSTR::value_type(2,"Two"));
theMap.insert( INTSTR::value_type(3,"Three"));
theMap.insert( INTSTR::value_type(4,"Four"));
41

42. theMap.insert(INTSTR::value_type(5,"Five")); theMap.insert(INTSTR::value_type(6,"Six"));

theMap.insert(INTSTR::value_type(5,"Five"));
theMap.insert(INTSTR::value_type(6,"Six"));
theMap.insert(INTSTR::value_type(7,"Seven"));
theMap.insert(INTSTR::value_type(8,"Eight"));
theMap.insert(INTSTR::value_type(9,"Nine"));
// Read a Number from the user and print it back as words
for( ; ; ) {
cout << "Enter \"q\" to quit, or enter a Number: ";
cin >> theString;
if( theString == "q")
break;
// extract each digit from the string, find its corresponding
// entry in the map (the word equivalent) and print it
for(index = 0; index < theString.length(); index++){
theIterator = theMap.find(theString[index] - '0');
if( theIterator != theMap.end() ) // is 0 - 9
cout << (*theIterator).second << " ";
else // some character other than 0 - 9
cout << "[err] ";
}
cout << endl;
}
} // конец программы
42

43. Output : Enter "q" to quit, or enter a Number: 22 Two Two Enter "q" to quit, or enter a Number: 33 Three Three Enter "q" to

Output :
Enter "q" to quit, or enter a Number: 22
Two Two
Enter "q" to quit, or enter a Number: 33
Three Three
Enter "q" to quit, or enter a Number: 456
Four Five Six
Enter "q" to quit, or enter a Number: q
43

44. map::operator [ ]

mapped_type& operator [ ] (const key_type& k);
Если k соответствует ключу элемента в контейнере, функция возвращает
ссылку на его отображаемое значение.
Если k не соответствует ключу любого элемента в контейнере, функция
вставляет новый элемент с этим ключом и возвращает ссылку на его
отображаемое значение. Обратите внимание, что это всегда увеличивает
размер контейнера на единицу, даже если для элемента не назначено
сопоставленное значение (элемент создается с использованием его
конструктора по умолчанию).
Аналогичная функция-член map :: at имеет такое же поведение, когда
элемент с ключом существует, но генерирует исключение, если это не так.
Эквивалентный вызов:
(*( ( this->insert( make_pair( k,mapped_type()))).first ) ).second;
44

45.

#include <iostream>
#include <map>
#include <string>
int main (){
std::map<char,std::string> mymap;
mymap['a']="an element";
mymap['b']="another element";
mymap['c']= mymap['b'];
std::cout << "mymap['a'] is " << mymap['a'] << '\n';
std::cout << "mymap['b'] is " << mymap['b'] << '\n';
std::cout << "mymap['c'] is " << mymap['c'] << '\n';
std::cout << "mymap['d'] is " << mymap['d'] << '\n';
std::cout << "mymap now contains " << mymap.size() << " elements.\n";
return 0;
}
Output:
mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is
mymap now contains 4 elements.
45

46. map::count()

size_type count (const key_type& k) const;
Подсчет элементов с определенным ключом
Выполняет поиск в контейнере элементов с ключом, эквивалентным k, и
возвращает количество совпадений.
Поскольку все элементы в контейнере карт уникальны, функция может
возвращать только 1 (если элемент найден) или ноль (в противном случае).
Два ключа считаются эквивалентными, если объект сравнения
контейнера возвращает false рефлексивно (т. е. независимо от порядка, в
котором ключи передаются в качестве аргументов).
46

47.

#include <iostream>
#include <map>
int main () {
std::map<char,int> mymap;
char c;
mymap ['a']=101;
mymap ['c']=202;
mymap ['f']=303;
for (c='a'; c<'h'; c++) {
std::cout << c;
if (mymap.count(c)>0)
std::cout << " is an element of mymap.\n";
else
std::cout << " is not an element of mymap.\n";
}
return 0;
}
Output:
a is an element of mymap.
b is not an element of mymap.
c is an element of mymap.
d is not an element of mymap.
e is not an element of mymap.
f is an element of mymap.
g is not an element of mymap.
47

48. map::operator=

map& operator= (const map& x); // копирование
map& operator= (map&& x); // перемещение
map& operator= (initializer_list<value_type> il); // список инициализации
48

49.

#include <iostream>
#include <map>
int main () {
std::map<char,int> first;
std::map<char,int> second;
first['x']=8;
first['y']=16;
first['z']=32;
second=first;
// в second теперь есть 3 int-а
first=std::map<char,int>(); // first - аннулируется
std::cout << "Size of first: " << first.size() << '\n';
std::cout << "Size of second: " << second.size() << '\n';
return 0;
}
Output:
Size of first: 0
Size of second: 3
49

50. map с предикатами

Некоторые конструкторы map:
empty (1)
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
range (2)
template <class InputIterator>
map (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
copy (3)
map (const map& x);
50

51. Пример

#include <iostream>
#include <map>
bool fncomp (char lhs, char rhs) {return lhs<rhs;} // предикат-функция
struct classcomp {
// предикат-функтор
bool operator() (const char& lhs, const char& rhs) const
{return lhs<rhs;}
};
int main () {
std::map<char,int> first;
first['a']=10;
first['b']=30;
first['c']=50;
first['d']=70;
std::map<char,int> second (first.begin(),first.end());
std::map<char,int> third (second);
std::map<char,int,classcomp> fourth;
// class as Compare
bool(*fn_pt)(char,char) = fncomp;
std::map<char,int,bool(*)(char,char)> fifth (fn_pt); // function pointer as Compare
return 0;
}
51

52. Чистая функция

Чистой функцией называется функция, возвращаемое значение которой
зависит только от параметров.
Если f чистая функция, а х и у объекты, то возвращаемое значение f(x,y)
может измениться только в случае изменения х или у.
В С++ все данные, используемые чистыми функциями, либо передаются в
виде параметров, либо остаются постоянными на протяжении всего
жизненного цикла функции (естественно, такие постоянные данные
объявляются с ключевым словом const).
Если бы данные, используемые чистой функцией, могли изменяться между
вызовами, то вызов этой функции в разные моменты времени с одинаковыми
параметрами мог бы давать разные результаты, что противоречит
определению чистой функции.
52

53. std::multimap

multimap являются ассоциативными контейнерами, которые хранят
элементы, сформированные комбинацией значения ключа и отображаемого
значения, следуя определенному порядку и где несколько элементов могут
иметь эквивалентные ключи.
В multimap значения ключа обычно используются для сортировки и
уникальной идентификации элементов, тогда как отображаемые значения
сохраняют содержимое, связанное с этим ключом. Типы ключей и
отображаемых значений могут отличаться и сгруппированы в тип элемента
value_type, который представляет собой тип пары, объединяющий оба:
typedef pair <const Key, T> value_type;
Внутри элементы в multimap всегда сортируются по его ключу, следуя
конкретному строгому критерию упорядоченности, заданным его предикатом
(типа Compare).
multimap обычно реализуются как двоичные деревья поиска.
53

54. Отличие от map

Вставка только через:
multimap::insert
multimap::emplace
multimap::emplace_hint
Отсутствует
operator [ ]
54

55. std::unordered_map

unordered_map - это ассоциативные контейнеры , в которых хранятся
элементы, образованные комбинацией ключевого значения и отображенного
значения, и которые позволяют быстро извлекать отдельные элементы на
основе их ключей.
В unordered_map значение ключа обычно используется для уникальной
идентификации элемента, в то время как сопоставленное значение
представляет собой объект с содержимым, связанным с этим ключом.
Внутренне элементы в unordered_map не сортируются в каком-либо
определенном порядке по отношению к их ключу или отображенным
значениям, а организуются в корзины в зависимости от их хэш-значений,
чтобы обеспечить быстрый доступ к отдельным элементам непосредственно
по их ключевым значениям (с постоянной средней временной сложностью в
среднем).
Контейнеры unordered_map быстрее , чем контейнеры map, получают
доступ к отдельным элементам по их ключу, хотя обычно они менее
эффективны для итерации.
Неупорядоченные карты реализуют оператор прямого доступа (operator [ ]),
который позволяет осуществлять прямой доступ к отображаемому значению,
55
используя его ключевое значение в качестве аргумента.

56. ДЗ в1

Создать полиморфную иерархию из двух классов: базовый и производный
именованными, как в прежних проектах. Каждый класс должен быть описан в
своих файлах с++/h.
В базовом классе определить член-данных х, типа int* и пользовательский
конструктор, в котором указывать число для помещения в х. В производном:
член-данных y типа int , и также заполнить при создании объекта любым
числом.
В отдельных файлах создать класс базы данных DB db1, поместив в его
приватной области объект set <Base*, predicate>. В качестве 1-го аргумента
шаблона задать указатель на базовый класс, а во втором аргументе шаблона
указать функтор сортировки данных в set. Сортировка должна быть
произведена по значению в х.
Создать еще две базы данных db2 и db3 . В db2 скопировать половину
объектов из db1, у которых *х наименьший, причем только базового класса, а в
db3 половину, имеющих наибольший *х, только производного .
Удалить db1.
Вывести на консоль с помощью члена-функции print значения х и y из
db3 .
56

57. Контрольная работа 1

Пусть есть класс Storage, а внутри
vector < You_Base_Name*> _db;
Всего в полиморфной иерархии имеется два класса. Внутри них все,
что нужно – есть.
Реализовать для Storage только конструктор копирования и
оператор присваивания копированием.
57