C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц
C++17 STL Стандартная библиотека шаблонов читать книгу онлайн
С++ — объектно-ориентированный язык программирования, без которого сегодня немыслима промышленная разработка ПО. В этой замечательной книге описана работа с контейнерами, алгоритмами, вспомогательными классами, лямбда-выражениями и другими интересными инструментами, которыми богат современный С++. Освоив материал, вы сможете коренным образом пересмотреть привычный подход к программированию.
Преимущество издания — в подробном описании стандартной библиотеки шаблонов С++, STL. Ее свежая версия была выпущена в 2017 году. В книге вы найдете более 90 максимально реалистичных примеров, которые демонстрируют всю мощь STL. Многие из них станут базовыми кирпичиками для решения более универсальных задач.
Вооружившись этой книгой, вы сможете эффективно использовать С++17 для создания высококачественного и высокопроизводительного ПО, применимого в различных отраслях.
Если же подсказка ошибочна, то функция вставки попросту проигнорирует ее и начнет работу с выполнения алгоритма поиска. В итоге она отработает корректно, но, очевидно, медленнее.
Эффективно изменяем ключи элементов std::map
Поскольку структура данных std::map соотносит ключи со значениями таким образом, что ключи всегда уникальны и отсортированы, очень важно исключить для пользователей возможность изменить ключи узлов, которые уже вставлены в контейнер. Чтобы пользователи не могли изменять ключи элементов идеально отсортированных узлов ассоциативного массива, к типу ключа добавляется слово const.
Такого рода ограничение разумно, поскольку пользователю будет сложнее неправильно задействовать контейнер std::map. Но что же делать, если нам вдруг действительно понадобится изменить ключи некоторых элементов ассоциативного массива?
До появления С++17 нам приходилось удалять элементы, для которых нужно изменить ключ, а затем вставлять их снова. Недостаток такого подхода состоит в выполнении бесполезных выделений и высвобождений памяти, что плохо с точки зрения производительности.
Начиная с С++17 можно удалить и снова вставить элементы ассоциативного массива без повторного выделения памяти. Далее мы увидим, как это работает.
Как это делается
В этом примере мы реализуем небольшое приложение, которое упорядочивает список водителей, участвующих в вымышленной гонке, в структуре std::map. По мере того, как водители обходят друг друга во время гонки, нужно изменять ключи, показывающие их текущее место. Мы будем делать это в стиле С++17.
1. Начнем с того, что включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:
#include <iostream>
#include <map>
using namespace std;
2. Мы выведем на экран места всех водителей до и после изменения контейнера map, поэтому реализуем вспомогательную функцию, посвященную именно этому:
template <typename M>
void print(const M &m)
{
cout << "Race placement:n";
for (const auto &[placement, driver] : m) {
cout << placement << ": " << driver << 'n';
}
}
3. В функции main создадим и инициализируем ассоциативный массив, в котором целые числа, указывающие текущее место гонщика, будут соотноситься со строками, содержащими его имя. Кроме того, выведем содержимое ассоциативного массива на экран, поскольку на следующих шагах изменим его.
int main()
{
map<int, string> race_placement {
{1, "Mario"}, {2, "Luigi"}, {3, "Bowser"},
{4, "Peach"}, {5, "Yoshi"}, {6, "Koopa"},
{7, "Toad"}, {8, "Donkey Kong Jr."}
};
print(race_placement);
4. Предположим, что на одном из кругов гонки у Боузера (Bowser) произошла небольшая авария и он откатился на последнее место, а Донки Конгу — младшему (Donkey Kong Jr.) представился шанс перескочить с последнего места на третье. В данном случае сначала нужно извлечь указанные элементы из ассоциативного массива, поскольку это единственный способ манипулировать их ключами. Функция extract — новая возможность С++17. Она удаляет элементы из массива, притом не вызывая побочных эффектов, связанных с выделением памяти. Создадим также новую область видимости для данной задачи.
{
auto a (race_placement.extract(3));
auto b (race_placement.extract(8));
5. Теперь поменяем местами ключи Боузера и Донки Конга — младшего. Несмотря на то, что ключи элементов ассоциативного массива обычно неизменяемы (поскольку объявлены с модификатором const), можно изменить ключи извлеченных элементов, полученных с помощью метода extract.
swap(a.key(), b.key());
6. Метод insert контейнера std::map в С++17 получил новую перегруженную версию, которая принимает дескрипторы извлеченных узлов, чтобы вставить их в контейнер, не вызывая выделения памяти:
race_placement.insert(move(a));
race_placement.insert(move(b));
}
7. Выходим из области видимости, и на этом все. Выводим на экран новые места гонщиков и позволяем приложению завершиться:
print(race_placement);
}
8. Компиляция и запуск программы дадут следующий результат. Сначала мы видим изначальную расстановку гонщиков, а затем новую, которую получили после изменения позиций Боузера и Донки Конга — младшего:
$ ./mapnode_key_modification Race placement:
1: Mario
2: Luigi
3: Bowser
4: Peach
5: Yoshi
6: Koopa
7: Toad
8: Donkey Kong Jr.
Race placement:
1: Mario
2: Luigi
3: Donkey Kong Jr.
4: Peach
5: Yoshi
6: Koopa
7: Toad
8: Bowser
Как это работает
В C++17 контейнер std::map получил новую функцию-член extract. Она поставляется в двух версиях:
node_type extract(const_iterator position);
node_type extract(const key_type& x);
В этом примере мы используем вторую версию, которая принимает ключ, а затем находит и извлекает соответствующий ему элемент ассоциативного массива. Первая версия функции принимает итератор, что подразумевает ее более быструю работу, поскольку ей не нужно искать элемент.
Если мы попробуем извлечь с помощью второго метода (выполняющего поиск по ключу) элемент, которого не существует, то получим пустой экземпляр типа node_type. Метод-член empty() возвращает булево значение, которое указывает, пуст ли экземпляр node_type. Вызов любого метода для пустого экземпляра приводит к неопределенному поведению.
После извлечения узлов можно изменить их ключи с помощью метода key(), который предоставляет неконстантный доступ к ключам, несмотря на то что они обычно являются неизменяемыми.
Обратите внимание: для повторного добавления узлов в ассоциативный массив нужно передать их в функцию insert. Это логично, поскольку функция extract стремится избежать создания ненужных копий и выделения памяти. Еще одно примечание: хотя мы перемещаем экземпляр типа node_type, на самом деле никакие значения из контейнера не перемещаются.
Дополнительная информация
Элементы ассоциативного массива, которые были извлечены с помощью метода extract, обычно довольно гибкие. Можно извлечь элементы из одного экземпляра типа map и вставить их в любой другой экземпляр типа map или даже multimap. Это верно и для контейнеров unordered_map и unordered_multimap, а также set/multiset и, соответственно, unordered_set/unordered_multiset.
Для того чтобы можно было перемещать элементы из одной структуры ассоциативного массива или множества в другую, типы ключей, значений и средство выделения памяти должны быть идентичны. Обратите внимание: даже
