Здравствуйте, сегодня мы продолжим говорить о том, как использовать ассоциативные контейнеры эффективно. И для того, чтобы посмотреть на эту эффективность, мы обратимся к задаче. Какую задачу мы будем сегодня решать? Заведем set строк и положим в него для начала три каких нибудь строчки: a, b и c. Распечатаем что в них находится, чтобы убедиться в том, что мы сделали все правильно. Да, действительно, мы видим, что в set лежат строчки a, b, c, отсортированные по алфавиту, и если мы представим себе в уме дерево, которое может их хранить, то получится примерно такая картинка. Что мы хотим сделать дальше? Мы хотим это дерево модифицировать, мы хотим, чтобы все строчки, которые хранятся в нём, начинались с маленькой буквы, а не с большой. Давайте начнём, ну скажем, с первого элемента. Установим итератор на begin, он указывает на какую-то строчку, и попробуем эту строчку изменить. Но компилятор нам говорит сообщение об ошибке, он говорит о том, что мы потеряли где-то константность. Что бы это могло значить? По-простому это говорит о том, что мы не можем изменить ключ объекта, который находится в дереве, и легко понять почему, если мы посмотрим на картинку. Вот у нас итератор указывает на begin, и мы хотим изменить это значение, то есть мы хотим изменить значение объекта, который лежит в дереве, но мы знаем, что мы не можем это просто взять и сделать, потому что элементы у нас в дереве упорядоченные, и если мы захотим поменять ключ, то нам придется поместить этот объект в другое место в дереве, а работая с итератором, мы не можем этого сделать, потому что итератор указывает на один элемент и про структуру всего дерева ничего не знает. Поэтому какие есть способы такую задачу решить? Мы можем взять эту строчку и скопировать из дерева, то есть взять копию, а не ссылку, теперь уже изменить, дальше из дерева старое значение - удалить, и новое значение измененное - вставить. Так у нас задача решится, решение компилируется, и распечатаем снова дерево, чтобы убедиться, что произошло ожидаемое. Да, мы видим, что у нас строчка, которая раньше начиналась на A, сейчас начинается на a маленькое, то есть мы добились чего хотели и, казалось бы, задача решена, она очень простая, и в чём же тут подвох? А подвох в следующем: давайте посмотрим на слайд и разберёмся, какие же этапы решения у нас были. У нас было дерево сначала из а, b и c, потом мы скопировали строку, потом мы удалили старый объект из дерева, поработали с копией в памяти, скопировали это значение обратно в дерево, и это копия у нас, получилось, была лишней почти всё время, мы зря сделали два копирования, из дерева и в дерево, только для того, чтобы снаружи дерева модифицировать строчку. И казалось бы, так придется делать всегда, ведь у нас ключи в дереве не заменяемые, это единственный способ. Но нужно понимать, что даже такой единственный способ вам не подойдёт, если у вас объекты очень тяжёлые, и вы не хотите тратить на них копирование, либо эти объекты вообще нельзя скопировать, потому что они move only, потому что их можно только перемещать, а копировать нельзя. Давайте рассмотрим именно такой пример для иллюстрации. Возьмём строчки, которые нельзя скопировать, вы их должны помнить с прошлых задач нашего курса. Значит, здесь у нас имеются конструкторы, унаследованные от строки; подчеркнуто, что конструктор копирования запрещён и подчеркнуто, что конструктор перемещения разрешён. И давайте заведем сейчас дерево из таких вот некопируемых строк. У нас начались проблемы вот здесь. У нас компилятор говорит, что мы не можем вставить в дерево строчку такого типа, даже не такого типа, она ведь у нас будет вот такого типа сейчас, мы не можем даже скопировать наружу, потому что она не копируемая, а только перемещаемая, и мы бы хотели её переместить именно поэтому, но как же перемещать из дерева? Оказывается, такой способ есть, у дерева есть специальный метод, он называется extract и работает так, как нам нужно. Мы можем взять и извлечь из дерева (даже наверное не строчку правильно будет сказать, а) весь узел целиком, то есть мы можем оторвать узел от дерева, и для этого воспользуемся словом auto, потому что он будет иметь специальный тип, а не тип строка. Значит вот у нас есть теперь какой-то node, который мы извлекли из дерева, он внутри себя содержит нужную нам строчку. Но сейчас можем её взять, эту строчку, и вытащить её для того, чтобы модифицировать. Заметьте, что мы вытаскиваем её по ссылке, чтобы не делать лишнее копирование. Вот мы сейчас вытащили эту строчку по ссылке, произвели её модификацию. Мы теперь можем это делать, потому что узел у нас находится не в дереве, а отдельно сам по себе. И затем мы хотим поместить обратно этот узел. Удалять нам уже ничего не нужно, мы же весь узел вытащили уже. Чтобы вставить - нам нужно вставить не строчку, а этот узел целиком. И нам подчеркивает ошибку, да, потому что мы должны вставить не копируя, а перемещая. Нужно не забыть написать здесь move. Собираем. Так у нас программа успешно компилируется, и проверим, что она успешно работает. Она работает отлично, она делает то, что раньше: она модифицирует значение ключа без избыточного копирования. Можем даже посмотреть на слайды, чтобы сравнить как было и как стало. Сейчас на схеме представлено как мы решили эту задачу с использованием extract. У нас было дерево из трёх узлов, затем мы один узел просто оторвали наружу без копирования, это просто перемещение с дерева. В этом отдельно взятом узле мы изменили значение строки и потом вставили этот узел обратно в дерево. Заметьте, что здесь не было никаких копирований, мы просто вытащили узел из дерева и затем вставили его в другое место, чтобы он связался с родителями и сыновьями по другому. Копирований никаких здесь не было. Это интересно, и давайте рассмотрим ещё один интересный пример, как это можно использовать ещё удобнее. Допустим, что у нас есть два дерева, одно дерево строк и другое дерево строк, два set'а. Возьмем второй set, заведем в нём новые объекты, назовем их так. И допустим, мы хотим слить два этих дерева: взять и переместить все узлы из второго дерева в первое. И мы можем это сделать, мы можем вытаскивать каждый узел из дерева 2 и вставлять его в дерево 1. Например, в цикле. Либо вместо этого, чтобы это делать не в цикле, использовать функцию merge, и просто перенести всё дерево, все элементы дерева 2 в дерево 1. Давайте проверим, что это все работает именно так, как я вам рассказал. Вот мы напечатали то, что получилось после вызова. Это у нас 6 элементов. Супер! И чтобы убедиться, что никаких копирований не было, давайте распечатаем содержимое дерева 2. Конечно, никаких копирований здесь быть не могло, у нас же конструктор копирования запрещён, и мы это видим, у нас распечатана пустая строка там, где мы печатали элементы дерева 2. Всё ожидаемо, всё работает отлично. Посмотрим на рисунки, как это выглядело. У нас было два дерева с элементами жёлтого цвета и зелёного. Мы их слили в одно дерево и в этом дереве находятся вперемешку жёлтые и зелёные узлы. Когда мы их сливали, никаких копирований не произошло, мы просто в дереве связали их по другому указателями, чем сэкономили кучу накладных расходов. Это здорово. Итак, что мы с вами рассмотрели сегодня? Мы с вами повторили и убедились, что нельзя напрямую изменять ключ объекта в контейнере set. Для того, чтобы изменить этот ключ, мы вынуждены скопировать ключ во временный объект и заменить его там, удалить из старого места, а потом скопировать временную копию обратно. Если мы хотим избежать промежуточных копирований, мы можем использовать функции extract и, при необходимости перенести все элементы из одного дерева в другое, мы можем использовать метод merge.
