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




Список C ++, лист з ++, Контейнери C ++ STL , Стандартна бібліотека шаблонів, контейнер з ++, двонаправлений список з ++У третій частині уроків про контейнери 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, як ми це робили в попередньому уроці.
Список C ++, лист з ++, Контейнери C ++ STL , Стандартна бібліотека шаблонів, контейнер з ++, двусвязний список

Нові уроки з програмування:

дата
сторінка
Контейнери STL: list (двусвязний список). Частина 4
рейтинг
51зірка1зірка1зірка1зірка1зірка
Olej

Про Olej

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

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>