Контейнеры STL: list. Часть 4




list c++, лист с++, контейнеры STL C++ , Standard Template Library, контейнер с++, двунаправленный список с++В третьей части уроков о контейнерах STL, мы закончили рассмотрение векторов, скажем, типа vector<float> как эквивалента массива вещественных чисел. Для таких «массивов» очень быстро осуществляются операции доступа к элементу (чтение-запись) по индексу и вставка-удаление элемента в конец вектора. Гораздо хуже (по эффективности) выполняются операции вставки-удаления элемента где-то в середине вектора, или перемещение элемента из одной позиции в другую.

Например, в векторе размером 15 операция перемещения 10-го элемента в позицию 2 потребует:

  • запомнить в промежуточной переменной 10-й элемент;

  • для всех элементов с 9-го по 2-й (в обратном порядке, возможно используя реверсный итератор) скопировать в следующую позицию (8 операций копирования);

  • сохранённый ранее в промежуточной переменной элемент скопировать в позицию 2;

Итого, для этой простой операции нам потребовалось 10 операций копирования. Каждый элемент вектора, как уже обсуждалось ранее, может представлять сбой сложно-составную структуру. И его копирование — это достаточно трудоёмкое действие.

Для “коллекций”, в которых планируются активные добавления, удаления и перемещения элементов, библиотека STL предлагает другой вид контейнера — двусвязный список, list. Для такого контейнера доступ к элементам (чтение, запись) последовательный, и не такой эффективный. Зато операции добавления, удаления или изменения порядка элементов очень быстрые.

Итератор list не является итератором прямого доступа. Поэтому для него неприменимы операции +, , +=, -=, а для контейнера недопустима операция индексации. Итераторы для этого контейнера перемещаются последовательно операциями ++ и.

Для иллюстрации работы с таким контейнером запишем всё ту же задачу нахождения всех простых чисел, не превосходящих N (для единообразия и сравнения с предыдущими вариантами):

Здесь первая половина кода (оператор << для списка) только декоративная реализация для диагностики и удобства, а в остальной части проделывается следующее:

  • Формируется список list<int> натуральных чисел диапазона [2…N] – строки 19 – 22;

  • Для каждого (оставшегося) числа из всего последующего списка удаляются кратные ему элементы – строка 31;

  • И так до тех пор, пока очередное проверяемое число не превысит квадратный корень из N – строка 26 (в теории чисел показано, что делимость можно проверять не до N-1, а до числа, превышающего корень квадратный N);

Из особенностей кода, и контейнеров list вообще, нужно обратить внимание на то, что после удаления элемента, указываемого текущим значением итератора, значение итератора становится неопределённым. Если нам нужно продолжать итерацию, то мы должны работать с копией итератора (i в показанном коде).

Выполнением кода мы можем проверить, что результаты его в точности аналогичны предыдущим вариантам. Перед запуском программы, не забудьте определить аргумент команды равный 300, как мы это делали в предыдущем уроке.
list c++, лист с++, контейнеры STL C++ , Standard Template Library, контейнер с++, двусвязный список

Рассылка новых уроков по программированию:

Контейнеры STL: list. Часть 4
Оцени эту статью

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *