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

Контейнеры 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, контейнер с++, двусвязный список

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

Olej

Об авторе Olej

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

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

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>