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

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


Згоден отримувати повідомлення від purecodecpp.com на мій e-mail

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

Про Olej

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

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

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