Лекция 30. Реализация итераторов. Адаптеры над итераторами

ruticker 05.03.2025 11:07:45

Текст распознан YouScriptor с канала Мещерин Илья

распознано с видео на ютубе сервисом YouScriptor.com, читайте дальше по ссылке Лекция 30. Реализация итераторов. Адаптеры над итераторами

Продолжаем. Я вам сказал, что вот есть метан, и там есть много чего полезного. Самое полезное — да, вот дава, я передумал, я не хочу реализовывать эту функцию, но она нам ничего не даст. Уже всё, что я хотел, я вам показал. Так, только я экран не расшарил. Я снова расшарю. Что здесь есть? Специализация для... Понятно ли? Зачем на самом деле? На самом деле, вот если внимательно почитать требования к итераторам, если снова открыть и найти там итератор, то вы заметите, что в итераторе... А, нет, я вас обманул. Да ладно, я вас... Я вас, кажется, кажется... Нет, кажется, это не так работает. Ну, ладно, короче, итератор сам в себе зачастую определяет, что такое `val Type`, `typ` и так далее. Вот если вы возьмёте произвольный итератор стандартной библиотеки, там, например, вектор, векторовский итератор, то в нём будет и так определено, что такое `val Type` и тому подобное. Просто, ну, тут в требованиях этого нет, но стандартные итераторы так делают. Но проблема в том, что если у вас `поте`, то вы не можете у него отдельно спросить `value Type`. Дело в том, что как работает `iterator traits value Type`? Оно просто смотрит в `iterator value Type`. Ну, как бы упрощённое `itat Trade value Type` — оно смотрит в `ратора value Type`, и если там оно есть, то просто берёт его, а если его нет, то оно, ну, там берёт то, что получится. Если, но проблема в том, что если тип — это `поте`, на самом деле, то ошибка произойдёт уже в момент, когда вы пытаетесь достать. Есть просто нельзя у него пытаться достать. Короче, для `Потера` вам нужна отдельная специализация, которая не пытается достать из итератора, а просто сама дописывает про него всё. Сама такая, а не просто... Если хотите достать корректный `п`, как `поль`, вот чтобы показать вам использование `C`, я хочу продемонстрировать ещё две полезные функции и на их примере, собственно, показать использование функций. Вот давайте посмотрим на функцию `сча`. Функция `distance` — это функция, которая позволяет вам посчитать разность итератора, то есть количество шагов, количество прыжков, которое нужно, чтобы дойти от `до`. Вот и как она работает? Если Иран вот этих двух итераторов... А ещё можете написать, у вас появится функция `distance`, которая будет делать не то, что вы ожидали, скорее всего. Вот давайте реализуем функцию `distance ty`, значит, какой воз... Спиру, ладно, вот такой возвращаемый тип. И вместо этого просто напишем `ирар итератор итератор`. Вот и мы хотим количеством итератор поддерживает операцию `плюс равно`, то просто, точнее, ну, если он поддерживает вычитание, то просто вычесть и вернуть это, а иначе, значит, честно завести цикл, посчитать количество шагов, которое нам потребовалось, чтобы дойти. Как же это сделать? Да, вот правильно, да и правильно. Да, надо написать `и Кок`. Мы хотим с вами написать, ну, давайте вспомним, мы уже однажды с этим сталкивались. Мы хотим написать что-то в стиле: если у него есть операция вычитания, то значит вернуть `Last - First`, и тут проверить какое-то условие. Но если мы напишем `бекон`, то это всё равно выдаст `CE`, когда мы подставим не `Random exat`, потому что эта строчка будет пытаться компилировать так. Поэтому нам нужно и Ко, начиная `C+ 17`, оно появилось. А что? Ну, можно написать так, можно написать, что категория итератора равна `std`. Да, это не совсем правда, но давайте сначала хотя бы это напишем. Ну, я могу или поставить, или... Да, это не очень правильно, но давайте хотя бы напишем. Для начала просто проверку, что она равна. Что надо написать? Надо сравнить, надо сравнить типы. Да, `std от каких параметров`, `std от`... Есть что-то типа наслед... Вообще, подожди, просто вот сначала мы, значит, так как подставить вот так, наверное, так. И значит, вот это... И чего? `std Random Access итератор` — это просто пустая структура. Всё, вот и `conex` равны вот эти два типа, то сделать `Last - First`. Иначе просто поехали `for бла-бла-бла`... ДУ от одного до пяти, короче, ну там `for А`, ну надо строго говоря завести вот этот вот тип. Короче, мне пофиг, я просто скажу, `иты` равно нулю и меньше. Да, я могу просто инкрементировать `First`, пока `First` не равно `Last`. Я же их копии принял, поэтому я ничего не испорчу. `First` не равно `Last` плюс-плюс. И да, и всё, что... А, плюс-плюсы, плюс-плюсы `First`, да. Ну и всё. А теперь `Return` и... Господи, ну просто, ладно, ну короче, понятно, что надо сделать. А, да, я написал говнокод. Ладно, для целей быстрого прототипа. Вот, но здесь, конечно, надо не написать, а проверка того, что один является наследником другого, то есть что является наследником. Значит, да, есть такой база, значит, `std is Base of V`, точно так же, как и `Same` с знак подчёркивания в на конце, и мы проверяем. Вот это значит, если это... Если это база, то тогда возвращаем `Last`. Ну как нормально, вот таким образом у вас, например, `дистанс` от двух итераторов в `пе` будет работать линейное время, а `дистанс` от двух итераторов в `векторе` будет работать константное время. Я вам уже неоднократно сказал, что и появился, начиная `c+ 1`. Внимание вопрос: а как же до этого жили люди? Как первобытные люди реализовывали дистанцию? Делали это люди во времена, когда я был студентом? Нет, на самом деле это упражнение такое. Не знаю, мне кажется, может быть, нахор какой-нибудь такое упражнение не очень сложное можно придумать. Как выразить без него, то есть средствами даже не `11`, а вообще более раннего классического выражается. Можно всё, что вы делаете, через чно знаний, чтобы это придумать. Кто-нибудь может быть догадается, что надо сделать, чтобы вместо... Чтобы их ко выразить через более старые средства. На самом деле, это не новая возможность, это просто тоже синтаксический сахар. Кани, есть идея, как выразить в `+`. Ну да, надо просто сделать перегрузку функций. Надо просто сделать... Ну, надо сделать функцию `distance Helper`, которая третьим параметром принимает вот этот вот тег, и в зависимости... Ну и передать ей третьим параметром `итератор category`, сконструированный по умолчанию, и она тогда в зависимости от того, какая это версия, попадёт либо в одну функцию, либо в другую. В одной функции она просто вернёт разность, в другой функции она вернёт... Ну, цикл. Вот, поняли как? Это, если что, упражнение. Это может быть, я вам в контрольную вставлю. Это упражнение, вот, ну это такое упражнение на понимание шаблонов. Что? Ну хорошо, функция `Advance` аналогично действует. Ну, `Advance` — это штука, которая продвигает. Она берёт, значит, продвигает итератор на шагов, причём может быть и отрицатель. Вот если, кстати, у вас `Дин`, если вы передали в `ди итераторы` такие, что от недостижим инкремента, то у вас, кстати, две очень полезных функции. Давайте про них тоже скажу, а то про них люди... `ТТ Next` — это функции, которые просто дают вам итератор на следующий элемент данного итератора, на предыдущий элемент от данного. Вот выглядит банально, но они очень упрощают код в некоторых случаях. То есть вам надо, типа, например, цикл не до конца, а до предыдущего перед концом элемента дойти, и вы там, если не э функция, будете лепить про дрянь какую-то, сделать копию ратора преф от... Значит, от `Н`, и, пожалуйста, вот у вас цикл не до конца, а до предыдущего перед концом. Хорошо, ну вот напоследок, наверное, я заканчиваю разговор про вид итераторов, скажу вот что. Сейчас будет немного философии снова. Короче, я хочу сказать, что виды итераторов — это, в общем-то, довольно такая глубокая идея, такая достаточно абстрактная, не только к плюсам применимая, а вообще вот если задуматься, виды итераторов — это вообще про то, насколько хорошая, насколько качественно у вас запомнена информация. Вот так вот я бы сказал, потому что вот когда вы говорите: "А я помню, не знаю, что вот вы помните курс Матана". Вот, например, вы помните ли вы материал этого семестра по плюсам? Ну, помнить можно по-разному. Вот можно помнить так, что я вам задаю вопрос: "Вот что будет?" И вы говорите: "Ну вот это будет", и вы всегда отвечаете на вопросы правильно. Это одно дело. А другое дело, когда вы не просто помните, а можете ещё и перечислить всё, что я вам рассказывал в порядке, в котором я вам это рассказывал. Это следующий уровень, это у вас уже итератор есть. То есть одно дело вы просто помните какую-то информацию, другое дело вы помните её с порядком, а третье дело вы помните её ещё в обратную сторону, а четвёртое дело вы помните её ещё и... Вот смотрите, вот я люблю приводить такие примеры, чтобы вы осознали, что на самом деле наличие итераторов — это большое, очень такое требование. Что вот мы сейчас с вами будем снова говорить про то, как контейнеры реализованы, и я вот хочу сказать, что наличие итераторов — это на самом деле достаточно существенное требование. Это достаточно, ну, такое большое усложнение. Без итераторов контейнеры, например, или просто можно было бы реализовать гораздо проще. Итераторов в каждом контейнере — это требование, которое усложняет реализацию сильно, потому что это существенно больше помнить всё с итераторами, с умением проходить. Это существенно более сложно, чем просто помнить. Вот, например, я люблю приводить такие примеры. Вот у вас есть список друзей в ВК, например, или там, сейчас ВК люди не особо пользуются, там не знаю, список чатов в Телеграме. Вот вы можете про произвольного человека сказать: "Есть у вас в друзьях или нет?" Скорее всего, но вы вряд ли можете перечислить все их хоть в каком-то порядке, гарантированно не забыв никого. Помнить, что просто помнить какое-то множество вещей — это гораздо меньше, чем помнить итератор. С другой стороны, вот вы, наверное, помните стихотворение "У Лукоморья дуб зелёный". Но если я вас спрошу: "Какая строчка идёт перед строчкой '30 витязей прекрасных'?", вам придётся линейное время потратить, чтобы вспомнить, не так ли? Потому что вы помните только в одну сторону стихии. Когда вы учите стихи, вы помните их в одну сторону. Вы не просто помните все строчки по отдельности, вы помните их, умея переходить к следующей, но вы не умеете переходить к предыдущей, почти наверняка. И это уметь переходить к предыдущей — это нечто большее. Вот дальше наме... Вот вы можете помнить останов полезной дороги по серой ветке метро, там вот что после Тульской, там Нагатинская, в обратную сторону Серпуховская. Вот, но вы вряд ли скажете за единицы, что через 10 остановок после Долгопрудного в сторону Дмитрова, даже если вы помните ветку в обе стороны, ездите по ней регулярно. Вот, и наконец, если вы помните так, что вам сказали: "Назови мне номер, там какой пункт программы был под номером 83", такие итераторы — вот это лучше вообще, что вы можете добиться в запоминании. Вот, короче, именно поэтому я нумерую, да? А лучше, да, самое лучше, если у вас конс... Тут у меня, к сожалению, нет житейского примера. То есть представьте, что у вас целый кусок мозга отведёт непрерывный кусок мозга, да, так что ваши нейроны просто подряд срабатывают, когда вы вспоминаете там контейнеры, итераторы. Да, но такого примера из... Я не знаю, чтобы у кого-то был конс итератор на какую-то информацию. Вот, короче, наличие итераторов на какую-то информацию — это прям, ну, это существенность. Вот это помнить с итераторами — это совсем не то же самое, что просто помнить. Помнить можно по-разному. Вот, а хорошо, сейчас мы в оставшееся время поговорим о том, как реализовывать итераторы. Вот следующий пункт будет называться реализация итераторов. А ещё нам надо поговорить про такие вещи, как коре итера... Вот, но я не буду отдельный файл заводить, потому что мы будем это на примере вектора делать. Вот сейчас мы поговорим про то, значит, пункт 84 будет называться `iterators implementation`, а также `const итератор`. А давайте для начала поговорим просто про то, как реализовать итераторы для своего контейнера. Что вам предстоит делать, собственно, когда вы будете писать `Дек`? Ну, как я уже сказал, в контейнере должен быть внутренний тип, называющийся итератор, и он в каждом контейнере есть, но можно сделать его просто структурой `страк итератор`. То есть итератор — это внутренний класс внутри класса контейнер. Вот, и что этот итератор будет из себя представлять? Вот мы с вами... Ситуация, когда нам понадобился класс внутри класса, с вами разбирали там какие-то абстрактные примеры. Нас жизнь... Вот пример, когда мы реально определяем класс внутри другого класса, и внутри каждого контейнера такой класс определён. Что будет хранить этот тип итератора? Ну вот в случае вектора что он будет хранить? Да, можно хранить про указатель на `Т`. Здесь `Т` — это шаблонный тип исходного класса. Здесь нам не нужно писать `template ty name T`, потому что когда инстанцией итератора тоже у нас итератор внутри уже не шаблонный. Какие методы должны быть у итератора? Ну, наверное, конструктор, правильно? Ну давайте подглядим методы у итератора. Мы вообще хотим коню сра... Ну, все методы. Я уж не буду реализовывать. Давайте... Блин, не то, я опять открыл. Нужно итератор. Вот что должен уметь итератор? Копировать, должен уметь присваиваться, уничтожать, свопа. Ну, э... Вот `Legacy Input итератор` должен уметь создаваться по умолчанию, наверное, да? Или нет? Нет, не кажется, нет. Ну ладно, зря. Ну неважно. Хорошо, давайте сами придумаем, что мы хотим. Мы хотим уметь копировать. От конст итератора равно `default`, а присваиваться... Ну, деструктор даже писать не буду. Вот, хотим, что мы хотим? От чего мы хотим уметь создаваться? Вообще, как нам получить хоть какой-то итератор на вектор? Ну, наверное, нам нужна функция, правильно? У вектора нам нужна функция, которая даёт нам, собственно, итератор, и итератор на вот это вот поле. Но мы, наверное, не хотим, чтобы можно было создавать итератор на вектор от произвольного `Т`. Наверное, этот конструктор мы приватным сделаем. Структу, значит, это будет у меня `priv`, а это будет `паб`. Значит, у меня будет приватный конструктор итератора от `Т звёздочки ПТ`, который просто это `пт` инициализирует. Вот, соответственно, даёт мне итератор на начало. А что мне даёт итератор на `R + СЗ`? Действительно, вот для вектора `N` — это просто честно указатель на элемент после последнего. У вас может возникнуть резонный вопрос: а для `Дека` тогда это что? Ну вот надо подумать, как сделать так, чтобы итератор `end` у `Дека` был как бы осмысленным. А для `энда`, если итератор, должно быть выполнено следующее условие: декремент должен вам давать последний элемент контейнера. Вот мы сейчас реализовали это так, что это верно для `Дека`. Вам надо будет самим подумать, как сделать, чтобы это корректно работало. То есть `ф` от него взять и получить последний элемент контейнера, а не чего. Вот, ладно, что ещё должен иметь итератор? Ну, разыменование итератора давать `Т амперсанд`, оператор звёздочка константный или не константный. И Тото другой, по-хорошему, значит, не константный даёт нам просто `Здо ПТ`. Ну, я, наверное, даже позволю себе такую вольность в одну строчку написать здесь. А ещё кон оператор звёздочка... Нет, неправда, константный. То мне не надо у него делать, чтобы разыменование давало не константный `Т`, константный. Конст итератор конст. Ну, если итератор на него намешано конст, то он... Ну, итератор — это в каком-то смысле обобщение указателя. Это значит, что он сам не должен подвергаться изменению. Но вот под ним то, что лежит, не может подвергаться изменению. Поэтому звёздочка нам будет давать тот тип, который под ним. Инкремент итератора... Где здесь можем? Разно Коста? А, да, мы можем просто `ПЛЮСПЛЮС ПТ`. Извините, что я так пишу. Но простите меня, в одну строчку не очень хорошо так писать. Нет, ладно, слушайте, не буду. Да, давайте всё-таки, как полагается, то потом будете мне тыкать носом, что я так тоже писал. Поэтому вы можете так итератор оператор `п` помнит. Так, э, что здесь надо сделать? Копи итератор `Cop` равно `This плюс плюс`, а плюс-плюс `ПТ`. Return `Copy`. Ну, на самом деле, дальше там надо реализовать ещё оператор `э минус минус`, вот это я не буду делать, это неинтересно. А давайте оператор стрелочку реализуем. Вот стрелочку мы ещё не реализовывали никогда. Как реализовать оператор стрелочку? С оператором стрелочка есть довольно интересный... Да, вот это очень интересный вопрос за гвозд. Как переопределять оператор стрелочку для своих типов? Вот нам впервые сейчас это понадобилось. Уреки довольно... Переопределение, она возвращает `Т звёздочку` и ничего не принимает. А вот значит и возвращает она просто `ПТ`. Да, как это работает? Дело в том, что если задуматься, как переопределить стрелочку, становится понятно, что, ну, это не очень поддаётся стандартному синтаксису переопределения. Ну, что чире, что она принимает, непонятно, она как бы от чего вызывается. Вот в стандарте там костыль такой. Если вы переопределяете стрелочку, когда вы пишете свой тип стрелочка что-то, то значит берётся ваша стрелочка и к тому, что она автомати в стом виде, и компилятор сам допит в него стрелочку. Е лишнюю переопределение стрелочки на самом деле, оно тривиально. Вы просто возвращаете `Потер`, и всё. Вот можно переопределить стрелочку со звёздочкой, кстати, хотите помните, зачем она нужна вообще? Вот, и я не помню. Ну нет, ладно, я шучу. Ям пойнтера подобных типов можно ещё при определять стрелочку со звёздочкой. Ну, наверное, у итератора мы всё-таки не будем её определять как-нибудь потом. Ладно, для умных указателей потом определим. Вот, а стрелочка звёздочка — это тоже оператор, который подлежит переопределению, и строго говоря, для типа, который ведёт всё как указатель, неплохо бы её тоже переопределить. Ну да, ладно, это всё на самом деле неинтересно было. Вот то, что я сейчас написал, это всё такое, это база. Вот интересно поговорить о том, как, во-первых, сделать итератор константный. Не в смысле сам итератор константный, а в смысле то, что под ним не должно меняться. Мы хотим сделать так, чтобы у нас был аналог указателей на константу в мире итераторов, то есть такой вид итератора, что если мы его берём, то разыменование его даёт нам константный темн. Не просто `Т`, а такой итератор тоже должен быть, тоже есть в каждом контейнере. Он называется конст итератор. И вот надо не путать конст пробел итератор. Но это вообще кри, такого никогда не встречается на самом деле, но вот не надо не путать, когда сам итератор константный и когда он кон итератор в смысле. Когда вы увидите кон итератор через знак подчёркивания, это означает, что вы то, что под ним менять не сможете. Вот то, что вы получите при разыменовании, будет константа. И вот это всё на самом деле почти также выглядит. У него только нам надо здесь сделать указатель на константу, и здесь, собственно, возвращать его. Ну и здесь везде вместо итератора написать кон. Да, тихо, тихо, подожди. Вот я вот так сделал, и теперь возникает естественное желание. Хочется убрать, хочется реализовать так, чтобы не копипастить всё два раза и просто... Да, просто, ну это можно сделать с помощью шаблонов. Давайте я просто всё это уберу и скажу, что копипаста не нужна. Давайте придумаем, как единожды написав тело класса итератор, получить и итератор, и конст итератор одним махом. Что надо сделать? Просто можно сделать это шаблонный оператором. Шаблон с каким параметром? Да, с параметром буль, конечно. Смотрите, это будет `бератор`, и мне надо, чтобы в зависимости от шаблонного параметра из конст тип был то `Т звёздочка`, то `конц звёздочка`. Как мне это написать? Как мне написать в зависимости от буль тип либо один, либо другой? Да, `std conditional`, мы это уже проходили. Чит тип будет здесь `std conditional`. Напоминаю, из кон Т звёздочка, наоборот, ко зв Т зв ПТ. И здесь то же самое. Да, да, можно, можно, можно. Можно, можно, да, написать. И это тоже правильная мысль. Давайте напишем, кстати говоря. В общем-то, мне надо это сделать. Я же сделаю. Давайте я, значит, определю `Pointer Type` как вот такой `std conditional`. Да, публично. Сейчас сделаем. Значит, `Pointer Type` — это вот такой `std conditional`, дальше `reference Type` — это вот такое `std conditional`. Здесь-то `ersan`, ну, value Type. Давайте заодно это `T`, это `Public`. Теперь `Pointer Type`... Блин, я забыл, как... Ладно, к сожалению, я не очень большой мастер вима `poter Type`. А, всё, ну ладно, неважно. Так, `Pointer Type` — это `ptr`. Ну и конструктор здесь, соответственно, `reference Type`, здесь снова `Pointer Type`. Круто. Теперь, а что такое итератор? Вот этот `B итератор` теперь должен быть приватным на самом деле. Что такое итератор? Это просто... Н, теперь у нас будет публичный н итератор равно итератор с параметром, а Коте это см `True`, вот и всё. Вот сейчас про реверс поговорим, но сначала поговорим про `begin` и `end`. Вопрос: а вот методы `begin` и `end`, они константные или нет? Ну, это очень странно на самом деле, правильно? Методы `begin` и `end` определить по-разному для константной `Вектора` и для не константной `вектора`. Если вы у константного `Беги`, вы тоже должны мочь это сделать, но он просто вернёт вам контор. Соответственно, вот эти все вещи я копирую и здесь заменяю. Вместо итератора пишу кон итератор. Кстати, я могу... Здесь можно не писать, потому что это и так сработает. Здесь я... И тут, и тут нашу справа. То есть у констант вектора тоже должно быть можно выть и получить ко таким обм, но поми, которые возвращают контор даже для не констант контейнера. Вот они не константные и возвращают. Вот это и, соответственно, контор `CN` не константный метод возвращает `R п СЗ` как конте для не констант контейнера. То есть у любого контейнера хоть у констант, хоть не констант можете константный итератор, а у не у константной где... Ой, да, Господи, конечно, чушь. Да, наоборот. Извините, я сам перепутал. `Гин мот` вызвать и... Ну да, и у обычного контейнера, и у константной Нера. Просто в первом случае произойдёт неявный ка константной Неру. Вот, а `бегин` для констант и не константный контейнеров ведут себя по-разному. Вот хорошо, что такое? Да, ещё у контейнеров есть такой тип `Rat`. Ну и `Con`. Но сначала я вам покажу тип, называемый `std reever`. Снова идм в `Library` и видим тут такой замечательный тип `rever итератор`. Картинка, иллюстрирующая идею. А вы хотите уметь ходить по последовательностям и назад. Если исходный итератор был хотя бы `bal`, как вам обойти `Map`, например, или `Set` в обратном порядке, если у вас в `НМ`? Для этого надо использовать итератор. Итератор — это на самом деле отдельный класс стандартной библиотеки. Вот это важно понять. `R итератор` — это на самом деле отдельный класс `std`. Вот простора — это такой тип был, но он устарел, 17, по-моему, Удан. Уже, ну, в общем, его нет больше. Считайте, итератор — это довольно бесполезная штука оказалась. Ей мы никогда не пользуемся, а вот итератор — это внутренние типы контейнеров. А вот это вполне полезная штука. И на самом деле это такой адаптер над итератором. То есть он шаблонирует другим оратором, которая берёт просто все ваши действия и разворачивает в обратную сторону. То есть что такое `РС итератор`? Ну вот от чего можно создать реверс итератор? Его можно создать от произвольного итератора, и он в себе будет хранить этот итератор. Когда вы ратор просите сделать `ПЛЮСПЛЮС`, он просто декремент делает у итератора, который лежит в нём. Когда `РС итератор` просите минус-минус, он у литератора, который лежит в нём, наоборот делает плюс-плюс. Когда вы делаете звёздочку или стрелочку, он вам просто возвращает, но возвращает он вам не тот, что лежит, а его минус один. Вот зачем. Чтобы вы... Чтобы, ну, типа так удобно. Вот когда вы получаете, как бы, когда вы от Бена делаете, вы получаете `rn`. `R` — это итератор на перед началом, это итератор на конец. Таким образом, если вы хотите сделать итератор, вы получите не итератор на то, чего не существует, а на итератор перед концом. Поэтому разыменование даст вам итератор. То, что лежит под итератором рата, вот если я хочу в своём контейнере, а я должен в любом контейнере определить тип, что это такое. Но это просто `using итератор` — это `std reverse итератор` от итератора и всё. Ничего писать не надо. С `Кост реверс итераторов` итератор от `Кост итератор` — всё. Свер ораторами всё просто писать, ничего не надо самостоятельно реализовывать. Реверс итераторы тоже не надо. Всё, теперь мы умеем ходить взад-вперёд по вектору с помощью итераторов. Да, есть `rend`, `crin`, `crn`, понятно, что они делают. Соответственно, `rin` даёт вам итератор на последний элемент, `rn` даёт вам итератор на элемент перед первым, как бы вот симметрично тому, что делал. Также `CR CR` аналогично себя ведут, как `C`. Вот такие дела. Вот, а ну хорошо, что я вам могу сказать? Круто, вроде разобрались, как реализовывать итераторы в контейнерах. Ну, в векторе, но понятно, что теперь вы можете по аналогии реализовать итераторы в... Вот, но вот в деке уже итераторы чуть менее тривиальные, потому что в деке итератор должен хранить не только просто `Потер`, вот, а он должен хранить, ну, поинте число, либо два поинте. То есть когда у нак это просто, когда у нак это массив, вот итератор нак уже посложнее устроен. М нужно в эрато помнить номер, ну, ячейку во внешнем массиве и номер ячейки в соответствующем внутреннем массиве. Вот теперь давайте я вам напоследок задам вот такой вопрос, прежде чем закончить этот разговор про итераторы в контейнерах. Вот смотрите, вот я эту... Сегодняшний вечер с разговора про то, что если я возьму вектор, сделаю в нём `пушк`, но перед этим возьму, значит, там `имн X = V5`, а потом выведу `V5`, то будет э. Я сказал, что если я так сделаю с деком, то всё будет хорошо. Вопрос в следующем: а что если я здесь делаю не указатели, не ссылку, а итератор `std векто итератор X рано`, ну, скажем, `V`, то также точно плю 5 доложил что-то в вектор, и значит, что будет? Ну, нет, яд. Вектор здесь использует. Вот как повет себя вектор? Можно ли так делать с итераторами? Мы обсудили, что с указательными ссылками так делать нельзя в векторе, но можно в деке. А что насчёт итераторов? Другими словами, происходит ли инвалидация итераторов? Вот этот пример очень важный, он ещё более важен, чем пример с за скамом дее. А вот в случае с остальными контейнерами вот этот пример более важен. Верно ли, что я могу взять итератор на элемент какого-то контейнера, дальше доложить каких-то элементов этот контейнер, а потом пользоваться итератора как в чём не бывало? Бывало разыменование. Это очень важный вопрос, и это важный вопрос как с практической точки зрения, так и с меркантильной точки зрения. Потому что его тоже очень любят на собеседованиях задавать. Если честно, вот вопрос про то, как ведут себя контейнеры с итераторами — это такое знание, которое всем обязательно надо помнить. Что происходит с итераторами в контейнерах, если вы что-то где-то перекладываете. Очень рекомендую запомнить то, что мы сейчас будем обсуждать про это. Так, всё-таки можно ли так делать в векторе? Ну, давайте. Кто считает, что всё можно и корректно всё будет? Кто считает, что нельзя и будет ошибка? Удивительно, я снова удивлён. Мне почему-то казалось, что это знание должно у всех присутствовать. Мне кажется, это какой-то очевидный вопрос. Он у вас в анкете же был, да? В распределительной, которая была в первом семестре, да? Кажется, это был один из последних вопросов в той анкете, которую вы заполняли для распределения на продвинутый поток. На самом деле, сегодня у нас последняя тема, вам скажу. Видите, рата была по первому семестру, в точности по нему. Да, мы с вами подошли к последнему тому, вас спрашивали в той анкете. Можете себя проверить, пройти ту анкету ещё раз и проверить, что вы теперь всё знаете. Ответ, конечно же, нет, нельзя так делать. Конечно же, это инвалидация итераторов, и это очевидно. Само собой, делать в векторе так нельзя. Вот, хранить итераторы, как бы мы тогда инвалидацию итераторов, а развали тогда как? То есть, вот послушайте, мы сейчас обсуждаем это, тоже важно. Вот говорится следующее: мы могли бы в итераторах вектора хранить просто индекс, а также указатель на сам вектор. Вот, а ну давайте сначала поймём, почему это плохо, а потом поймём, почему нет, не могли. Формально, на самом деле, да, смело. Потому что это неэффективно. Если бы мы в итераторах хранили указатель на сам контейнер, то разыменование итератора занимало бы два разыменования вместо одного. Мы хотим, чтобы разыменование итератора было так же дёшево, как разыменование указателя. Это важно, и получить, наконец, элемент. Тогда итератора было бы невыгодно пользоваться, потому что разыменование, оно, конечно, не очень дорого стоит, но оно стоит, ну, на порядок подороже, чем просто инкремент. Именно поэтому в деке, даже в деке, мы не можем хранить указатель на контейнер в итераторе. Указатель на контейнер — это, ну, это слишком. Это дурацкая затея, просто эффективность итератора теряется тогда. Но на самом деле мы и формально не можем так делать, потому что мы тогда не сможем соблюсти одно из требований к итераторам. Я вам сейчас покажу, какое. Значит, итераторы должны оставаться корректными. То есть вот итераторы, давайте я вам покажу. Вот, давайте я открою снова вектор, и тут есть метод `swap`. Я напомню, метод `swap` должен быть по требованию у любого контейнера. Вот здесь написано, что при `swap` двух контейнеров не должно быть так, что вы `swap` вектор с другим вектором, и у вас итераторы полетели от этого. Вот это для всех контейнеров так должно быть. Если у вас есть два дека, вы их `swap` — то итераторы должны продолжать указывать, куда они указывали в контейнерах. Или, лома контейнеры `swap`, итераторы продолжили указывать на те же данные, хотя владения контейнеров сменились. Поэтому мы не можем в итераторах хранить указатель на контейнер ни с точки зрения производительности, ни с точки зрения формального соответствия стандарту. Вот поэтому итераторы в векторе инвалидации. Если вы меняете вектор, если вы кладёте что-то в вектор, и не только в векторе, а и в деке тоже. И вот это уже довольно тонкое, довольно глубокое понимание, но просто довольно глубокое понимание, что в деке указатели и ссылки не инвалидации, а вот итераторы всё ещё инвалидации. То есть завести указатель или ссылку на элемент дека, а потом положить что-то в дек, указатель или ссылка останется валидной. А вот завести итератор на элемент дека и что-то положить в дек после этого — это уб. Осознайте, почему, но вы это осознаете, когда будете писать дек, потому что вам нужно хранить указатель на элемент внешнего массива. Но внешний массив может релоцироваться при пушке в дек, поэтому указатели и ссылки при пушке в дек не инвалидации, а итераторы инвалидации. Это не тривиально, и это надо понимать. Вот инвалидация итераторов — это такая важная тема. Я говорю, её любят спрашивать в том числе на собеседованиях всяких по плюсам. А есть целая таблица, что инвалидации при каких действиях над контейнерами. Вот мы с вами попозже, чуть-чуть, когда изучим остальные контейнеры, систематизируем все наши знания и нарисуем большую таблицу, в том числе с инвалидацией, связанной. Вот, но, например, можно уже сейчас, наверное, сказать, например, про лист. Вот связанный список, в нём что инвалидации, а что нет? Как вы думаете, указатели, ссылки, итераторы? Вот в связанном списке ничего не инвалидации никогда, потому что никто ничего никогда не релоцирует. Связанный список как раз хорош тем, что сколько в него не вставляй, указатели, ссылки и итераторы на предыдущие элементы будут по-прежнему валидны. Таким же свойством обладает и дерево. В нём вершины, ноды не релоцируются, в них только переставляются поинтеры, они переподключаются. Последний пункт на сегодня — это аутпут-операторы. Это пункт 85, и это, видимо, последний пункт, который мы пройдём в этом семестре — аутпут-операторы. Я долго вас мучил загадкой, что же это за операторы такие. Вот смотрите, у нас есть алгоритм `copy`. Ну, давайте я задам алгоритм. Да, давайте я назову пункт "Итераторы и аутпут-итераторы". Вот у меня есть массив `in` квадратные скобочки 10, 1, 2, 1, 2, 3, 4, 5, и есть, не знаю, вектор `vector`. И вот я хочу переложить, скопировать элементы одного диапазона в другой с помощью `copy`. Пишу `copy(in, ... )`. Ну, там `first`, `last` и куда копировать `v`. А могу так написать? Я просто взял поэлементно, скопировал элементы вектора в этот массив. Могу, но вот вопрос: могу ли я написать, ну, у меня `A` — это массив из элементов, а `B` — это вектор, массив из пяти элементов. Вот могу ли я написать там `std::copy(A, A + 10, v.begin())`? Что будет, если я так напишу? Сломается ли что-нибудь? А что именно будет? Потому что что такое `copy`? Это просто тупой алгоритм, который разное инкрементирует, рамено присваивает, инкремент минует, присваивает инкремент. Он не делает `push_back`. Алгоритм `copy` ничего не знает про то, что под итераторами лежит. Он воспринимает итератор как указатель. Он просто рамено инкрементирует и так далее. Если я передам ему вектор, он просто начнёт писать по... Ну, за границу вектора. Хуже, если я передам ему лист — это вообще весело будет. Он разменёт `begin` листа, и потом инкремент. Ну, то есть, ладно, ещё вектор, там хотя бы кон... там хотя бы элементы в памяти подряд лежат. Если он не зайдёт за границу вектора, то он просто будет писать подряд по памяти. Но если там связанный список или `set`, то он в какой-то момент, когда дойдёт до конца, он сделает инкремент итератора, и будет... Поскольку инкремент — это же прыжок по указателю. Но если там конец списка, там указатели никуда не ведут. Он может вести, он может быть зацикленным, вести сам на себя, например, тогда он будет просто писать на себя, в себя же несколько раз. А он может быть натром, и тогда он упадёт. Короче, эти итераторы не подходят для того, чтобы по ним писать, и поэтому они не являются аутпут-итераторами. Так вот, аутпут-итератор — это такой итератор формально, который гарантирует, что можно его разыменовывать. Вот что такое итератор? Это итератор, который гарантирует вам корректность, если вы будете писать в него с помощью алгоритмов. Вот эти вот, которые что-то пишут по контейнерах, такими не являются. Нам нужен отдельный вид итераторов — аутпут-итераторы. Первый пример будет называться `back_insert_iterator`. Вот давайте подумаем, как сделать так, чтобы я мог использовать стандартные алгоритмы над контейнерами, чтобы в контейнеры писать. Вот я хочу написать `copy_if`, например. Если, ну, то есть что такое `copy_if`? Да, это алгоритм, который пишет по итераторам при соблюдении условия какого-то. Да, что такое `copy_if`? Да, например, скопировать все чётные числа. Вот что ж такое? Вот какая сигнатура? Ну, точно также `A`, `10`, `B`, `v.begin()`, что будет, если я так напишу? У меня `A` — это массив из элементов, а `B` — это вектор, массив из пяти элементов. Вот могу ли я написать там `std::copy_if(A, A + 10, v.begin(), pred)`? Предикат — это какая-то одноместная функция. Да, мне нужно на данным элементом. Я вот буду передавать сюда вот этот вот `pred`, и предикат должен привести к тому, что я скопирую в вектор все чётные числа. Но я не могу так напрямую вызывать этот алгоритм, потому что он мне вызовет ошибку, потому что будет писать мимо вектора, начиная с какого-то момента. Я, конечно, могу сделать `v.reserve`, но уже с деком я не могу сделать `reserve`, с листом тоже. Как мне, что мне нужно какую-то, так сказать, надстройку над вектором сделать? Какой интерфейс? Эта обёртка называется `back_insert_iterator`. Это адаптер на итератор, который хранит ссылку на контейнер и умеет конструироваться от контейнера. Да, вот я проинициализировался `push_back`. Смотрите, какой трюк. Это просто трюк. Это трюк сродни трюку с вектором. Я определю своему итератору оператор присваивания от `value_type` контейнера. Я определю своему итератору, ну, `back_insert_iterator` оператор присваивания от `const typename Container::value_type`. Напомню, что в контейнере есть внутренний тип `value_type`, который говорит, какой тип в этом контейнере лежит. Это обязательно должно быть по требованиям к контейнеру. `value_type value`. И что в этот момент я буду делать? Я буду просто говорить `container.push_back(value)`. Ну и `*this`. А теперь что я буду делать, когда мне говорят инкремент? Ничего. А что я буду делать, когда мне говорят разыменование? Ничего. Звёздочка будет возвращать мне меня же самого. Блин, то есть смотрите, какая фишка. Я звёздочку и плюс-плюс переопределяю. Звёздочка на самом деле не новая, а возвращает его же. И что происходит, когда вот написано вот такое: `*it++ = value`? Ну, ещё надо постфиксный инкремент, конечно, определить. Да, вот постфиксный инкремент, который возвращает копию. Ну, можно сказать, что он тоже ссылку на самом деле возвращает и тоже ничего. Но что происходит, когда случается делается инкремент? Возвращается, ну, ссылка или копия — неважно. Пусть копия делается, инкремент возвращается, копия, а виноват. Вот сюда мы при делаем, возвращается копия, инкремент ничего не делает. См. при этом, потом делаем разыменование. Опять снова он и ему присваивается `value`. Мы оператор присваивания определили не от другого итератора, а от `value` контейнера. То есть итератор мы присваиваем значение элементов контейнера, и это приводит к тому, что в контейнер делается `push_back`. Таким образом, эта обёртка над итератором позволяет нам вызывать стандартные алгоритмы над контейнерами и класть в них, будто мы пишем. То есть код написан так, как будто мы пишем просто по массиву, а в реальности мы `push_back` в контейнер делаем. Вот, но писать `std::back_insert_iterator` откровенно неудобно, потому что это очень длинно. Приходится писать название контейнера. Поэтому есть функция, она нужна просто для того, чтобы поменьше писать кода в своём коде. Что она делает? Она просто `typename Container` — это функция, которая возвращает `back_insert_iterator` от контейнера. `back_inserter` от контейнера `&container`, и она просто создаёт вот этот `back_insert_iterator` от этого контейнера. И вместо того, чтобы здесь писать `std::back_inserter` и повторять вот этот вот тип контейнера, можно писать короче и писать просто `back_inserter(v)`. Вот помимо есть `insert_iterator`, который делает то же самое, только делает и просто итератор, который принимает не только контейнер, а контейнер и итератор в этом контейнере. Ну, применим к вектору, к листу и так далее. Понятно, к вектору не применим, только к листу. Ну и всё. Вы можете, например, `insert_iterator` отдать связанный список и итератор на элемент в этом связанном списке, и `insert_iterator` будет писать по этому итератору туда. То есть он будет не `push_back` делать, а метод `insert` вызывать у данного контейнера по данному итератору. Понятно? Вот это пример аутпут-итератора. У нас осталось разобрать ещё пример итераторов над потоками. Вот, но, видимо, это мы сделаем уже в следующий раз. Я напоследок под Новый год расскажу, что такое потоковые итераторы. Ну, ещё кое-что расскажу. Во, а вот, ну что, видимо, всё на сегодня тогда.

Назад

Залогинтесь, что бы оставить свой комментарий