Инвалидация ссылок

Loading...

Del curso dictado por Moscow Institute of Physics and Technology

Основы разработки на C++: красный пояс

66 calificaciones

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Moscow Institute of Physics and Technology

Основы разработки на C++: красный пояс

66 calificaciones

Curso 3 de 5 en SpecializationИскусство разработки на современном C++

Этот курс является продолжением курса "Основы разработки на C++: жёлтый пояс". Основная цель курса — научить писать на С++ эффективный код. Кроме того рассмотрены некоторые возможности С++, которые не попали в предыдущие курсы. В курсе рассмотрены: - макросы - шаблоны классов - принципы оптимизации кода - эффективное использование потоков ввода/вывода - оценки сложности алгоритмов - модель памяти в С++ - эффективное использование линейных контейнеров (vector, deque, list, string) - move-семантика - введение в многопоточное программирование Кроме того, в курсе продемонстрировано, как, пользуясь знаниями только "Белого", "Жёлтого" и "Красного" поясов, разработать свой собственный профайлер. Так же, как и в предыдущих курсах, в конце вас ждёт финальный проект. Было бы странно в курсе от Яндекса не попросить вас создать свою поисковую систему! Именно этим вам и предстоит заняться в финальной задаче. Курс разработан ведущими специалистами Яндекса и преподавателями Школы анализа данных. За их плечами – годы разработки сервисов поиска, рекламы и инфраструктуры. Кроме того в подготовке заданий участвовали 1. Сотрудники Яндекса: - Алексей Аверченко - Даниил Петров - Константин Меренков - Алексей Зобнин 2. Выпускники «Жёлтого пояса по С++»: - Борис Егоров - Ольга Марчевская 3. Сотрудник Института проблем информатики РАН Олег Яковлев В создании урока «Шаблоны классов» принимал участие преподаватель Белого и Жёлтого «поясов» Евгений Парамонов.

De la lección

Эффективное использование линейных контейнеров

Эффективное использование вектора12:36

Инвалидация ссылок8:39

Эффективное использование дека11:47

Инвалидация итераторов6:20

Контейнер list6:08

Преимущества списка9:55

Неинвалидация итераторов списка5:24

Контейнер array12:14

Внутреннее устройство массива4:36

Класс string_view8:48

Удобное использование string_view5:35

Безопасное использование string_view5:32

Conoce a los instructores

Полднев Антон Вячеславович

Яндекс
Шишков Илья Иванович
кандидат технических наук
Яндекс

В прошлом видео мы узнали, что стандартный вектор,

подобно тому вектору, который вы написали в блоке про модель памяти,

реалацирует память иногда, когда вы добавляете в него новые элементы,

потому что ему не хватает той памяти, которая у него была.

У этой особенности векторы есть некоторые спецэффекты, некоторые побочные действия.

Давайте посмотрим какие именно. Вот у нас был вектор из трех чисел,

мы добавляем его четверку, что если перед добавлением четвёрки

я захочу запомнить ссылку на первый элемент вектора, я напишу так,

ссылка на int называется first иницилизируем его с помощью v нуля.

Я эту ссылку проинизилизировал, давайте я выведу, что в ней лежит,

до пушбека и после. Что же у меня произойдёт?

Изначально, конечно, я просто увижу единицу, потому что у

меня там была единица и вот я как раз ее вывел,

но после пушбека мы знаем, что вектор переместил свои данные в другое место,

а старые данные освободил и теперь по той же самой ссылке,

по которой мы только что видели единицу,

мы теперь увидели какое-то огромное мусорное число.

Это ожидаемо на самом деле, если вы узнаете,

как устроен вектор и как работает пушбек, вы могли ожидать, что эта ссылка испортится,

что это ссылка перестанет

быть валидной или инвалидируется и на самом деле вот это инвалидация,

это не просто какая-то забава, способ показать,

что у виктора данные опережают, нет, это важное понятие,

которое много раз даже упоминается в документации к языку C++.

Вы можете зайти в документацию вектора и увидеть, что там будет написано,

что если вы добавляете элемент вектор, у вас ссылки на элементы инвалидируются,

ссылки перестают быть валидными и давайте продемонстрируем, почему это может быть важно.

Перед этим видео мы предложили

вам тренировочную задачу на реализацию контейнера, контейнера,

в который нужно было добавлять строки с некоторым приоритетом с помощью метода add,

а также находить последнюю добавленную строку и строку с наибольшим приоритетом.

Как это можно было реализовать?

В опубликованном нами решении прилагается следующее,

складывать строки в вектор

и помимо этого складывать их в set с помощью структур, которые называется string item.

В каждой структуре лежит сама строка, еще раз заметьте,

она лежала в векторе, а еще лежит вот здесь,

вместе с приоритетом и у нас есть некоторое оператор сравнения,

которое сравнивает эти string item-и по приоритету.

Соответственно, при добавлении строчки в контейнер мы кладем ее в вектор и в set,

в методе find last мы берем последний элемент вектора,

а в методе find best мы берем последний элемент

set-а и соответственно строчку s, которая там лежит.

Давайте даже на простом примере покажем, что этот код работает

а именно создаем контейнер string,

кладем туда сначала строчку upper с высоким приоритетом, он потому и называется upper и

затем строчку lower, с низким приоритетом.

Соответственно метод find last должен вывести последнюю добавленную строчку,

то есть lower, а метод find best должен вывести строчку с наибольшим приоритетом, т.е.

upper, то есть мы должны увидеть lower upper.

Давайте этот код скомпилируем, запустим и

увидим действительно ли она работает так, как мы ожидаем.

Да действительно, lower и upper.

Хорошо, но вообще мы говорим о написании эффективного кода.

Неужели это правда эффективно складывать одну и ту же строчку и в вектор и во множество?

Вообще говоря - нет, хочется этого как то избежать

и складывать строчки только в один контейнер,

раз уж мы говорим про эффективность.

Хорошо, что же здесь можно сделать,

что же здесь хочется сделать в первую очередь?

Хочется сложить строчки в один контейнер, а в другой контейнер складывать,

ну скажем, ссылки на строчки в том контейнере,

а именно давайте у нас вектор строк останется как есть,

но во множестве мы будем класть вместе с приоритетом не саму строчку,

а ссылку на нее,

ссылку на эту строчку в векторе.

Как изменится код, который мы написали?

Вектор мы все также вставляем исходную строчку,

а сюда мы вставляем, пожалуй, не ссылку на строчку, которая была снаружи,

потому что она может уничтожится и т.д.,

а ссылку на строчку,

которую мы добавили вектор только что, соответственно,

здесь по напишем datа.back, последний элемент вектора data.

Find last остается как есть, а find best мы возвращаем ссылку на эту строчку,

то есть код не меняется.

Давайте попробуем его скомпилировать и запустить

и lower вывелось, а upper - нет.

Видимо там вывелась пустая строка. Что же произошло?

Да, инвалидация конечно произошла, вы добавляли строчки в вектор,

добавляли, добавляли, сохраняли ссылки на них во множестве,

но вектор в процессе свои строчки куда-то переместил и все,

теперь ссылки, которые лежат во множестве, не валидние,

они инвалидировали, ровно то, о чем мы и говорили.

Инвалидация - важное понятие. Вот например,

вот здесь, на этом примере,

на примере контейнере string set продемонстрировали,

что инвалидация важна и в реальной жизни она действительно случается,

даже в финальной проекте второго курса у вас возникала похожая задача.

Как же можно эту проблему решить в данном случае?

Например, можно использовать контейнер,

который не обладает таким недостатком как вектор, например, deque.

Давайте я подключу deque и вместо вектора здесь использую deque.

Просто заменил вектор на deque и запустил.

Код компилируется, все еще компилируется, и теперь он работает правильно.

Смотрите, очень удобно на самом деле, я просто взял,

заменил слово вектор на слово deque,

подключил библиотеку deque и всё,

мой код работает, мой код больше не обладает таким недостатком, как инвалидация ссылок.

Замечательно, это конечно очень интересно,

наверное deque устроен как-то по другому,

не так как вектор и эту интригу мы раскроем в следующем видео,

а в этом видео давайте обсудим ещё вот что,

что если вам всё таки важно,

чтобы у вас оставался вектор а не deque.

Тогда, конечно, вам придётся отказаться от ссылок. Как это можно сделать?

Например, можно вместо ссылок хранить индексы элементов в векторе.

Давайте попробуем, int idx, давайте поправим наш код.

Теперь нам нужно складывать во множество индекс,

то есть номер последнего элемента в векторе,

data size -1, find last остается как есть,

а в find best код становится чуть сложнее.

Мы должны по итератору достать поле idx,

а затем обратиться к элементу вектора data то с таким номером.

Вот, пожалуй, так будет то, что нужно.

Давайте этот код скомпилируем и запустим.

И у нас lower и upper, отлично.

Итак, как можно разбираться с инвалидацией?

Вектор инвалидирует ссылки и если мы хотим эту проблему как-то решить,

мы можем либо использовать deque и здесь

мы расскажем в следующем видео про внутренне устройстве deque,

либо можем хранить индексы.

Но хранение индексов влечет за собой необходимость, по сути,

таскать за собой этот самый вектор,

вы не можете просто по одному лишь индексу получить сам элемент, по ссылке можете,

а по индексу не можете,

поэтому если вы решаете хранить индекс на элемент вместо ссылки,

то будьте готовы к тому, что вам нужно знать еще и сам вектор,

чтобы обратиться по этому индексу к элементу этого вектора.

Итак, обсудили инвалидацию ссылок,

в следующем видео обсудим, как же устроен deque и почему ссылки в нем не инвалидируются.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play