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

В третьей части уроков о контейнерах 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, как мы это делали в предыдущем уроке.