Этот курс является продолжением курса "Основы разработки на C++: жёлтый пояс". Основная цель курса — научить писать на С++ эффективный код. Кроме того рассмотрены некоторые возможности С++, которые не попали в предыдущие курсы. В курсе рассмотрены: - макросы - шаблоны классов - принципы оптимизации кода - эффективное использование потоков ввода/вывода - оценки сложности алгоритмов - модель памяти в С++ - эффективное использование линейных контейнеров (vector, deque, list, string) - move-семантика - введение в многопоточное программирование Кроме того, в курсе продемонстрировано, как, пользуясь знаниями только "Белого", "Жёлтого" и "Красного" поясов, разработать свой собственный профайлер. Так же, как и в предыдущих курсах, в конце вас ждёт финальный проект. Было бы странно в курсе от Яндекса не попросить вас создать свою поисковую систему! Именно этим вам и предстоит заняться в финальной задаче. Курс разработан ведущими специалистами Яндекса и преподавателями Школы анализа данных. За их плечами – годы разработки сервисов поиска, рекламы и инфраструктуры. Кроме того в подготовке заданий участвовали 1. Сотрудники Яндекса: - Алексей Аверченко - Даниил Петров - Константин Меренков - Алексей Зобнин 2. Выпускники «Жёлтого пояса по С++»: - Борис Егоров - Ольга Марчевская 3. Сотрудник Института проблем информатики РАН Олег Яковлев В создании урока «Шаблоны классов» принимал участие преподаватель Белого и Жёлтого «поясов» Евгений Парамонов.
Инвалидация ссылок
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Основы разработки на C++: красный пояс
99 calificaciones
Moscow Institute of Physics and Technology
99 calificaciones
Curso 3 de 5 en SpecializationИскусство разработки на современном C++
De la lección
Эффективное использование линейных контейнеров
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.
