Основы программирования на С++ для начинающих

Контейнеры 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, как мы это делали в предыдущем уроке.
list c++, лист с++, контейнеры STL C++ , Standard Template Library, контейнер с++, двусвязный список

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

  1. нихрена не понятно… статья написана коряво и поверхностно не ожидал от purecode такого отношения.
    Это одна из тем для гейм дева, а к ней так некрасиво отнеслись, мало того неясно ничего после прочтения.

  2. Если “нихрена не понятно”, то нужно взять и перечитать по 2-му разу, по 3-му … для лучшего усвоения.

    А если “статья написана коряво и поверхностно” – то возьмите и напишите от себя авторскую статью лучше.

  3. Согласен. Статья мало понятна, особенно начинающей аудитории. И перечитывание по несколько раз тут не поможет.

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

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